红黑树的定义和性质

7.3.3.1

通过路径计数实验，理解红黑树的黑高与平衡性质。

先按这个顺序学

如果你没看网课，从这里开始。每一步都对应课件和文案中的一段讲解。

第 1 步

为什么要发明红黑树？

1. 为什么发明BST 可能退化；AVL 查找稳但插入删除维护成本高；RBT 用颜色约束换取更低维护成本。
2. 可能怎么考定义性质最适合选择题；插入可能要求手绘；删除和代码不是本节重点。
3. 五条定义左根右、结点红黑、根叶黑、不红红、黑路同，判断时按这个顺序排除。
4. 黑高 bh从某结点出发到 NIL 叶子的黑结点数，是理解黑路同和高度性质的桥。
5. 两条性质最长路径不超过最短路径 2 倍；高度为 O(log n)，所以查找效率稳定。
6. 查找过程红黑树首先是 BST，查找仍然从根出发，左小右大，遇到 NIL 表示失败。

黑高路径实验室

逐条点亮从当前结点到 NIL 的路径，同时统计黑结点数量。

黑结点 红结点 当前选中 高亮路径
等待播放：从结点 13 出发，计算到每个 NIL 的黑结点数。 路径 1 / 6
陷阱 1：忘记不计入规则黑高计算不计入起点结点，也不计入红结点；NIL 是否计入要看教材口径，本页按王道课件口径用于路径对比。
陷阱 2：漏算 NIL 叶子红黑树里的叶结点通常是 NIL、NULL、外部结点、失败结点，不是最底层的关键字结点。
陷阱 3：混淆红色父子兄弟结点都为红色可以；父子连续红色才违反“不红红”。

从 0 到掌握：本页对应课件全内容

如果你完全没学过红黑树，按这个顺序走一遍：先读上方路线，再在实验台点选不同结点，最后做练习。你应该能掌握课件 7.3.3.1 的全部核心点。

会解释“为什么”能说出 RBT 相比 AVL 的取舍：不追求高度差绝对严格，而用颜色规则减少插入删除维护成本。
会判断“是不是”给一棵树，先查 BST 顺序，再查根叶黑和红红相邻，最后用黑高路径判断黑路同。
会推出“凭什么快”黑路同保证黑结点数量一致，不红红限制红结点连续出现，因此最长路径不超过最短路径 2 倍，高度仍为 O(log n)。

考研易错练习

若某结点到三条 NIL 路径的黑结点数分别是 2、2、3，最直接违反哪条定义？

选择题模式