红黑树
234树
红黑树一种高效的自平衡二叉搜索树,特性为
- 左子树上的所有节点均值<=父节点的值
- 佑子树上的所有节点的均值>=父节点的值
- 左右子树也分别为二叉搜索树
但普通的二叉搜索树有一个致命的缺点
在最坏情况下的时间复杂度几乎达到了线性查找
红黑树的前身为234树也叫4阶b树
插入时
如果当前节点超过3了,就会发生节点上溢(删除时会发生下溢)
性质
- 节点是红色或者黑色
- 根节点是黑色
- 叶子节点(最底部不存储数据的节点都为黑色,都为空)
- 红色节点的父节点and子节点都为黑色(不存在俩个连续的红色节点)
- 从任一节点到叶子节点的所有路径都包含相同数量的黑色节点
红黑树和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给改成黑色的
写代码的时候,这四种情况是要在代码里分别判断的,但是归类的时候,可以放到一起归类
总结
- 插入节点的父节点为黑色(四种)直接插入不作调整
- 叔父节点不是红色(4种),旋转+变色
- 叔父节点是红色(4种上溢的情况)需要变色
删除
删除操作分为俩大类
- 红色节点(直接)删除
- 黑色节点删除
b树种的删除操作,对于非叶子节点是转换为前驱/后继节点的删除
比如我们要删除8
8的前驱节点为6,后继节点为10
将8和前驱节点的数据进行交换,交换完成后就可以删除8
因为红黑树的性质5,从任意节点到叶子节点的所有路径都包含相同的黑色节点
而黑色节点删除就存在三种形式
- 有俩个红色节点的黑色节点(对应234树的4节点)
(不做考虑,因为会转换成对子节点的删除) - 有一个红色节点的黑色节点(对应234树的3节点)
用唯一的红色子节点来替代被删除的节点 - 黑色叶子节点(对应234树的2节点)
第二种删除
,比如现在要删除节点10
第一步,让10和父节点断开连接,然后父节点和12进行连接,删除掉节点10,最后对12进行染色(替代,删除,把替代节点染为黑色)
第三种删除
分为三种情况
- 删除节点为根节点,直接删除
- 删除节点的的兄弟节点是黑色
- 删除节点的兄弟节点为红色(转变为黑色处理)
2删除的兄弟节点为黑色
先讲第二种情况删除节点的的兄弟节点是黑色
又分为俩种情况
- 兄弟节点有红色子节点(借用兄弟节点修复)
- 兄弟节点没有红色子节点
现在来看删除黑色叶子节点时,兄弟节点有红色子节点的情况
比如要删除36那么他的兄弟节点就是20
这又被分为三种情况
- 兄弟节点有一个红色左儿子节点
- 兄弟节点有一个右儿子红色节点
- 兄弟节点有俩个子节点
首先来看这个情况,我们要删除36这个节点
删掉之后,就出现了下溢的情况 , 因为8,15,25是一个4节点
我们需要把25旋转到上面,25旋转到右面,进行一个右旋
把20染为红色,俩个子节点染为黑色
来看兄弟节点的红色子节点在右边的时候,需要的操作
总的思想其实就是取三个节点的中间值最为父节点
先对节点20,也就是删除节点的兄弟节点进行一次左旋 (25->22->20)然后对父节点进行一次右旋,最后把子节点进行染色
如果删除的元素的兄弟节点,有俩个子节点,可以用以上俩个任意一个方式进行修复,但是选用LL的方式会更好修复,只需要进行一次旋转就可以修复
现在来看删除黑色叶子节点时,兄弟节点没有红色子节点的情况
这里有俩种情况,
- 父节点是红色节点
- 父节点是黑色节点
先来说第一种情况,比如要删除36,在b树的思想下需要进行节点下溢,但是作为红黑树不作为b树来看确实不需要进行改动
其实只需要把25改成黑色,20改为红色就可以了
第二种情况
直接染色是不够的
这样就不符合红黑树的特性了
写代码时我们需要对父节点调用afterRemove方法(当做他已经删除了)
最后变成这个样子
总结:当黑色叶子节点删除,删除的学弟节点为黑色,且学弟节点没有红色子节点(父节点向下合并)
兄弟节点染红,父节点染黑
如果父节点为黑色:把父节点当做已被删除的节点处理,进行递归
总结
- 红色节点可以直接删除
黑色节点的删除
- 有一个红色子节点的黑色节点(红色子节点代替删除节点)
黑色子节点(下溢)
- 删除节点为根节点,直接删除
删除节点的兄弟节点为黑色
- 兄弟节点有红色子节点(借用兄弟子节点修复)
- 兄弟节点没有红色子节点(父节点想下合并/红与黑)
- 删除节点的兄弟节点为红色(转变为黑色处理)