【分享】红黑树的性质与实现思路

①红黑树(RBT)的Search,Insert,Delete操作的时间复杂度与平衡二叉树(AVL Tree)相同，皆是O(㏒2n)

②平衡二叉树适用以查为主，很少插入/删除的场景
红黑树适用于频繁插入、删除的场景，实用性更强
                ●图一

③红黑树相比普通二叉查找树相比，有以下要求
    ㈠每个结点或是红色或是黑色的
    ㈡根节点是黑色的
    ㈢叶节点（外部结点、NULL结点、失败结点）均是黑色的
          （注：此处的叶节点跟普通二叉树的叶子结点不同，需要注意，红黑树的叶节点只是一个空指针）
    ㈣不存在两个相邻的红结点（即红结点的父节点和孩子结点均为黑色）
    ㈤对每个结点，从该结点到任一叶结点的简单路径上，所含黑结点的数目相同
    这五个点简单来说就是：
            左根右，根叶黑，不红红，黑路同
             ●图二
      如图二，图二不满足㈣，它就不是一个红黑树

④结点的黑高：（即bh参数）指从某结点出发（不含该结点)到达任一空结点的路径上黑结点总数

例如：图一17号的bh值就为2

⑤红黑树的插入：
        先查找，确定插入位置(原理同二叉排序树)，插入新结点
       新结点是根--染为黑色
       新结点非根--染为红色（原因：保证黑路同这一特性）
       若插入新结点后依然满足红黑树定义，则插入结束
       若插入新结点后不满足红黑树定义，需要调整，使其重新满足红黑树定义
       如何调整:看新结点叔叔的脸色
      
       例：图一中27是新结点的话，27的叔叔就是27的父亲（25)的左兄弟（15)

        如果叔叔是黑色:旋转+染色
        ●LL型:右单旋，父换爷+染色
        ●RR型:左单旋，父换爷+染色
        ●LR型:左、右双旋，儿换爷+染色
        ●RL型:右、左双旋，儿换爷+染色
        注：LL,RR,LR,RL为新结点所处的位置，例27号的位置就为RR
        如果叔叔是红色：染色+变新
        ●叔父爷染色，爷变为新结点

叔叔为黑色，且为LL型时交换例子如下：
叔叔为红色，违反不红红时情况如图
叔叔为黑色，违反不红红，且为RR时情况如图
叔叔为黑色，违反不红红，且为LR时情况如图：
RL情况跟LR具体情况相同。

⑥从根节点到叶节点的最长路径不大于最短路径的2倍

⑦有n个内部节点的红黑树高度h≤2㏒2(n+1)

我是个凑数的。。。

回个帖子，下班咯~

路过 帮顶 嘿嘿

LZ帖子不给力，勉强给回复下吧

顶起顶起顶起

站位支持

看帖要回，回帖才健康，在踩踩，楼主辛苦了！

前排顶，很好！

顶起出售广告位