本专栏的上一篇文章使用Python实现了红黑树的插入操作。参考：https://blog.csdn.net/weixin_43790276/article/details/106456969
本篇文章使用Python实现红黑树的删除操作。
先将红黑树的5条特性列出来：
1. 节点是红色或黑色。
2. 根节点是黑色。
3. 所有叶子节点都是黑色的空节点。(叶子节点是NIL节点或NULL节点)
4. 每个红色节点的两个子节点都是黑色节点。(从每个叶子节点到根的所有路径上不能有两个连续的红色节点)
5. 从任一节点到其每个叶子节点的所有路径都包含相同数目的黑色节点。
删除操作是很复杂的，先把复杂的情况分解成各种情况，然后一种一种的解决。
一、代码准备
在进行红黑树的删除操作前，要先有一棵红黑树，所以这里使用上一篇文章中的代码(文末附了完整代码)，先在红黑树中插入数据。
1. 定义了一个节点类 RBNode ，用于创建新节点。
2. 定义了红黑树类 RBBinaryTree ，类中实现了按树形结构打印红黑树的方法 show_tree()，并且根据红黑树的节点颜色，打印值时打印对应的颜色。还有二叉搜索树的插入方法 insert(root, value) 和搜索方法 search(root, data) 。同时还有红黑树的插入方法 rb_insert(value)，获取后继节点的get_min(root)方法，以及对红黑树进行调整的左旋方法left_rotate(node)，右旋方法right_rotate(node)和变色方法change_color(node)。
二、实现红黑树的删除方法
红黑树的删除方法可以分两个步骤实现，第一步是按照二叉搜索树的方法将节点删除，第二步是对删除节点后的红黑树进行调整，使红黑树重新满足5条特性。不过，在实际的代码中，要将这两个步骤倒过来，先对红黑树进行调整，然后删除节点，因为删除节点后，节点间的关系就“断开”了，不方便进行调整。
二叉搜索树删除节点，分为三种情况：
1. 被删除节点为叶节点，即被删除节点没有左子树和右子树。这种情况直接找到节点将其删除。
2. 被删除节点有一棵子树，这棵子树可以是左子树或右子树。这种情况将节点删除后，用节点的子树替换被删除节点的位置，进行“补位”。
3. 被删除节点有两棵子树，即被删除节点同时有左子树和右子树。这种情况先找到被删除节点的后继节点，将后继节点的值“转移”到被删除节点中，然后删除后继节点。而后继节点一定属于前两种情况的其中之一。
因此，对于红黑树的删除，也是按这个思路。
为了方便理解，先申明几个需要使用到的术语：
待删除节点：需要被删除的节点，因为调整放在删除的前面，所以在进行调整时待删除节点还在红黑树中，用D(delete_node)表示。
因素节点：因为这个节点的变化，使红黑树的结构发生了变化，用F(factor_node)表示。在第一次进行调整时，因素节点就是待删除节点，如果一次调整后进行递归调整，递归时的因素节点可能会发生改变。
父节点：因素节点的父节点，用P(parent_node)表示。
兄弟节点：因素节点的父节点的另一个子节点，用B(brother_node)表示。
兄弟节点的左子节点：因素节点的兄弟节点的左子节点，用BL(brother_node.left_child)表示。
兄弟节点的右子节点：因素节点的兄弟节点的右子节点，用BR(brother_node.right_child)表示。
本文的所有结构图中，蓝色节点表示该节点可以是红节点或黑节点，不影响调整步骤和平衡结果。
按照被删除节点是否有子节点，分三种情况：
1. 被删除节点是叶节点(这里的叶节点不是指叶子节点NIL)，叶节点没有非空子节点。
被删除节点是叶节点时，根据被删除节点的颜色，可以分为两种情况。
1.1 被删除节点是红节点，直接将节点删除，不会破坏红黑树的5条特性，不需要进行调整。
1.2 被删除节点是黑节点。这是红黑树删除中最复杂的部分，具体有如下三种情况。
1.2.1 被删除节点是根节点。直接将节点删除，红黑树变成一棵空树。
1.2.2 被删除节点是左子节点。根据兄弟节点的颜色，又可以分如下四种情况。
1.2.2.1 兄弟节点是黑节点，并且兄弟节点的右子节点是红节点。
第一步将兄弟节点的颜色变成父节点的颜色，将父节点和兄弟节点的右子节点的颜色都设置成黑色。第二步以父节点作为旋转节点进行左旋。调整完成，此时将待删除节点从红黑树中删除即可。
删除节点后，黑节点减少(破坏了特性5)，所以要找到一个红节点变成黑节点，补充减少的黑色。这里相当于是“借用”了BR节点的红色，变成黑色来补充损失的黑色。
这种情况只要BR节点是红色即可，不管BL节点是否存在和BL是什么颜色。如果BL节点为空，则调整过程与上图一样，没有变化。
如果BL节点是一个红节点，即BL和BR都是红节点，BL的加入不会对红黑树的特性产生影响，调整的过程如下图所示。
如果BL节点是黑节点，调整方式也不变。因素节点是叶节点时，BL节点不可能是非空黑节点，因为在删除节点前，红黑树是满足5条特性的，因素节点和兄弟节点都是黑色，如果兄弟节点有黑色子节点，则因素节点也一定有黑色子节点，这与因素节点是叶节点矛盾。如果第一次调整后没有达到平衡，将因素节点变成待删除节点的父节点进行递归，因素节点不再是叶节点，这时可能会遇到BL节点是黑节点的情况，如后面的1.2.2.3调整后就可能变成这种情况。调整方式不变，并且经过此次调整后即可结束调整，调整过程如下图(D的兄弟节点一开始是黑节点，上一次调整中变成了红色)。
1.2.2.2 兄弟节点是黑节点，并且兄弟节点的左子节点是红节点。
第一步将兄弟节点变成红色，将兄弟节点的左子节点变成黑色。第二步以兄弟节点作为旋转节点进行右旋。这时二叉树的结构变成了1.2.2.1的情况，第一次调整结束，因素节点不变，递归进行下一次调整。
删除节点后，黑节点减少(破坏了特性5)，这里相当于是“借用”了BL节点的红色，变成黑色来补充损失的黑色。
这种情况只要BL节点是红色即可，不管BR节点是否存在和BR是什么颜色。如果BR节点为空，则调整过程与上图一样，没有变化。如果BR节点是红色，即BL和BR都是红节点，则会直接按1.2.2.1进行处理。
如果BR是黑节点，调整方式也不变。与上面的1.2.2.1一样，因素节点是叶节点时，BR节点不可能是黑节点。在后面的1.2.2.3中，如果第一次调整后没有达到平衡，将因素节点变成待删除节点的父节点进行递归，因素节点不再是叶节点，这时可能会遇到BR节点是黑节点的情况，如后面的1.2.2.3调整后就可能变成这种情况。调整方式不变，调整过程如下图(D的兄弟节点一开始是黑节点，上一次调整中变成了红色)。
1.2.2.3 兄弟节点是黑节点，并且兄弟节点没有子节点。
第一步将兄弟节点变成红色。第二步判断父节点是不是红节点。如果父节点是红节点，直接将父节点变成黑节点，调整结束。如果父节点是黑节点，则将因素节点变为父节点，进行下一次递归调整，直到父节点是根节点。
删除节点后，黑节点减少(破坏了特性5)，这里相当于是“借用”了父节点的红色，变成黑色来补充损失的黑色，如果父节点不是红色，则由父节点去(父节点的BL、BR或P)“借”，如果一直递归到父节点是根节点，都没地方可以“借”，则所有叶节点到根节点的路径上黑节点都减一。
在递归调整的过程中，可能会遇到1.2.2.1和1.2.2.2两种情况以及后面的1.2.3.1和1.2.3.2两种情况，也可能遇到BL和BR都是黑节点的情况。
如果BL和BR都是黑节点，则继续将兄弟节点变成红色，将因素节点变为父节点，继续递归下去，调整过程如下图(D的兄弟节点一开始是黑节点，上一次调整中变成了红色，第二次调整F变成了D的父节点，此时BL和BR都为黑色，则继续将B变红，递归处理)。
1.2.2.4 兄弟节点是红节点。此时BL、BR和P一定都是黑节点，否则不满特性4。
第一步将兄弟节点变成黑色，将父节点变成红色。第二步以父节点作为旋转节点进行左旋。这时二叉树的结构变成了1.2.2.3的情况，第一次调整结束，因素节点不变，递归进行下一次调整。并且下一次调整中因素节点的父节点是红节点，一定可以调整完成。
删除节点后，黑节点减少(破坏了特性5)，这里相当于是“借用”了兄弟节点的红色，变成黑色来补充损失的黑色。
1.2.3 被删除节点是右子节点。
这与被删除节点是左节点的情况互为镜像，原理也一样，根据兄弟节点的颜色，分如下四种情况。
1.2.3.1 兄弟节点是黑节点，并且兄弟节点的左子节点是红节点。
第一步将兄弟节点的颜色变成父节点的颜色，将父节点和兄弟节点的左子节点的颜色都设置成黑色。第二步以父节点作为旋转节点进行右旋。调整完成，此时将待删除节点从红黑树中删除即可。
与被删除节点是左子节点的原理一样，只要BL是红节点即可，不用关注是否有BR节点和BR是什么颜色，处理方式都一样，这里就不展开了。
1.2.3.2 兄弟节点是黑节点，并且兄弟节点的右子节点是红节点。
第一步将兄弟节点变成红色，将兄弟节点的右子节点变成黑色。第二步以兄弟节点作为旋转节点进行左旋。这时二叉树的结构变成了1.2.3.1的情况，第一次调整结束，因素节点不变，递归进行下一次调整。
与被删除节点是左子节点一样，只要BR是红节点即可，不用关注是否有BL节点和BL是什么颜色，处理方式都一样。
1.2.3.3 兄弟节点是黑节点，并且兄弟节点没有子节点。
第一步将兄弟节点变成红色。第二步判断父节点是不是红节点。如果父节点是红节点，直接将父节点变成黑节点，调整结束。如果父节点是黑节点，则将因素节点变为父节点，进行下一次递归调整，直到父节点是根节点。
在递归调整的过程中，可能会遇到1.2.3.1和1.2.3.2两种情况以及前面的1.2.2.1和1.2.2.2两种情况，也可能遇到BL和BR都是黑节点的情况。
如果BL和BR都是黑节点，则继续将兄弟节点变成红色，将因素节点变为父节点，继续递归下去。
1.2.3.4 兄弟节点是红节点。此时BL、BR和P一定都是黑节点，否则不满特性4。
第一步将兄弟节点变成黑色，将父节点变成红色。第二步以父节点作为旋转节点进行右旋。这时二叉树的结构变成了1.2.3.3的情况，第一次调整结束，因素节点不变，递归进行下一次调整。并且下一次调整中因素节点的父节点是红节点，一定可以调整完成。
到这里，待删除节点是叶节点的所有情况都分析完成了，代码实现如下。
def _rb_delete_no_child(self, node):
"""红黑树删除两个子节点都为空的节点"""
if node == self.root:
self.root = None
self.root.color = 'black'
return
factor_node = node
# 如果待删除节点为黑节点则需要进行调整
if factor_node.color is 'black':
while True:
parent_node = factor_node.parent
brother_node = parent_node.right_child if factor_node is parent_node.left_child else parent_node.left_child
# 待删除节点是左子节点
if factor_node is parent_node.left_child:
# 如果兄弟节点是黑节点
if brother_node.color is 'black':
# 如果兄弟节点没有子节点(递归处理时如果兄弟节点的两个子节点都是黑节点)
if brother_node.left_child is None and brother_node.right_child is None or \
((brother_node.left_child and brother_node.left_child.color is 'black') and
(brother_node.right_child and brother_node.right_child.color is 'black')):
self.change_color(brother_node)
if parent_node.color is 'red':
self.change_color(parent_node)
break
else:
if parent_node == self.root:
break
factor_node = parent_node
# 如果兄弟节点有右子节点，此右节点一定是红节点(递归处理时，如果兄弟节点的右子节点为红节点)
elif brother_node.right_child is not None and brother_node.right_child.color is 'red':
brother_node.color = parent_node.color
parent_node.color, brother_node.right_child.color = 'black', 'black'
self.left_rotate(parent_node)
break
# 如果兄弟节点有左节点，此左节点一定是红节点(递归处理时，如果兄弟节点的左子节点为红节点)
else:
brother_node.color, brother_node.left_child.color = 'red', 'black'
self.right_rotate(brother_node)
# 如果兄弟节点是红节点
elif brother_node.color is 'red':
self.change_color(parent_node)
self.change_color(brother_node)
self.left_rotate(parent_node)
# 待删除节点是右子节点
if factor_node is parent_node.right_child:
if brother_node.color is 'black':
# 如果兄弟节点没有子节点(递归处理时如果兄弟节点的两个子节点都是黑节点)
if brother_node.left_child is None and brother_node.right_child is None or \
((brother_node.left_child and brother_node.left_child.color is 'black') and
(brother_node.right_child and brother_node.right_child.color is 'black')):
self.change_color(brother_node)
if parent_node.color is 'red':
self.change_color(parent_node)
break
else:
if parent_node == self.root:
break
factor_node = parent_node
# 如果兄弟节点有左节点，此左节点一定是红节点(递归处理时，如果兄弟节点的左子节点为红节点)
elif brother_node.left_child is not None and brother_node.left_child.color is 'red':
brother_node.color = parent_node.color
parent_node.color, brother_node.left_child.color = 'black', 'black'
self.right_rotate(parent_node)
break
# 如果兄弟节点有右节点，此右节点一定是红节点(递归处理时，如果兄弟节点的右子节点为红节点)
else:
brother_node.color, brother_node.right_child.color = 'red', 'black'
self.left_rotate(brother_node)
# 如果兄弟节点是红节点
elif brother_node.color is 'red':
self.change_color(parent_node)
self.change_color(brother_node)
self.right_rotate(parent_node)
if node is node.parent.left_child:
node.parent.left_child = None
else:
node.parent.right_child = None
node.parent = None_rb_delete_no_child(node): 红黑树删除叶节点的方法。删除叶节点后的调整是三种情况中最复杂的一种，要先理解每一种情况的调整方法，以及递归处理时可能会变成哪些情况。代码是按照上面的分析过程实现的，需要仔细分析并理解。
2. 被删除节点有一个子节点。
被删除节点要么有左子节点没有右子节点，要么没有左子节点有右子节点。这种情况的处理比较简单，因为在删除前，红黑树满足5条特性，所以不管子节点是左子节点还是右子节点，这个子节点一定是红节点，否则不满足特性5，进一步可以得出被删除节点一定是黑节点，否则不满足特性4。
删除比较简单，第一步将待删除节点的子节点变成黑色，第二步按照二叉搜索树的方法将待删除节点删除，即用子节点补位到待删除节点的位置。
在这个过程中，不用区分待删除节点的子节点是左子节点还是右子节点，也不用区分待删除节点是其父节点的左子节点还是右子节点，或者待删除节点是不是根节点。处理方式都一样，将其子节点变黑补位即可，代码如下。
def _rb_delete_one_child(self, node):
"""红黑树删除有一个子节点的节点"""
if node.left_child:
self.change_color(node.left_child)
if node.parent and node.parent.left_child == node:
node.left_child.parent, node.parent.left_child = node.parent, node.left_child
elif node.parent and node.parent.right_child == node:
node.left_child.parent, node.parent.right_child = node.parent, node.left_child
else:
self.root = node.left_child
node.left_child.parent, node.left_child = None, None
elif node.right_child:
self.change_color(node.right_child)
if node.parent and node.parent.left_child == node:
node.right_child.parent, node.parent.left_child = node.parent, node.right_child
elif node.parent and node.parent.right_child == node:
node.right_child.parent, node.parent.right_child = node.parent, node.right_child
else:
self.root = node.right_child
node.right_child.parent, node.right_child = None, None
node.parent = None_rb_delete_one_child(self, node): 红黑树删除只有一个子节点的节点。这种情况的处理很简单，代码也比较简单。
3. 被删除节点有两个子节点，即被删除节点同时有左子节点和右子节点。
根据二叉搜索树的删除方法，这种情况需要找到被删除节点的前继节点或后继节点，本文中使用后继节点，用后继节点的值替换被删除节点的值，避免树的“断裂”，然后将后继节点删除。后继节点是不可能有左子节点的，因此后继节点要么没有子节点，要么有一个右子节点，处理方法可以分为两种。
3.1 后继节点没有子节点。
这时调用上面的情况1，将后继节点删除。
3.2 后继节点有一个右子节点。
后继节点一定是黑节点，后继节点的右子节点一定是红节点，调用上面的情况2，将后继节点删除。代码实现如下。
def _rb_delete(self, node):
"""删除节点的三种情况"""
if node.left_child is None and node.right_child is None:
self._rb_delete_no_child(node)
elif node.left_child and not node.right_child or not node.left_child and node.right_child:
self._rb_delete_one_child(node)
else:
rear_node = self.get_min(node.right_child)
node.data = rear_node.data
self._rb_delete(rear_node)删除节点，首先这个节点要在红黑树中，因此不能创建一个节点然后删除，而是根据节点的值，先到红黑树中进行搜索，如果这个值存在红黑树中，则将其删除。(本文中的红黑树不会添加重复的值，这个可以按需进行修改)
最后，红黑树的删除方法如下。
def rb_delete(self, value):
"""红黑树删除"""
if not self.is_empty():
node_delete = self.search(self.root, value)
if node_delete:
self._rb_delete(node_delete)
else:
raise KeyError("Error, {value} not in this tree".format(value=value))
else:
raise KeyError("Error, tree is empty")rb_delete(value): 红黑树的删除方法。
总结，红黑树的删除中，被删除节点是叶节点时最复杂，需要仔细分析每一种情况。当被删除节点是黑节点时，会破坏特性5，经过被删除节点的路径上黑节点少了一个，所以要找一个红节点变成黑色来补充，每一种情况分别是去BL、BR或P“借”，如果没有红节点可以“借”，则让父节点去“借”，一直到父节点变成根节点都没有红节点可以“借”，则所有路径上的黑节点都减一，从而保持平衡。被删除节点有一个子节点时比较简单，将子节点变黑补位即可。被删除节点有两个子节点时，可以将被删除节点转换成后继节点，从而变成前两种情况进行处理。
三、红黑树删除方法的验证
1. 先插入数据到红黑树中，如还是用之前的数据[50, 77, 55, 29, 10, 30, 66, 18, 80, 51, 90]。
if __name__ == '__main__':
tree = RBBinaryTree()
data = [50, 77, 55, 29, 10, 30, 66, 18, 80, 51, 90]
for i in data:
tree.rb_insert(i)
tree.show_tree()运行结果：
插入数据后红黑树的结构如下图。
现在删除其中的一个节点，如删除节点66。
tree.rb_delete(66)
tree.show_tree()运行结果：
删除节点66后红黑树的结构如下图。
可以看到，红黑树的删除功能已经实现了。不过，由于数据比较少，没有包含删除的每一种情况，本文中也不可能每种情况都进行验证，并且数据量大时，也不方便画出红黑树的结构图。所以，有必要实现一个方法来对红黑树进行自查，判断当前红黑树是否满足5条特性。
def rb_check(self):
"""检查红黑树是否满足5条特性"""
if self.is_empty():
print("空树")
return
queue = list()
queue.insert(0, self.root)
height = 0
while len(queue):
node = queue.pop()
if node.color is not "red" and node.color is not "black":
raise Exception("节点{}不满足特性1".format(node.data))
if node is self.root and node.color is not "black":
raise Exception("节点{}不满足特性2".format(node.data))
if node.color is "red" and (node.left_child and node.left_child.color is "red" or
node.right_child and node.right_child.color is "red"):
raise Exception("节点{}不满足特性4".format(node.data))
if node.left_child is None and node.right_child is None:
path = 0
cur = node
while cur:
if cur.color is "black":
path += 1
cur = cur.parent
if height and path != height:
raise Exception("节点{}不满足特性5".format(node.data))
else:
height = path
if node.left_child is not None:
queue.insert(0, node.left_child)
if node.right_child is not None:
queue.insert(0, node.right_child)
print("满足红黑树的5条特性,叶子节点到根节点的非空黑节点个数为{}".format(height))rb_check(): 对当前红黑树进行判断，如果不满足5条特性中的一条，则抛出异常。此方法对红黑树的所有节点进行层序遍历，依次对每一个节点判断是否满足红黑树的特性。
下面添加一棵有1000个节点的红黑树，进行验证。
data = range(1000)
for i in data:
tree.rb_insert(i)
tree.rb_check()
tree.rb_delete(66)
print("--- after delete ---")
tree.rb_check()运行结果：
满足红黑树的5条特性,叶子节点到根节点的非空黑节点个数为9
--- after delete ---
满足红黑树的5条特性,叶子节点到根节点的非空黑节点个数为9代码附在后面，更多情况请自行取用验证。(部分代码是可以精简的，不过为了保证可读性和方便与分析过程对照，这样更好一点)
四、完整代码
# coding=utf-8
class RBNode(object):
"""节点类"""
def __init__(self, data, left_child=None, right_child=None, color='red'):
self.data = data
self.parent = None
self.left_child = left_child
self.right_child = right_child
self.color = color
class RBBinaryTree(object):
"""红黑树类"""
def __init__(self):
self.__root = None
self.prefix_branch = '├'
self.prefix_trunk = '|'
self.prefix_leaf = '└'
self.prefix_empty = ''
self.prefix_left = '─L─'
self.prefix_right = '─R─'
def is_empty(self):
return not self.__root
@property
def root(self):
return self.__root
@root.setter
def root(self, value):
self.__root = value if isinstance(value, RBNode) else RBNode(value)
def left_rotate(self, node):
"""红黑树左旋"""
parent_node, right_node = node.parent, node.right_child
if not right_node:
return
# 1.node是旋转节点，将旋转节点的右子节点的左子节点变为旋转节点的右子节点
node.right_child = right_node.left_child
if node.right_child:
node.right_child.parent = node
# 2.将旋转节点修改为右子节点的左子节点
right_node.left_child, node.parent = node, right_node
# 3.将右子节点替换旋转节点的位置，作为旋转节点父节点的子节点
if not parent_node:
self.root = right_node
else:
if parent_node.left_child == node:
parent_node.left_child = right_node
else:
parent_node.right_child = right_node
right_node.parent = parent_node
def right_rotate(self, node):
"""红黑树右旋"""
parent_node, left_node = node.parent, node.left_child
if not left_node:
return
# 1.node是旋转节点，将旋转节点的左子节点的右子节点变为旋转节点的左子节点
node.left_child = left_node.right_child
if node.left_child:
node.left_child.parent = node
# 2.将旋转节点修改为左子节点的右子节点
left_node.right_child, node.parent = node, left_node
# 3.将左子节点替换旋转节点的位置，作为旋转节点父节点的子节点
if not parent_node:
self.root = left_node
else:
if parent_node.left_child == node:
parent_node.left_child = left_node
else:
parent_node.right_child = left_node
left_node.parent = parent_node
def change_color(self, node):
"""红黑树变色"""
if node.color is 'red':
node.color = 'black'
elif node.color is 'black':
node.color = 'red'
def rb_insert(self, value):
"""红黑树插入"""
node = value if isinstance(value, RBNode) else RBNode(value)
if self.search(self.root, node.data):
return
if self.is_empty():
node.color = 'black'
self.root = node
return
self.insert(self.root, node)
factor_node = node
while True:
parent_node = factor_node.parent
if parent_node.color is 'red':
grandparent_node = parent_node.parent
if parent_node is grandparent_node.left_child:
uncle_node = grandparent_node.right_child
else:
uncle_node = grandparent_node.left_child
# 如果父节点为红节点且叔节点为黑节点
if uncle_node is None or uncle_node and uncle_node.color is 'black':
if parent_node == grandparent_node.left_child:
# 先左旋为左左结果，然后父节点和祖父节点变色，再右旋
if factor_node == parent_node.right_child:
self.left_rotate(parent_node)
self.change_color(factor_node)
else:
self.change_color(parent_node)
self.change_color(grandparent_node)
self.right_rotate(grandparent_node)
elif parent_node == grandparent_node.right_child:
# 先右旋为右右结构，然后父节点和祖父节点变色，再左旋
if factor_node == parent_node.left_child:
self.right_rotate(parent_node)
self.change_color(factor_node)
else:
self.change_color(parent_node)
self.change_color(grandparent_node)
self.left_rotate(grandparent_node)
break
# 如果父节点为红节点且叔节点也为红节点
elif uncle_node and uncle_node.color is 'red':
# 父节点和叔节点变色，祖父节点变色(祖父节点是根节点除外)
self.change_color(parent_node)
self.change_color(uncle_node)
if grandparent_node != self.root:
self.change_color(grandparent_node)
# 祖父节点变成红节点后，将祖父节点作为新的因素节点，判断其父节点，避免不满足特性4
factor_node = grandparent_node
else:
break
def insert(self, root, value):
"""二叉搜索树插入节点-递归"""
node = value if isinstance(value, RBNode) else RBNode(value)
if self.is_empty():
self.root = node
return
if root is None:
root = node
elif node.data < root.data:
root.left_child = self.insert(root.left_child, value)
root.left_child.parent = root
elif node.data > root.data:
root.right_child = self.insert(root.right_child, value)
root.right_child.parent = root
return root
def rb_delete(self, value):
"""红黑树删除"""
if not self.is_empty():
node_delete = self.search(self.root, value)
if node_delete:
self._rb_delete(node_delete)
else:
raise KeyError("Error, {value} not in this tree".format(value=value))
else:
raise KeyError("Error, tree is empty")
def _rb_delete(self, node):
"""删除节点的三种情况"""
if node.left_child is None and node.right_child is None:
self._rb_delete_no_child(node)
elif node.left_child and not node.right_child or not node.left_child and node.right_child:
self._rb_delete_one_child(node)
else:
rear_node = self.get_min(node.right_child)
node.data = rear_node.data
self._rb_delete(rear_node)
def _rb_delete_no_child(self, node):
"""红黑树删除两个子节点都为空的节点"""
if node == self.root:
self.root = None
self.root.color = 'black'
return
factor_node = node
# 如果待删除节点为黑节点则需要进行调整
if factor_node.color is 'black':
while True:
parent_node = factor_node.parent
brother_node = parent_node.right_child if factor_node is parent_node.left_child else parent_node.left_child
# 待删除节点是左子节点
if factor_node is parent_node.left_child:
# 如果兄弟节点是黑节点
if brother_node.color is 'black':
# 如果兄弟节点没有子节点(递归处理时如果兄弟节点的两个子节点都是黑节点)
if brother_node.left_child is None and brother_node.right_child is None or \
((brother_node.left_child and brother_node.left_child.color is 'black') and
(brother_node.right_child and brother_node.right_child.color is 'black')):
self.change_color(brother_node)
if parent_node.color is 'red':
self.change_color(parent_node)
break
else:
if parent_node == self.root:
break
factor_node = parent_node
# 如果兄弟节点有右子节点，此右节点一定是红节点(递归处理时，如果兄弟节点的右子节点为红节点)
elif brother_node.right_child is not None and brother_node.right_child.color is 'red':
brother_node.color = parent_node.color
parent_node.color, brother_node.right_child.color = 'black', 'black'
self.left_rotate(parent_node)
break
# 如果兄弟节点有左节点，此左节点一定是红节点(递归处理时，如果兄弟节点的左子节点为红节点)
else:
brother_node.color, brother_node.left_child.color = 'red', 'black'
self.right_rotate(brother_node)
# 如果兄弟节点是红节点
elif brother_node.color is 'red':
self.change_color(parent_node)
self.change_color(brother_node)
self.left_rotate(parent_node)
# 待删除节点是右子节点
if factor_node is parent_node.right_child:
if brother_node.color is 'black':
# 如果兄弟节点没有子节点(递归处理时如果兄弟节点的两个子节点都是黑节点)
if brother_node.left_child is None and brother_node.right_child is None or \
((brother_node.left_child and brother_node.left_child.color is 'black') and
(brother_node.right_child and brother_node.right_child.color is 'black')):
self.change_color(brother_node)
if parent_node.color is 'red':
self.change_color(parent_node)
break
else:
if parent_node == self.root:
break
factor_node = parent_node
# 如果兄弟节点有左节点，此左节点一定是红节点(递归处理时，如果兄弟节点的左子节点为红节点)
elif brother_node.left_child is not None and brother_node.left_child.color is 'red':
brother_node.color = parent_node.color
parent_node.color, brother_node.left_child.color = 'black', 'black'
self.right_rotate(parent_node)
break
# 如果兄弟节点有右节点，此右节点一定是红节点(递归处理时，如果兄弟节点的右子节点为红节点)
else:
brother_node.color, brother_node.right_child.color = 'red', 'black'
self.left_rotate(brother_node)
# 如果兄弟节点是红节点
elif brother_node.color is 'red':
self.change_color(parent_node)
self.change_color(brother_node)
self.right_rotate(parent_node)
if node is node.parent.left_child:
node.parent.left_child = None
else:
node.parent.right_child = None
node.parent = None
def _rb_delete_one_child(self, node):
"""红黑树删除有一个子节点的节点"""
if node.left_child:
self.change_color(node.left_child)
if node.parent and node.parent.left_child == node:
node.left_child.parent, node.parent.left_child = node.parent, node.left_child
elif node.parent and node.parent.right_child == node:
node.left_child.parent, node.parent.right_child = node.parent, node.left_child
else:
self.root = node.left_child
node.left_child.parent, node.left_child = None, None
elif node.right_child:
self.change_color(node.right_child)
if node.parent and node.parent.left_child == node:
node.right_child.parent, node.parent.left_child = node.parent, node.right_child
elif node.parent and node.parent.right_child == node:
node.right_child.parent, node.parent.right_child = node.parent, node.right_child
else:
self.root = node.right_child
node.right_child.parent, node.right_child = None, None
node.parent = None
def rb_check(self):
"""检查红黑树是否满足5条特性"""
if self.is_empty():
print("空树")
return
queue = list()
queue.insert(0, self.root)
height = 0
while len(queue):
node = queue.pop()
if node.color is not "red" and node.color is not "black":
raise Exception("节点{}不满足特性1".format(node.data))
if node is self.root and node.color is not "black":
raise Exception("节点{}不满足特性2".format(node.data))
if node.color is "red" and (node.left_child and node.left_child.color is "red" or
node.right_child and node.right_child.color is "red"):
raise Exception("节点{}不满足特性4".format(node.data))
if node.left_child is None and node.right_child is None:
path = 0
cur = node
while cur:
if cur.color is "black":
path += 1
cur = cur.parent
if height and path != height:
raise Exception("节点{}不满足特性5".format(node.data))
else:
height = path
if node.left_child is not None:
queue.insert(0, node.left_child)
if node.right_child is not None:
queue.insert(0, node.right_child)
print("满足红黑树的5条特性,叶子节点到根节点的非空黑节点个数为{}".format(height))
def search(self, root, data):
"""二叉搜索树的查询操作"""
if root is None:
return
if root.data == data:
return root
elif data < root.data:
return self.search(root.left_child, data)
elif data > root.data:
return self.search(root.right_child, data)
def get_min(self, root):
"""查找二叉搜索树值最小的节点"""
if self.is_empty():
return
return self.get_min(root.left_child) if root.left_child else root
def show_tree(self):
if self.is_empty():
print('空二叉树')
return
print('-' * 20)
print("\033[31m{}\033[0m".format(str(self.root.data))) if self.root.color is 'red' else print(str(self.root.data))
self.__print_tree(self.__root)
print('-' * 20)
def __print_tree(self, node, prefix=None):
if prefix is None:
prefix, prefix_left_child = '', ''
else:
prefix = prefix.replace(self.prefix_branch, self.prefix_trunk).replace(self.prefix_leaf, self.prefix_empty)
prefix_left_child = prefix.replace(self.prefix_leaf, self.prefix_empty)
if self.has_child(node):
if node.right_child is not None:
if node.right_child.color is 'red':
print(prefix + self.prefix_branch + self.prefix_right + "\033[31m{}\033[0m".format(str(node.right_child.data)))
else:
print(prefix + self.prefix_branch + self.prefix_right + str(node.right_child.data))
if self.has_child(node.right_child):
self.__print_tree(node.right_child, prefix + self.prefix_branch + ' ')
else:
print(prefix + self.prefix_branch + self.prefix_right)
if node.left_child is not None:
if node.left_child.color is 'red':
print(prefix + self.prefix_leaf + self.prefix_left + "\033[31m{}\033[0m".format(str(node.left_child.data)))
else:
print(prefix + self.prefix_leaf + self.prefix_left + str(node.left_child.data))
if self.has_child(node.left_child):
prefix_left_child += ' '
self.__print_tree(node.left_child, self.prefix_leaf + prefix_left_child)
else:
print(prefix + self.prefix_leaf + self.prefix_left)
def has_child(self, node):
return node.left_child is not None or node.right_child is not None
if __name__ == '__main__':
tree = RBBinaryTree()
# data = [50, 77, 55, 29, 10, 30, 66, 18, 80, 51, 90]
# for i in data:
# tree.rb_insert(i)
# # tree.show_tree()
#
# tree.rb_delete(66)
# tree.show_tree()
data = range(1000)
for i in data:
tree.rb_insert(i)
tree.rb_check()
tree.rb_delete(66)
print("--- after delete ---")
tree.rb_check()
