7.3.3.1 红黑树的插入

教材导航 · 第7章

原书定位

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

按 BST 找位置,新结点先染红。父黑则完成;成为根则染黑;父红时考察叔结点:

  • 叔红:父、叔染黑,祖父染红,把祖父当当前结点继续向上处理。
  • 叔黑(含 NIL):折线形先对父旋转化为直线形,再对祖父旋转并交换父、祖父颜色;左右情形镜像处理。

新结点染红不增加路径黑结点数,主要要消除连续红。旋转前后要保持中序顺序;变色向上可能最终使根重新染黑。

红黑树黑叔情形的旋转与变色

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

红叔情形的变色与向上传递

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

红黑树插入过程

红黑树插入过程,原书P293。

对应练习

7.3 节习题与逐题解析

关联知识

原书对照

展开原书对照截图

原书对照,原书P292,PDF第304页

原书对照,原书P293,PDF第305页