红黑树

234树

红黑树一种高效的自平衡二叉搜索树,特性为

• 左子树上的所有节点均值<=父节点的值
• 佑子树上的所有节点的均值>=父节点的值
• 左右子树也分别为二叉搜索树

但普通的二叉搜索树有一个致命的缺点

在最坏情况下的时间复杂度几乎达到了线性查找

红黑树的前身为234树也叫4阶b树

插入时

如果当前节点超过3了,就会发生节点上溢(删除时会发生下溢)

性质

1. 节点是红色或者黑色
2. 根节点是黑色
3. 叶子节点(最底部不存储数据的节点都为黑色,都为空)
4. 红色节点的父节点and子节点都为黑色(不存在俩个连续的红色节点)
5. 从任一节点到叶子节点的所有路径都包含相同数量的黑色节点

红黑树和234树等价

红黑树的黑色节点个数==234树的节点数

234树的每一个节点中:

黑色节点必为父节点,红色节点为子节点(黑色中间,红色俩边)

把红黑树中子节点上移到父节点同一高度上,就会变成这样

操作

插入

如果插入的是根节点,则为黑色

其余情况插入的节点最开始一定为红色(如果是插入红色节点,只有一种冲突状况,就是可能出现连续俩个红色节点,这时候只需要旋转和变色进行调整)

红黑树的插入操作分为12种情况

其中插入节点的父节点为黑色的四种情况,是可以直接插入不做调整的

父节点为黑

父节点为红色

右边四种情况

分别为RL,RR,LL,LR

比如当前插入的情况是LL,在234树中可以直接插入,但是红黑树不允许连续的俩个红色的节点

那么12这个节点就需要变色

光变色肯定是不行的,

这时候就需要进行一个右旋转变成了这个样子

同理RR的话需要左旋

那么如果是RL的情况呢,最终我们想要的样子是这样的

首先父节点要进行一次右旋,8->10->11->12

然后祖父节点进行一次左旋

那么同理LR的情况,父节点进行一次左旋,祖父节点进行一次右旋

总结,LL/RR要染色后进行一次单旋,RL和LR变色后要进行一次双旋

注意,这四种情况都是没有叔父节点(叔父节点就是父节点的兄弟节点2和6就是兄弟节点)比如2和6

左边四种情况

比如插入1,那么按照b树的思想需要进行一个节点上溢,这时候就会发现只是把树的高度提上去了,在红黑树的架构下其实没有任何变化

插入这个1节点的时候首先把父节点和叔父节点2,6改为黑色,然后把祖父节点4,改为红色,当做新节点插入上一层的节点去,比如这里就应该把8给改成黑色的

写代码的时候,这四种情况是要在代码里分别判断的,但是归类的时候,可以放到一起归类

总结

1. 插入节点的父节点为黑色(四种)直接插入不作调整
2. 叔父节点不是红色(4种),旋转+变色
3. 叔父节点是红色(4种上溢的情况)需要变色

删除

删除操作分为俩大类

• 红色节点(直接)删除
• 黑色节点删除

b树种的删除操作,对于非叶子节点是转换为前驱/后继节点的删除

比如我们要删除8

8的前驱节点为6,后继节点为10

将8和前驱节点的数据进行交换,交换完成后就可以删除8

因为红黑树的性质5,从任意节点到叶子节点的所有路径都包含相同的黑色节点

而黑色节点删除就存在三种形式

1. 有俩个红色节点的黑色节点(对应234树的4节点)
   (不做考虑,因为会转换成对子节点的删除)
2. 有一个红色节点的黑色节点(对应234树的3节点)
   用唯一的红色子节点来替代被删除的节点
3. 黑色叶子节点(对应234树的2节点)

第二种删除

,比如现在要删除节点10

第一步,让10和父节点断开连接,然后父节点和12进行连接,删除掉节点10,最后对12进行染色(替代,删除,把替代节点染为黑色)

第三种删除

分为三种情况

1. 删除节点为根节点,直接删除
2. 删除节点的的兄弟节点是黑色
3. 删除节点的兄弟节点为红色(转变为黑色处理)

2删除的兄弟节点为黑色

先讲第二种情况删除节点的的兄弟节点是黑色

又分为俩种情况

1. 兄弟节点有红色子节点(借用兄弟节点修复)
2. 兄弟节点没有红色子节点

现在来看删除黑色叶子节点时,兄弟节点有红色子节点的情况

比如要删除36那么他的兄弟节点就是20

这又被分为三种情况

• 兄弟节点有一个红色左儿子节点
• 兄弟节点有一个右儿子红色节点
• 兄弟节点有俩个子节点

首先来看这个情况,我们要删除36这个节点

删掉之后,就出现了下溢的情况 , 因为8,15,25是一个4节点

我们需要把25旋转到上面,25旋转到右面,进行一个右旋

把20染为红色,俩个子节点染为黑色

来看兄弟节点的红色子节点在右边的时候,需要的操作

总的思想其实就是取三个节点的中间值最为父节点

先对节点20,也就是删除节点的兄弟节点进行一次左旋 (25->22->20)然后对父节点进行一次右旋,最后把子节点进行染色

如果删除的元素的兄弟节点,有俩个子节点,可以用以上俩个任意一个方式进行修复,但是选用LL的方式会更好修复,只需要进行一次旋转就可以修复

现在来看删除黑色叶子节点时,兄弟节点没有红色子节点的情况

这里有俩种情况,

• 父节点是红色节点
• 父节点是黑色节点

先来说第一种情况,比如要删除36,在b树的思想下需要进行节点下溢,但是作为红黑树不作为b树来看确实不需要进行改动

其实只需要把25改成黑色,20改为红色就可以了

第二种情况

直接染色是不够的

这样就不符合红黑树的特性了

写代码时我们需要对父节点调用afterRemove方法(当做他已经删除了)

最后变成这个样子

总结:当黑色叶子节点删除,删除的学弟节点为黑色,且学弟节点没有红色子节点(父节点向下合并)

兄弟节点染红,父节点染黑

如果父节点为黑色:把父节点当做已被删除的节点处理,进行递归

总结

• 红色节点可以直接删除

• 黑色节点的删除

  • 有一个红色子节点的黑色节点(红色子节点代替删除节点)

  • 黑色子节点(下溢)

    • 删除节点为根节点,直接删除

    • 删除节点的兄弟节点为黑色

      • 兄弟节点有红色子节点(借用兄弟子节点修复)
      • 兄弟节点没有红色子节点(父节点想下合并/红与黑)
  • 删除节点的兄弟节点为红色(转变为黑色处理)