• 欢迎访问最初的梦想
  • Github https://github.com/anthonyzhai

红黑树

编程 AnthonyZhai 2个月前 (08-10) 83次浏览 已收录 0个评论

一种自平衡二叉查找树,在进行插入和删除时通过特定操作保持二叉查找树的平衡。

1 原因

二叉查找树支持的集合操作:
查找,上一元素,下一元素,最小元,最大元,插入,删除。其时间 $ O(h),h$ 最坏为 $n$,即链表性能。
红黑树的时间为 $O(logn)$

2 特性

enum RBNodeColor{RED,BLACK};
template<class T>
struct RBNode{
    RBNodeColor color;
    struct T key;
    RBNode *left;
    RBNode *right;
    RBNode *parent;
}

其中叶子结点最好用哑结点leaf替换空指针NULL。

1)每个结点非红即黑;
2)根和叶子都为黑色;
3)红色结点的孩子都为黑色;
4)每个结点到叶子结点都有相同数量的黑色结点;
红黑树
注意:根的父亲结点也是哑结点leaf。

黑阶(black-height):该结点(不含)到叶子结点路径上的黑色结点数量。

证明黑阶
引理:$n$个结点的红黑树,高度至多为$2log(n+1)$。
所以,以$x$为根结点的子树至少有$2^{b(x)} -1$个内部结点,其中$b(x)$为任意结点$x$的黑阶。
使用归纳法证明上述引理:
红黑树
红黑树
由此可知,红黑树的各项结合操作时间为$O(logn)$

那么问题来了,如何实现红黑树的操作?

3 旋转

以左旋为例,原始红黑树为:
(注意此时y应该有左孩子)
红黑树
1)将y的左孩子作为x的右孩子

y = x->right;
x->right = y->left;
y->left->parent = x;

红黑树
2)将x作为y的左孩子

y->parent = x->parent;
if(x->parent == leaf)
    root = y;  //更换root结点
else if(x->parent->left == x)
    x->parent->left = y;
else
    x->parent->right = y;
y->left = x;
x -> parent = y;

红黑树

4 插入

二叉查找树在失败处插入,但红黑树与之不同之处在于:
1)引入哑结点leaf;
2)新插入结点也指向leaf;
3)新结点为红;
4)要进行红黑颜色调整。

插入时可能违背红黑树的如下特性:
1)根必须为黑;
2)红色结点的孩子都为黑。

4.1 循环不变式

1)当前结点z为红色;
2)若z->parent为根,则z->parent必为黑色;(停止)
3)否则,违背红黑树特性,二者只能违背其一:
    a. z为根;(直接变为黑色即可)
    b. z->parent不为根且为红。(调整结点,难点所在

4.2 实现思路

z有无parent:
1)无,z为根;
2)有,它是否为根?:是,否。

主要处理:当前结点z为红色且其parent也为红色。(为何讨论父亲,因为其开始时是叶子

红黑树
红黑树

5 删除

红黑树
注意:动态记录y,y是将要取代z位置的结点。
1)如果待删除元素z是当前子树中的最小元(只有右子树)或者最大元(只有左子树),则直接删除;
2)如果待删除元素z既有左子树也有右子树,则在其右子树中寻找最小值y,将y移至z的原位置,保存y的原有颜色,然后将y的颜色设置为z的颜色。

问题1:为什么需要保存y的原有颜色?
答:若y的原有颜色为红色,则不影响黑阶;若为黑色,则黑阶可能变化,因此需要调整。

问题2:如何调整?
答:调整x,移至y原有位置。

那么,y为黑色有三种情况:
1)y是根,x为红色,则x去替代根,令x为黑色满足红黑树特性2
2)x和调整后x->parent(即y的原有父亲)均为红色,则令x为黑色即可,同时可以保证黑阶
3)x为黑色,没有办法对x改色以恢复y位置的黑阶,只能做调整。

其中,主要处理的是第3种情况:x不为根且x为黑色,需要不断调整

处理原则:
不要改动x为根的子树,想办法在x到根的向上路径中加一个黑结点,恢复黑阶即可。否则,向下扩展很麻烦。

循环终止条件:x为红色,最终单独改色即可。
红黑树
红黑树
红黑树

6 拓展

AVL树
2-3树
B树
AA树(改进版红黑树),便于代码实现
树堆
LEDA(MPII,德国,马克斯普朗克计算机科学研究所)
伸展树
跳跃表

7 参考资料

1、30张图带你彻底理解红黑树


最初的梦想 , 版权所有丨如未注明 , 均为原创丨本网站采用BY-NC-SA协议进行授权
转载请注明原文链接:红黑树
喜欢 (0)
发表我的评论
取消评论

表情 贴图 加粗 删除线 居中 斜体 签到

Hi,您需要填写昵称和邮箱!

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址