7.3.3 红黑树

教材导航 · 第7章

原书定位

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

红黑树是满足颜色约束的 BST:结点红或黑;根黑;空叶 NIL 黑;无相邻红结点;从任一结点到其各后代 NIL 的路径包含相同数量黑结点。

黑高按教材约定不含出发结点、含终点 NIL。nn 个实际内部结点的树高满足 h≤2log⁡2(n+1)h\le2\log_2(n+1),查找、插入、删除最坏 O(log⁡n)O(\log n)。

红黑树放宽 AVL 的高度差约束,用旋转与变色维持对数高度。颜色是附加约束,关键字顺序仍按 BST;判定时必须同时检查顺序、根色、连续红与黑高。

红黑树与黑高

红黑树与黑高,原书P291。

下级知识点

对应练习

7.3 节习题与逐题解析

关联知识

原书对照

展开原书对照截图

原书对照,原书P291,PDF第303页

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