红黑树的删除

红黑树的删除共有12种情况,

设要删除的节点为Z:

1.Z为根 且没有孩子 直接删除,将根赋空

2.Z为根 有一个红孩子(由于第4条性质一定为红孩子) 将孩子颜色->黑,当做新的根,删除节点

3.Z红色 直接删除,判断Z为父亲的左孩子或右孩子 将其赋空 (此节点一定没有孩子,因为2个孩子的已经处理过,一个红孩子(两个红色节点不能相邻),一个黑孩子(到终端节点黑节点数相同))

4.Z为黑色 有一个红孩子 将红孩子->黑,Z的父与Z的子相连,删除Z

5.Z为黑色 没有孩子(由于要删除的是黑节点,整个过程通俗的理解就是想要借一个黑节点,当侄子为红节点则可以变为黑节点,然后借来一个黑节点)

5.1 兄弟为红(初始状态)

兄是父右,兄->黑,父->红 ,以父为支点左旋 更新兄

红黑树的删除红黑树的删除红黑树的删除

兄是父左,兄->黑,父->红,以父为支点右旋,更新兄

5.2兄弟为黑(初始状态或调整状态)

5.2.1左侄黑,右侄黑

5.2.1.1父黑: 兄->红,以父亲为当前节点向上调整 ,更新兄 (由于少了一个黑节点,则向上借黑节点)

初始状态:

红黑树的删除红黑树的删除红黑树的删除

调整状态:

红黑树的删除红黑树的删除红黑树的删除

5.2.1.2父红:兄->红,父->黑,结束

初始状态:

红黑树的删除红黑树的删除红黑树的删除删除Z即可

调整中:

红黑树的删除红黑树的删除红黑树的删除

5.2.2左侄子红,右侄子黑

5.2.2.1兄为父右:左侄子->黑,兄->红,以兄弟为支点右旋 ,更新兄

初始状态:

红黑树的删除红黑树的删除红黑树的删除

调整中:

红黑树的删除红黑树的删除红黑树的删除

5.2.2.2兄为父右:兄弟->父亲的颜色,父->黑,左侄->黑,以父亲为节点右旋 结束

5.2.3右侄红(右侄子红,左侄子黑;或者右侄子红)

5.2.3.1兄为父右:兄弟->父亲的颜色,父->黑,右侄->黑,以父亲为支点左旋 结束

初始状态:

红黑树的删除红黑树的删除红黑树的删除删除Z即可

调整中:

红黑树的删除红黑树的删除红黑树的删除

5.2.3.2兄为父左:右侄->黑,兄->红,以兄弟为支点右旋 ,更新兄弟

通过上图,可以看出,5.2.2.1状态的下一个状态是5.2.3.1

5.2.3.2状态点的下一个状态是5.2.2.2

这篇博客是有史以来写的最认真的一个了,希望下次看的时候一下就能看懂,也希望能对看到这篇博客的人有一些帮助~

相关推荐