一、性质
红黑树是一颗二叉搜索树，在咩个节点上增加了一个存储位来表示节点的颜色，可以是RED或BLACK。
红黑树确保没有一条路径会比其他路径长出2倍，因而近似于平衡的。
树中每个节点包含5个属性:color、key、left、right和p。如果一个节点没有子节点或父节点，则该节点相应指针属性的值为NIL，我们可以把这些NIL视为指向二叉搜索树的叶结点的指针，而把关键字的节点视为树的内部节点。
特性：
-
每个节点或是红色的，或是黑色的。
-
根节点是黑色的。
-
每个叶结点（NIL）是黑色的。
红黑树叶结点
-
如果一个节点是红色的，则它的两个子节点都是黑色的。（也就是说不存在两个连续的红色节点）
-
对每个节点，从该节点到其所有后代叶结点的简单路径上，均包含相同数目的黑色节点。
从五大特征直观上总结出来几个点：
1 对每个红色节点，子节点只有两种情况：要么都没有，要么都是黑色的。（不然会违反特征四）
2 对黑色节点，如果只有一个子节点，那么这个子节点，必定是红色节点。（不然会违反特征五）
3 假设从根节点到叶子节点中，黑色节点的个数是h, 那么树的高度H范围 h<= H <= 2H（特征四五决定）。
二、红黑树节点代码设计
class RBNnode:
def __init__(self, val, color="R"):
self.val = val
self.color = color
self.left = None
self.right = None
self.parent = None
def is_black_node(self):
return self.color == "B"
def set_black_node(self):
self.color = "B"
def set_red_node(self):
self.color = "R"
def print(self):
if self.left:
self.left.print()
print(self.val)
if self.right:
self.right.print()
三、红黑树的基本操作算法
1. 左旋&右旋
红黑树_左旋
红黑树_右旋
class RBTree:
'''
红黑树 五大特征
性质一：节点是红色或者是黑色；
性质二：根节点是黑色；
性质三：每个叶节点（NIL或空节点）是黑色；
性质四：每个红色节点的两个子节点都是黑色的（也就是说不存在两个连续的红色节点）；
性质五：从任一节点到其没个叶节点的所有路径都包含相同数目的黑色节点
'''
def __init__(self):
self.root = None
def left_rotate(self, node):
print("left rotate", node.val)
'''
* 左旋示意图：对节点x进行左旋
* parent parent
* / /
* node right
* / \ / \
* ln right -----> node ry
* / \ / \
* ly ry ln ly
* 左旋做了三件事：
* 1. 将right的左子节点ly赋给node的右子节点,并将node赋给right左子节点ly的父节点(ly非空时)
* 2. 将right的左子节点设为node，将node的父节点设为right
* 3. 将node的父节点parent(非空时)赋给right的父节点，同时更新parent的子节点为right(左或右)
:param node: 要左旋的节点
:return:
'''
parent = node.parent
right = node.right
# 把右子节点的左子节点，赋给右节点
node.right = right.left
if node.right:
node.right.parent = node
# 把node变成基右子节点的左子节点
right.left = node
node.parent = right
# 右子节点的父节点更新为原来节点的父节点
right.parent = parent
if not parent:
self.root = right
else:
if parent.left == node:
parent.left = right
else:
parent.right = right
def right_rotate(self, node):
print("right rotate", node.val)
'''
* 左旋示意图：对节点y进行右旋
* parent parent
* / /
* node left
* / \ / \
* left ry -----> ln node
* / \ / \
* ln rn rn ry
* 右旋做了三件事：
* 1. 将left的右子节点rn赋给node的左子节点,并将node赋给rn右子节点的父节点(left右子节点非空时)
* 2. 将left的右子节点设为node，将node的父节点设为left
* 3. 将node的父节点parent(非空时)赋给left的父节点，同时更新parent的子节点为left(左或右)
:param node:
:return:
'''
parent = node.parent
left = node.left
# 将left的左子节点赋给node的左子节点
if node.left:
node.left = left.right
node.left.parent = node
# left的右子节点为node，node的父子节点为left
left.right = node
node.parent = left
# 将left的父子节点更新为parent
left.parent = parent
if not parent:
self.root = left
else:
if parent.left == node:
parent.left = left
else:
parent.right = left
2. 插入操作
如果插入的是黑色节点时，则每次插入都会违返性质5, 都需要重新调整树,所以 插入时，每次都认为只插入红色节点。这样调整的次数就会减少很多。 倡但是还是有要调整的情况:
-
如果插入的是根节点，则直接把点变成黑色（性质二）,示例中插入第一个节点5的情况
插入根节点
-
如果插入的节点的父节点是黑色节点，则不调整颜色。
插入节点父节点为黑色节点情况
-
如果插入节点的父节点的红色节点（违反性质四），且父节点的兄弟节点为红色节点。
1) 把父节点及其兄弟节点变成黑色，把组父节点变成红色（使其不违反性质五）。 示例中 插入点3和点18就属于这种情况：
2) 再检查祖父节点是否违反红黑树的性质（一或四）
插入节点父节点为红色节点情况
-
如果插入节点的父节点的红色节点（违反性质四），且父节点的兄弟节点为黑色节点。 并且插入节点，父节点，及祖父节点同则。 即node = node.parent.left && node.parent = node.parent.parent.left(同左则), 或 node = node.parent.right && node.parent = node.parent.parent.right（同右则）
处理方法： 把父节点变成黑色节点，把祖父节点变成红色节点， 同时反向旋转祖父节点（同左则，右旋； 同右则左旋）
示例中，插入 节点12, 节点7就是此种变行。
插入节点12
插入节点7
-
如果插入节点的父节点的红色节点（违反性质四），且父节点的兄弟节点为黑色节点。 并且插入节点，父节点，及祖父节点同则。
处理方法：旋转父节点，使期变成同则（第4种情况）， 再根据情况4来处理。
示例中 插入节点6就属于这种情况。
插入节点6
3. 删除操作
两个概念：
前驱节点： 节点的左子树中， 最大值的节点。
后继节点： 节点的右子树中，最小值的节点。
示例中，把删除操作分成了三个步骤： -
获取要真正删除的叶子节点（把删除操作都归为删除叶子节点操作）
目的：把要删除的点，往叶子节点推。使删除操作变成删除叶子节点的操作。找到要删除节点的后继节点或前驱节点，如果存在，则替换掉当前节点。再以替换后的节点，的后续或前驱节点。替换掉，直到无后继或前驱节点。 -
对红黑树进行调调整，使删除节点后的树，不违反红黑树的性质。
-
真正的删除节点。
获取真正删除的节点操作 示例中删除16时为例做下说明
如图所示的变换中，把节点16,推到了叶子节点，使删除节点16时，不破坏二叉树的性质。
总共进行了两步变换： 16与17(后继节点）互换。 16与19（后续节点）互换 变成了后面图的样子
将问题由删除根节点16,变成了删除叶子节点16.
删除操作
def pre_delete_node(self, node):
'''
删除前检查，返回最终要删除的点
:param node:
:return:
'''
post_node = self.get_post_node(node)
if post_node:
node.val, post_node.val = post_node.val, node.val
return self.pre_delete_node(post_node)
pre_node = self.get_pre_node(node)
if pre_node:
pre_node.val, node.val = node.val, pre_node.val
return self.pre_delete_node(pre_node)
#没有前驱节点，也没有后续节点
return node
删除前调整红黑树
目的： 使删除节点后的树还是一棵红黑树
注： 这使用的删除示例图中将包含把删除节点往叶子节点推的过程。
1 ） 删除的节点是红色节点，可不需要调整直接删除 （如上图的16节点, 及删除节点3时）
删除节点为红色节点时
2 ） 删除的节点是根节点，直接删除
3 ）如果是黑色节点，兄弟节点是红色节点， 旋转父节点： 把你节点变成黑色，兄弟节点变黑色。 重新平衡。
删除节点操作
4 ）删除黑色节点，兄弟结点也是黑色节点， 且兄弟节点的要么没有子节点，要么所有子节点都是黑色节点。
- 1 直接将兄弟节点变成红色节点
- 2 如果父节点是红色节点，直接把父节点变成黑色节点（调整结束）。
-
3 如果父节点是黑色节点，再检查当前节点（递归检查）（示例中删除14节点，19 变红色后，再递归把6也变成红色）。
删除前检查
5 ）删除黑色节点，兄弟结点也是黑色节点， 兄弟节点的同则子节点（如果兄弟节点为左节点，则为史弟节点的左节点，右节点同理）为红色节点
- 1 变色： 兄弟同则子节点设置成黑色。 兄弟节点（黑色）和父节点（可能是红色，也可能是黑色）互换颜色
-
2 旋转父节点。
删除节点15
6 ）删除黑色节点，兄弟结点也是黑色节点， 兄弟节点的同则子节点 为黑色节点或无节点， 而兄弟节点 异则子节点为红色子节点
- 变色： 兄弟节点变成红黑， 兄弟节点的异则子节点变成黑色。
- 旋转兄弟节点： 可使节点变成 情况5。
删除节点18
代码：
def check_delete_node(self, node):
'''
检查删除节点node
:param node:
:return:
'''
if self.root == node or node.is_red_node():
return
node_is_left = node.parent.left == node
brother = node.parent.right if node_is_left else node.parent.left
#brother 必不为空
if brother.is_red_node():
# 如果是黑色节点，兄弟节点是红色节点， 旋转父节点： 把你节点变成黑色，兄弟节点变黑色。 重新平衡
if node_is_left:
self.left_rotate(node.parent)
else:
self.right_rotate(node.parent)
node.parent.set_red_node()
brother.set_black_node()
print("check node delete more ")
#再重新检查当前节点
self.check_delete_node(node)
return
all_none = not brother.left and not brother.right
all_black = brother.left and brother.right and brother.left.is_black_node() and brother.right.is_black_node()
if all_none or all_black:
brother.set_red_node()
if node.parent.is_red_node():
node.parent.set_black_node()
return
self.check_delete_node(node.parent)
return
#检查兄弟节点的同则子节点存丰并且是是红色节点
brother_same_right_red = node_is_left and brother.right and brother.right.is_red_node()
brother_same_left_red = not node_is_left and brother.left and brother.left.is_red_node()
if brother_same_right_red or brother_same_left_red:
if node.parent.is_red_node():
brother.set_red_node()
else:
brother.set_black_node()
node.parent.set_black_node()
if brother_same_right_red:
brother.right.set_black_node()
self.left_rotate(node.parent)
else:
brother.left.set_black_node()
self.right_rotate(node.parent)
return
# 检查兄弟节点的异则子节点存丰并且是是红色节点
brother_diff_right_red = not node_is_left and brother.right and brother.right.is_red_node()
brother_diff_left_red = node_is_left and brother.left and brother.left.is_red_node()
if brother_diff_right_red or brother_diff_left_red:
brother.set_red_node()
if brother_diff_right_red:
brother.right.set_black_node()
self.left_rotate(brother)
else:
brother.left.set_black_node()
self.right_rotate(brother)
self.check_delete_node(node)
return
网友评论