7.3.3.2 红黑树的删除

教材导航 · 第7章

原书定位

印刷页P294起,对应PDF第306页。下文为目视整理的知识提要;完整内容见原书对照。

先按 BST 将双孩子删除转为删前驱或后继,关注最终实际摘除结点的原颜色。删红叶直接完成;黑结点仅一个实际孩子时,该孩子必红,可接替并染黑;删黑叶需修复黑高缺失。

可用“额外一重黑”描述当前位置 xx 的缺额;对其黑或红兄弟及侄结点分类:

  • 兄弟红:交换兄弟与父颜色并旋转父,转为黑兄弟情形。
  • 兄弟黑且远侄红:旋转父、重着色,消除缺额。
  • 兄弟黑、近侄红而远侄黑:先旋转兄弟,转成远侄红。
  • 兄弟黑且两侄黑:兄弟染红,把缺额上推父;父若红可染黑终止。

上述左右可镜像;上推可能重复 O(log⁡n)O(\log n) 次。标准删除最多 3 次旋转,不能一概说插入和删除都最多 2 次。

单孩子结点的删除

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

红兄弟转为黑兄弟

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

黑兄弟且远侄为红的处理

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

近侄为红转为远侄为红

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

黑兄弟且双侄为黑的处理

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

红黑树逐步删除过程

红黑树逐步删除过程,原书P296。

对应练习

7.3 节习题与逐题解析

关联知识

原书对照

展开原书对照截图

原书对照,原书P294,PDF第306页

原书对照,原书P295,PDF第307页

原书对照,原书P296,PDF第308页