上一篇写了234树对比红黑树,和红黑树某些情况需要调整的原因,这篇就只写红黑树的添加和删除

红黑树

性质

1. 每个节点要么红色要么黑色
2. 根节点是黑色
3. 每个叶节点是黑色的,这里叶子节点指空的节点,和二叉树的叶子节点不同
4. 每个红色节点的两个子节点都是黑色
5. 每个节点到它的每个叶子节点的所有路径都包含相同数目的黑色节点

添加

所有添加的节点默认都是红色

1. 空节点
2. 父节点为黑色
3. 父节点为红色

1 空节点

所有节点默认为红色,添加后5为根节点,违反了性质2"根节点是黑色" ,只需要将红变黑即可

2 父节点为黑色

2.1 父节点为黑色,直接添加,小于父添加左边,大于等于添加右边

3 父节点为红色

情况1 祖孙三代在一条线

直接进行旋转变色即可

而这里面还有一种情况

我们需要先将5和6进行旋转,让它变成上面的情况,然后按照上面的操作进行添加

情况2有叔叔节点

情况2.1叔叔节点为红色

如果10节点为跟节点,那么再变黑,如果10节点变红与上面发生冲突,那么把10节点作为新添加的节点,再继续执行调整

删除

情况

1. 没有子节点
2. 有一个子节点
3. 有两个子节点

先说有两个子节点的情况,需要寻找到它的前驱或后继节点来替代,然后删除前驱或后继节点,也就是将情况转换为1或2

关于前驱或后继节点看上篇文章

没有子节点

1.1 节点为红色

没有子节点且当前节点为红色直接删除

1.2 节点为黑色

1.2.1兄弟节点为红色

1.2.2兄弟节点为黑色且有一个子节点

1.2.3兄弟节点为黑色且有两个子节点

1.2.4兄弟节点为黑色,没有子节点

1.2.1兄弟节点为红色

需要将兄弟节点进行旋转变色,为什么兄弟节点为红色需要旋转变色原因可以看上一篇博客,将情况变为234

1.2.2兄弟节点为黑色且有一个子节点

在这里面还有一种 小情况,兄弟节点的子节点如果离自己近需要先进行旋转变色,将情况变成上面的再进行操作

1.2.3兄弟节点为黑色且有两个子节点

有两种解决方法

1 先删除5同时将15和20进行右旋变色,然后10和15进行左旋变色,而20和15就是上面的情况,旋转完后15两个子节点必须是黑色,如果15节点于红黑树性质冲突,那么在根据情况调整

2 直接删除5,然后10和20进行左旋,一般都用这个方法,减少一次旋转

1.2.4兄弟节点为黑色,没有子节点

父节点为红色

删除5,然后兄弟节点变为红色来维持父节点的左右黑色平衡,如果父节点为红色,直接变黑即可,父节点变黑是维护爷爷节点的左右黑色平衡

如果父节点为黑色

同样也是将兄弟节点变红,然后把父节点向上递归处理

删除一个黑色节点,然后改一个红色节点,这个父节点的黑色是平衡了,如果上面还有节点呢,那么黑色节点还是不平衡,

这时就需要递归进行操作,直到出现红色父节点将其变为黑色或到达根节点为止

有子节点

1. 删除节点为红色
2. 删除节点为黑色

1 删除节点为红色

直接删除

2 删除节点为黑色

只会有一种情况,有一个红色的左孩子或右孩子,如果有两个孩子那么就会去删除前驱或后置而不是当前节点,

也不可能出现一个孩子为黑色一个孩子为红色,更不可能出现只有一个黑色孩子,根据红黑树性质5就明白了

那么来看只有一个红色子节点情况

先将10和它的红色子节点20进行旋转变色,然后直接删除,5节点可以是红也可以是黑

练习

添加

属于有父节点和叔叔节点,且都为红色,根据添加的3.2.1父节点和叔叔节点都为红色进行变色处理

完成后发现因为变色6节点和4节点出现了连续两个红色,需要继续调整,把6当做新添加的节点,发现属于情况3.1祖孙三代在一条线,将2和4节点进行旋转变色

删除

我们删除4节点,这里4就是根节点

首先判断是那种情况,有两个子节点那就是寻找前驱或后继进行替换,我们这里使用前驱节点,也就是3

首先判断3节点的情况,没有子节点,兄弟节点也没有节点,那就是删除情况的1.2.4兄弟节点为黑色,没有子节点

首先将值覆盖掉,然后删除3节点,将3节点的兄弟节点变色为红色

然后发现父节点为黑色,不能进行变色来平衡,那么把2节点当做需要删除的节点(并不真正删除)继续调整

发现兄弟节点为黑色且有两个子节点,属于删除情况的1.2.3,只需要进行旋转即可

删除节点6

有两个节点,寻找前驱或后继,这次我们使用后继节点,也就是8,还是首先把值赋给6,然后进行删除

将8删除,兄弟节点变色,发现父节点为黑色,不能进行变色保持黑色平衡,那么只能向上递归

将9的兄弟节点变色为红色,如果这个6 (8)节点 如果还有父亲则继续递归操作,现在发现到根节点,调整完成

本文仅个人理解,如果有不对的地方欢迎评论指出或私信,谢谢٩(๑>◡<๑)۶

• 还没有人评论，欢迎说说您的想法！