7.3.3.2 红黑树的删除
原书定位
印刷页P294起,对应PDF第306页。下文为目视整理的知识提要;完整内容见原书对照。
先按 BST 将双孩子删除转为删前驱或后继,关注最终实际摘除结点的原颜色。删红叶直接完成;黑结点仅一个实际孩子时,该孩子必红,可接替并染黑;删黑叶需修复黑高缺失。
可用“额外一重黑”描述当前位置 的缺额;对其黑或红兄弟及侄结点分类:
- 兄弟红:交换兄弟与父颜色并旋转父,转为黑兄弟情形。
- 兄弟黑且远侄红:旋转父、重着色,消除缺额。
- 兄弟黑、近侄红而远侄黑:先旋转兄弟,转成远侄红。
- 兄弟黑且两侄黑:兄弟染红,把缺额上推父;父若红可染黑终止。
上述左右可镜像;上推可能重复 次。标准删除最多 3 次旋转,不能一概说插入和删除都最多 2 次。

单孩子结点的删除,原书P294。

红兄弟转为黑兄弟,原书P294。

黑兄弟且远侄为红的处理,原书P295。

近侄为红转为远侄为红,原书P295。

黑兄弟且双侄为黑的处理,原书P295。

红黑树逐步删除过程,原书P296。
对应练习
关联知识
原书对照
展开原书对照截图


