算法导论第十五章习题解答

import copy def MAX_UPSEQUENCE(X): """ 5) 也可以通过先排序，在求最长公共子序列的方法得到正确的结果 """ mx = 0 seqscount = [ 0 for i in range(0, len(X))] for i in range(len(X)-1, -1, -1): m = 0 for j in range(i, len(X)): if X[i] <= X[j]: m = seqscount[j] + 1 if m > seqscount[i]: seqscount[i] = m if seqscount[i] > mx: mx = seqscount[i] return seqscount, mx class COLOR: RED = "red" BLACK = "black" class TREENODE(): def __init__(self, key, index, color=COLOR.BLACK, parent = None): self.key = key self.parent = parent self.left = None self.right = None self.color = color self.index = index def setLeft(self, left): self.left = left left.parent = self def setRight(self, right): self.right = right right.parent = self def setColor(color): self.color = color class TREE(): def __init__(self): self.nil = TREENODE(None, None) self.root = self.nil def LEFT_ROTATE(T, x): y = x.right x.right = y.left if y.left != T.nil: y.left.parent = x y.parent = x.parent if x.parent == T.nil: T.root = y elif x == x.parent.left: x.parent.left = y else: x.parent.right = y y.left = x x.parent = y def RIGHT_ROTATE(T, x): y = x.left x.left = y.right if y.right != T.nil: y.right.parent = x y.parent = x.parent if x.parent == T.nil: T.root = y elif x == x.parent.left: x.parent.left = y else: x.parent.right = y y.right = x x.parent = y def RB_INSERT_FIXUP(T, z): while z.parent.color == COLOR.RED: if z.parent == z.parent.parent.left: y = z.parent.parent.right if y.color == COLOR.RED: z.parent.color = COLOR.BLACK y.color = COLOR.BLACK z.parent.parent.color = COLOR.RED z = z.parent.parent else: if z == z.parent.right: z = z.parent LEFT_ROTATE(T, z) z.parent.color = COLOR.BLACK z.parent.parent.color = COLOR.RED RIGHT_ROTATE(T, z.parent.parent) else: y = z.parent.parent.left if y.color == COLOR.RED: z.parent.color = COLOR.BLACK y.color = COLOR.BLACK z.parent.parent.color = COLOR.RED z = z.parent.parent else: if z == z.parent.left: z = z.parent RIGHT_ROTATE(T, z) z.parent.color = COLOR.BLACK z.parent.parent.color = COLOR.RED LEFT_ROTATE(T, z.parent.parent) T.root.color = COLOR.BLACK def RB_INSERT(T, z): z.right = T.nil z.left = T.nil z.parent = T.nil y = T.nil x = T.root while x != T.nil: y = x if z.key < x.key: x = x.left else: x = x.right z.parent = y if y == T.nil: T.root = z elif z.key < y.key: y.left = z else: y.right = z z.left = T.nil z.right = T.nil z.color = COLOR.RED RB_INSERT_FIXUP(T, z) def TREE_MAXIMUM(T, x): while x.right != T.nil: x = x.right return x def TREE_PREDECESSOR(T, x): if x.left != T.nil: return TREE_MAXIMUM(T, x.left) y = x.parent while y != T.nil and x == y.left: x = y y = y.parent return y def INORDER_TREE_WALK(T, x): if x != T.nil: print(x.key) INORDER_TREE_WALK(T, x.left) INORDER_TREE_WALK(T, x.right) """ 6)构建一棵红黑树，将x中的值作为节点加入到红黑树中，每个节点找到其值的前驱节点 并将其前驱节点的最大升序子序列拷贝后将自己加入其中 """ def MAX_UPSEQUENCE_logn(X): T = TREE() m = [ [] for i in range(0, len(X))] ml = 0 flag = 0 for i in range(0, len(X)): node = TREENODE(X[i], i) RB_INSERT(T, node) preNode = TREE_PREDECESSOR(T, node) if preNode != T.nil: m[i] = copy.deepcopy(m[preNode.index]) m[i].append(i) if len(m[i]) > ml: ml = len(m[i]) flag = i return m[flag] if __name__ == "__main__": X = [12,3,17,42,9,7,4,0,19,21,6,13,496,1,25] l,m = MAX_UPSEQUENCE(X) for i in range(0, len(X)): if m == l[i]: print(X[i]) m = m - 1 print("--------------") l = MAX_UPSEQUENCE_logn(X) for i in range(0, len(l)): print(X[l[i]])