红黑树为什么能保证最长路径不超过最短路径的两倍？
简化版
靠两条性质联手：性质 5（从任一节点到所有叶子的路径黑节点数相同，记为黑高 bh）保证「所有路径的黑色部分一样长」；性质 4（红节点不能相邻）保证「任何路径上红节点数不超过黑节点数」。所以最短路径是「全黑」的 bh 个节点，最长路径是「红黑交替」的至多 2·bh 个节点——最长 ≤ 2 倍最短，于是树高是 O(log n)。
详细版
设某条从根到叶子的路径黑高为 bh（黑色节点个数）。
- 最短路径：全部由黑色节点组成，长度 =
bh。 - 最长路径：黑红交替（红节点尽量多）。由于红节点不能相邻，每两个黑节点之间最多插一个红节点，所以红节点数 ≤ 黑节点数 =
bh，最长路径长度 ≤2·bh。
因此 最长路径 ≤ 2 × 最短路径。结合黑高，可推出：含 n 个内部节点的红黑树，高度 h ≤ 2·log₂(n+1)，即 O(log n)。这保证了查找、插入、删除都是 O(log n)。
完整版教学
一、两条性质的分工
红黑树能平衡，靠性质 4 和性质 5 各管一头：
- 性质 5（黑高相同） 管「下限」：它强制所有根到叶子的路径拥有相同数量的黑节点。这意味着没有哪条路径能只靠「少放黑节点」变得特别短或特别长——黑色骨架是对齐的。
- 性质 4（红不相邻） 管「上限」：它限制红节点的密度，红节点之间必须夹着黑节点，所以一条路径上红节点最多和黑节点一样多，路径长度被压在黑高的 2 倍以内。
两者合起来：所有路径的黑色部分等长，红色部分又不能太多，于是任意两条路径的长度比不会超过 2。这就是「大致平衡」的严谨含义。
二、从「路径比 ≤ 2」到「高度 O(log n)」
推导树高上界：
- 设红黑树黑高为
bh。由性质 4，红节点不相邻，所以树高h ≤ 2·bh。 - 一棵黑高为
bh的红黑树，其「只算黑节点」的子树至少是一棵高度bh的满二叉结构，所以内部节点数n ≥ 2^bh − 1，即bh ≤ log₂(n+1)。 - 结合 1、2：
h ≤ 2·bh ≤ 2·log₂(n+1)= O(log n)。
所以红黑树高度被牢牢压在 O(log n)，最坏情况下的查找也不会退化。
三、为什么允许「2 倍」而不是更严格
AVL 树要求高度差 ≤ 1，非常严格，代价是插入删除要频繁旋转维持。红黑树故意放松到「2 倍」这个较松的界，好处是：大多数插入删除只需变色、少量旋转就能修复，维护成本显著低于 AVL。它牺牲了一点点查找速度（高度常数略大），换来了更低的更新成本——这个权衡在增删频繁的通用场景里非常划算。
四、和 AVL 的高度对比
- AVL：高度 ≤ 1.44·log₂n，更矮、查找更快。
- 红黑树：高度 ≤ 2·log₂n，稍高、查找略慢。
数量级都是 O(log n)，差别只在常数。所以两者查找性能接近，主要差异在「维持平衡的开销」上。
五、这条性质的实际意义
「最长 ≤ 2 倍最短」意味着红黑树永远不会退化成链（那需要一条路径比另一条长很多，被性质禁止了）。所以哪怕输入是有序的、对抗性的，红黑树也能保证 O(log n)。这正是它能被用作 TreeMap、内核数据结构等对最坏情况有要求的场景的原因。
六、常见误区与追问
| 考点 | 正确口径 |
|---|---|
| 性质 1 | 红节点不能连续，限制最长路径红节点数量 |
| 性质 2 | 根到叶子的黑节点数相同，保证黑高一致 |
| 结论 | 最长路径不超过最短路径两倍 |
shortest path: all black = bh
longest path: red and black alternate <= 2 * bh
height <= 2 * log2(n + 1)红黑树的平衡不是高度差平衡，而是用黑高一致和红节点不连续限制高度。
- 误区：红黑树要求左右子树高度差不超过 1。 这是 AVL 的约束；红黑树允许更松的近似平衡。
- 误区：黑高相同就足够限制高度。 还需要红节点不能连续，否则可插入任意多红节点拉长路径。
- 误区：最长路径两倍关系是经验值。 它由黑高一致和红节点不连续两条性质严格推出。
- 追问：最短路径为什么可以看作全黑？ 在黑高相同的前提下，不插入红节点时路径最短。
- 追问：最长路径为什么至多红黑交替？ 红节点不能有红孩子，所以两个黑节点之间最多夹一个红节点。
- 追问：这对复杂度有什么意义？ 树高被限制在 O(log n)，查找、插入、删除都能保持 O(log n)。
七、加强记忆
红黑树「最长 ≤ 2 倍最短」靠两性质联手：性质 5（黑高相同） 让所有路径黑色部分等长（管下限），性质 4（红不相邻） 让红节点数 ≤ 黑节点数、最长路径 ≤ 2·黑高（管上限）。由此推出高度 h ≤ 2·log₂(n+1) = O(log n)，永不退化。相比 AVL（≤1.44 log n）稍高但更新更省，是「平衡度换维护成本」的折中。