7.3.3 红黑树
原书定位
印刷页P291起,对应PDF第303页。下文为目视整理的知识提要;完整内容见原书对照。
红黑树是满足颜色约束的 BST:结点红或黑;根黑;空叶 NIL 黑;无相邻红结点;从任一结点到其各后代 NIL 的路径包含相同数量黑结点。
黑高按教材约定不含出发结点、含终点 NIL。 个实际内部结点的树高满足 ,查找、插入、删除最坏 。
红黑树放宽 AVL 的高度差约束,用旋转与变色维持对数高度。颜色是附加约束,关键字顺序仍按 BST;判定时必须同时检查顺序、根色、连续红与黑高。

红黑树与黑高,原书P291。
下级知识点
对应练习
关联知识
原书对照
展开原书对照截图

