#coding:utf8 #author:HaxtraZ #description:红黑树,python实现 RED = 'red' BLACK = 'black' class RBT: def __init__(self): self.items = [] self.root = None def LEFT_ROTATE(self, x): # x是一个RBTnode y = x.right if y is None: # 右节点为空,不旋转 return else: beta = y.left x.right = beta if beta is not None: beta.parent = x p = x.parent y.parent = p if p is None: # x原来是root self.root = y elif x == p.left: p.left = y else: p.right = y y.left = x x.parent = y def RIGHT_ROTATE(self, y): # y是一个节点 x = y.right if x is None: # 右节点为空,不旋转 return else: beta = x.right y.left = beta if beta is not None: beta.parent = y p = y.parent x.parent = p if p is None: # y原来是root self.root = x elif y == p.left: p.left = x else: p.right = x x.right = y y.parent = x def INSERT(self, val): z = RBTnode(val) y = None x = self.root while x is not None: y = x if z.val < x.val: x = x.left else: x = x.right z.PAINT(RED) z.parent = y if y is None: # 插入z之前为空的RBT self.INSERT_FIXUP(z) elif y.color == RED: # z的父节点y为红色,需要fixup。 # 如果z的父节点y为黑色,则不用调整 if z.val < y.val: y.left = z else: y.right = z self.INSERT_FIXUP(z) def INSERT_FIXUP(self, z): # case 1:z为root节点 if self.root == None: z.PAINT(BLACK) self.root = z return # case 2:z的父节点为黑色 if self.parent.color == BLACK: # 包括了z处于第二层的情况 return # 下面的几种情况,都是z.parent.color == RED: # 节点y为z的uncle p = z.parent if p == p.parent.left: y = p.parent.right else: y = p.parent.left g = p.parent # g为x的grandpa # case 3-0:z没有叔叔。即:y为NIL节点 # 注意,此时z的父节点一定是RED if y is None: if z == p.left: # 3-0-0:z为右儿子,则把p左旋 # 转化为3-0-1或3-0-2的情况 self.LEFT_ROTATE(p) p, z = z, p g.PAINT(RED) p.PAINT(BLACK) if g.left == p: # 3-0-1:p为g的左儿子 self.RIGHT_ROTATE(g) else: # 3-0-2:p为g的右儿子 self.LEFT_ROTATE(g) # case 3-1:z有黑叔 elif y.color == BLACK: if p.right == z: # 3-1-0:z为右儿子,则左旋p # 转化为3-1-1或3-1-2 self.LEFT_ROTATE(p) p, z = z, p p.PAINT(BLACK) g.PAINT(RED) if p == g.left: # 3-1-1:p为g的左儿子,则右旋g self.RIGHT_ROTATE(g) else: # 3-1-2:p为g的右儿子,则左旋g self.LEFT_ROTATE(g) # case 3-2:z有红叔 # 则涂黑父和叔,涂红爷,g作为新的z,递归调用 else: y.PAINT(BLACK) p.PAINT(BLACK) g.PAINT(RED) self.INSERT_FIXUP(g) def DELETE(self, val): curNode = self.root while curNode is not None: if val < curNode.val: curNode = curNode.left elif val > curNode.val: curNode = curNode.right else: # 找到了值为val的元素,正式开始删除 if curNode.left is None and curNode.right is None: # case1:curNode为叶子节点:直接删除即可 if curNode == self.root: self.root = None else: p = curNode.parent if curNode == p.left: p.left = None else: p.right = None elif curNode.left is not None and curNode.right is not None: sucNode = self.SUCCESOR(curNode) curNode.val, sucNode.val = sucNode.val, curNode.val self.DELETE(sucNode.val) else: p = curNode.parent if curNode.left is None: x = curNode.right else: x = curNode.left if curNode == p.left: p.left = x else: p.right = x x.parent = p if curNode.color == BLACK: self.DELETE_FIXUP(x) curNode = None return False def FIND(self, val): class RBTnode: '''红黑树的节点类型''' def __init__(self, val): self.val = val self.left = None self.right = None self.parent = None del PAINT(self, color): self.color = colro