redblack_tree

约 896 字大约 3 分钟

2025-03-20

红黑树分析

红黑树性质

1. 每个节点要么为黑色要么为红色2. 根节点是黑色3. 叶子节点均为黑色(nil)4. 如果一个节点是红色的那么它的叶子节点必须是黑色的5. 从一个节点到其子孙节点的路径中所包含的黑色节点相同(也就是所谓黑高相同)

注意

一个常见的误区是红黑树必须一层红，一层黑。一个黑节点下面两个黑节点也允许。

    黑
黑      黑

这种情况也可以存在。

               [黑]
              /    \
             /      \
            /        \
         [红]        [红]
        /    \      /    \
       /      \    /      \
    [黑]     [黑] [黑]    [黑]
   /    \   /   \/   \  /    \
  [nil][nil][nil]...
  //最底层无实际值的节点被称为叶子节点，其节点是黑色的

红黑树的插入

红黑树可以看成3阶b树，也就是说其黑色节点可以提到其父节点的两边，在逻辑上三个节点看成一个b树节点。

说明

红黑树为了保持以上五条性质才能保证其nlogn的查找。红黑树被插入节点初始颜色是红色。

插入情况1："B树节点未满"

也就是说存在黑色非叶节点(有意义的节点)两个子节点至少有一个不存在的情况。那么直接插入即可。此时红黑树不需要调整。

某子树:     ...
              \
              黑(1)
             /   \
           nil(2) nil(3)

1的左右子节点是空的，所以可以任意插入。

插入情况2：插入节点的父节点是红色

删除

定义一个转换操作 TRANSPLANT(T, u, v)，此函数的目的是用以v为根的子树替换以u为根的子树。在实际操作中，v通常为u的左右子树。（只处理u的父节点与v的关系，不处理被删除节点的子节点的关系）

先梳理一下搜索树的删除：

情况	描述	处理方式
case1	被删除节点u没有左右孩子	直接删除（u=null，或者delete u，或者不管不同语言不同处理方式）
case2	有左孩子无右孩子	直接把左子树拼到被删除节点u的位置（处理与父节点的关系）
case3	有右孩子无左孩子	直接把右子树拼到被删除节点u的位置
case4	同时有左右孩子	一般找中序遍历的后继节点（当然也可以找前驱）先把后继取出（把找到的后继的右子树拼到后继节点v的位置上，相当于v被删除了）把后继节点v拼到被删除节点u处

case4 详细步骤

先处理v和u->right的关系，u->right处理后结束了v的右子树，现在v就是掌管了原来u的右子树的节点了
用TRANSPLANT处理v和u的父节点的关系（链接）
再单独处理u的左子树和v的关系（链接）
具体编程还需要处理被删除节点u的内存等操作

后继节点特性

后继节点在右子树上且后继节点没有左子树，因为有左子树，那么后继节点肯定比当前找到的节点还小在其左子树里，当前找到的节点肯定不是被删除节点的后继。

现在来看下红黑树的删除，除了删除，还需要关联红黑树性质被满足。