红 黑 树
RBTree
完整代码如下：
NIL = Node(-1, 1, None, None) NIL.left = NIL NIL.right = NIL class Node: def __init__(self, key = -1, color = 0, left = NIL, right = NIL): self.key = key self.color = color self.left = left self.right = right def __repr__(self): return "[" + str(self.key) + "-" + str(self.color) + ": (" + str(self.left.key) + "-" + str(self.left.color) + ", " + str(self.right.key) + "-" + str(self.right.key) + ")]"
class RBTree: def __init__(self, root = NIL): self.root = root def insert(self, key): self.root = self.__insert(self.root, key) self.root.color = 1 return self.root def __insert(self, root, key): if root == NIL: return Node(key) if root.key == key: return root if root.key < key: root.right = self.__insert(root.right, key) else: root.left = self.__insert(root.left, key) return self.insert_maintain(root) def insert_maintain(self, root): if not self.has_red_child(root): return root if root.left.color == 0 and root.right.color == 0: if not self.has_red_child(root.left) and not self.has_red_child(root.right): return root root.color = 0 root.left.color = root.right.color = 1 return root if root.left.color == 0 and not self.has_red_child(root.left): return root if root.right.color == 0 and not self.has_red_child(root.right): return root if root.left.color == 0: if root.left.right.color == 0: root.left = self.left_rotate(root.left) root = self.right_rotate(root) else: if root.right.left.color == 0: root.right = self.right_rotate(root.right) root = self.left_rotate(root) root.color = 0 root.left.color = root.right.color = 1 return root def erase(self, key): self.root = self.__erase(self.root, key) self.root.color = 1 return self.root def __erase(self, root, key): if root == NIL: return NIL if root.key < key: root.right = self.__erase(root.right, key) elif root.key > key: root.left = self.__erase(root.left, key) else: if root.left == NIL or root.right == NIL: tmp = root.left if root.left != NIL else root.right tmp.color += root.color del root return tmp tmp = self.get_pre(root) root.key = tmp.key root.left = self.__erase(root.left, tmp.key) return self.erase_maintain(root) def erase_maintain(self, root): if root.left.color != 2 and root.right.color != 2: return root if self.has_red_child(root): root.color = 0 if root.left.color == 0: root = self.right_rotate(root) root.right = self.erase_maintain(root.right) else: root = self.left_rotate(root) root.left = self.erase_maintain(root.left) root.color = 1 return root if root.left.color == 2 and not self.has_red_child(root.right) or root.right.color == 2 and not self.has_red_child(root.left): root.left.color -= 1 root.right.color -= 1 root.color += 1 return root if root.left.color == 2: root.left.color = 1 if root.right.right.color != 0: root.right.color = 0 root.right = self.right_rotate(root.right) root.right.color = 1 root = self.left_rotate(root) root.color = root.left.color else: root.right.color = 1 if root.left.left.color != 0: root.left.color = 0 root.left = self.left_rotate(root.left) root.left.color = 1 root = self.right_rotate(root) root.color = root.right.color root.left.color = root.right.color = 1 return root def left_rotate(self, root): tmp = root.right root.right = tmp.left tmp.left = root return tmp def right_rotate(self , root): tmp = root.left root.left = tmp.right tmp.right = root return tmp def get_pre(self, root): tmp = root.left while tmp.right != NIL: tmp = tmp.right return tmp def has_red_child(self, root): return root.left.color == 0 or root.right.color == 0 def inorder(self, root): if root.left != NIL: self.inorder(root.left) print(root) if root.right != NIL: self.inorder(root.right) return None
测试代码：
t = RBTree() for i in range(1, 7): t.insert(i) if i % 3 == 0: t.erase(i - 1) t.inorder(t.root)
🔴⚫️🌲
😊性质
每个节点非黑即红
根节点一定是黑色
叶子节点（NIL）是黑色
如果节点是红色，那么它的两个子节点都是黑色
从根节点到叶节点的所有路径，黑色节点数量相同
由性质4、5可推知：红黑树中，最长路径 == 2倍最短路径
💸Node
NIL节点，作为空节点（叶子节点）使用，默认单重黑。这样便于操作
正常新建节点，默认color为红，这样最大程度不影响性质5
红节点：没有子节点 or 两个黑色子节点
黑节点：如果只有一个子节点，那么必定是红色
🔫RBTree
封装红黑树的主要方法插入和删除
由于根节点到路径长度最坏相差一半，所以红黑树是一个基本平衡的二叉搜索树。
它没有AVL树那么绝对平衡，但是红黑树相比AVL旋转操作要少，而且删除操作也比AVL树效率更高。
👕insert
调整策略：
首先明确插入调整站在祖父节点看。（相当于做了一个延时操作）
其次插入调整是为了解决两个红色节点相邻的问题
🐱Case1 🐱
黑红红： 采取红色上浮，变为红黑黑
🐶Case2🐶
黑红黑：LL失衡，大右旋（如下图2），变为红黑黑
🍗erase
调整策略：
红色节点
度0：直接删
度1：不存在
度2：转为前驱
黑色节点
度0：双黑顶替（延时）
度1：红色点互换
度2：转为前驱
首先明确删除调整是站在父节点 上
其次删除调整是为了调整双黑节点
🐯Case1🐯
兄弟黑+兄弟孩子黑：双黑上浮，黑红黑
🐻Case2🐻
兄弟黑+兄弟同侧孩子红：RR失衡，大左旋（如下图2），根变左孩子颜色（右旋右孩子），孩子都变黑，双黑少一重
🐼Case3🐼
同case2： 不过先小旋（新根变黑，老根变红），在大旋
- 如果兄弟红，那么就旋成黑，就可以啦（O(∩_∩)O）
不要忘了，每次插入或删除操作后，根强制为黑
