红黑树分析

红黑树性质

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

注意一个常见的误区是 红黑树必须一层红,一层黑。一个黑节点下面两个黑节点也允许. 黑 黑 黑 这种情况也可以存在

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

红黑树的插入

红黑树可以看成3阶段b树，也就是说其黑色节点可以提到其父节点的两边，在逻辑上三个节点看成一个b树节点 红黑树为了保持以上五条性质才能保证其nlogn的查找 红黑树被插入节点初始颜色是红色

1.插入情况1 "B树节点未满" 也就是说存在黑色非叶节点(有意义的节点)两个子节点至少有一个不存在的情况。那么直接插入即可。此时红黑树不需要调整 某子树: ...
黑(1) /
nil(2) nil(3) 1的左右子节点是空的，所以可以任意插入

2.插入情况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处 。这里说拼有些抽象 1.先处理v和u->right的关系,u->right 处理后结束v的右子树了,现在v就是掌管了原来u的右子树的节点了 2.用TRANSPLANT 处理v和u的父节点的关系(链接) 3.再单独处理u的左子树和v的关系(链接) 4.具体编程还需要处理被删除节点u的内存等操作

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

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