红黑树
2019-11-09 本文已影响0人
4c6ed2800025
1. 红黑树
1.1 红黑树的应用场景
红黑树需要具备的性质：
- 每一个节点或者为红色或者为黑色；
- 根节点是黑色的；
- 如果一个节点是红色的，那么其子节点必须是黑色的；
- 从一个节点到一个NULL指针的每一条路径必须包含相同数目的黑色节点。
1.2 红黑树的旋转
1.2.1 左旋
rbtree_rotate_left.jpg
1.2.2 右旋
rbtree_rotate_right.jpg
2. 红黑树的插入
红黑树插入节点
Case1：叔叔节点为红色，
Case2：叔叔节点为黑色，当前节点为父节点的左子树;
Case3：叔叔节点为黑色，当前节点为父节点的右子树；
2.2 循环的停止条件
在2.1小节讨论了红黑树插入节点的三种可能情况，颜色修正、左旋或者右旋之后事情并没有结束，而是将某个节点作为新的当前节点继续迭代。那么什么时候递归可能结束呢？当初学习红黑树很少看到有对这个问题进行讨论，下面我们探讨一下。不难发现，Case-3经过一次调整之后变为父节点的左子树即Case-2的情形。故我们仅需要对于前两种情况进行讨论。
对于Case-1，经过一次调整，祖父节点着色为黑色且作为新的当前节点；
image
rbtree_insert_0.jpg
对于Case-2，经过重新着色和旋转，P节点取代了原来G节点的位置且为黑色。无论原来G节点的父节点为黑色还是红色，都不会违反红黑树的定义。因此无需继续调整。在上述操作中，我们并没有改变当前节点，当前节点仍为S节点。
rbtree_insert_1.jpg
3. 红黑树的删除
// TODO
- 待删除的节点没有子节点，直接删除
2）待删除的节点只有一个子节点，则直接删除并将用子节点替代该节点
3）待删除节点有两个子节点，则使用该节点的后继节点代替，并将后继节点作为新的待删除节点，此时待删除节点
伪代码
RB-DELETE(T, z)
if left[z] = nil[T] or right[z] = nil[T]
then y ← z // 若“z的左孩子” 或 “z的右孩子”为空，则将“z”赋值给 “y”；
else y ← TREE-SUCCESSOR(z) // 否则，将“z的后继节点”赋值给 “y”。
if left[y] ≠ nil[T]
then x ← left[y] // 若“y的左孩子” 不为空，则将“y的左孩子” 赋值给 “x”；
else x ← right[y] // 否则，“y的右孩子” 赋值给 “x”。
p[x] ← p[y] // 将“y的父节点” 设置为 “x的父节点”
if p[y] = nil[T]
then root[T] ← x // 情况1：若“y的父节点” 为空，则设置“x” 为 “根节点”。
else if y = left[p[y]]
then left[p[y]] ← x // 情况2：若“y是它父节点的左孩子”，则设置“x” 为 “y的父节点的左孩子”
else right[p[y]] ← x // 情况3：若“y是它父节点的右孩子”，则设置“x” 为 “y的父节点的右孩子”
if y ≠ z
then key[z] ← key[y] // 若“y的值” 赋值给 “z”。注意：这里只拷贝z的值给y，而没有拷贝z的颜色！！！
copy y's satellite data into z
if color[y] = BLACK
then RB-DELETE-FIXUP(T, x) // 若“y为黑节点”，则调用
return y
rbtree_delete_flow2.png
4. 参考
1. https://www.cs.usfca.edu/~galles/visualization/RedBlack.html
rbtree_rotate_left.jpg
