7.3.3.1 红黑树的插入
原书定位
印刷页P292起,对应PDF第304页。下文为目视整理的知识提要;完整内容见原书对照。
按 BST 找位置,新结点先染红。父黑则完成;成为根则染黑;父红时考察叔结点:
- 叔红:父、叔染黑,祖父染红,把祖父当当前结点继续向上处理。
- 叔黑(含 NIL):折线形先对父旋转化为直线形,再对祖父旋转并交换父、祖父颜色;左右情形镜像处理。
新结点染红不增加路径黑结点数,主要要消除连续红。旋转前后要保持中序顺序;变色向上可能最终使根重新染黑。

红黑树黑叔情形的旋转与变色,原书P292。

红叔情形的变色与向上传递,原书P293。

红黑树插入过程,原书P293。
对应练习
关联知识
原书对照
展开原书对照截图

