红黑树不要求任意节点左右子树高度完全相等，但其查找时间仍为 O(log n)。支撑这一结论的关键理由是（）。
从同一节点到各空叶子的路径具有相同黑节点数，红节点又不能连续出现，因此最长路径至多在黑节点之间各插一个红节点，长度不超过最短全黑路径的两倍。结合节点数可推出树高为 O(log n)。
选项分析
错误。二叉搜索树的关键字用于有序比较，叶子关键字不要求相同。
正确。红节点不相邻与黑高一致共同限制了路径长度比例。
错误。红黑树通过局部旋转和重新着色恢复性质，不会每次重建整棵完全二叉树。
错误。红黑树可保存大量节点，节点数不是其平衡条件。
本题为什么容易错
容易误以为只有“左右高度差不超过1”才能得到 O(log n)。AVL 是更严格的高度平衡，红黑树则用颜色约束获得较宽松但足够的高度上界。
简短答案
红黑树并非完全平衡，为什么查找仍能保持对数级，正确答案是 B（任一路径红节点不能相邻且黑高一致，使最长根叶路径不超过最短路径的两倍）。从同一节点到各空叶子的路径具有相同黑节点数，红节点又不能连续出现，因此最长路径至多在黑节点之间各插一个红节点，长度不超过最短全黑路径的两倍。结合节点数可推出树高为 O(log n)。
易混淆概念对比表
| 概念 | 本题判断 | 区别要点 | 记忆提示 |
|---|---|---|---|
| 所有叶子节点都保存相同的关键字 | 本题干扰项 | 错误。二叉搜索树的关键字用于有序比较，叶子关键字不要求相同。 | 看到该词不要急着选，先判断是否真正解决题干问题 |
| 任一路径红节点不能相邻且黑高一致，使最长根叶路径不超过最短路径的两倍 | 本题正确答案 | 正确。红节点不相邻与黑高一致共同限制了路径长度比例。 | 看到题干核心场景时优先联想到它 |
| 每次插入都会把整棵树重建为完全二叉树 | 本题干扰项 | 错误。红黑树通过局部旋转和重新着色恢复性质，不会每次重建整棵完全二叉树。 | 看到该词不要急着选，先判断是否真正解决题干问题 |
| 红黑树只允许保存不超过两个节点 | 本题干扰项 | 错误。红黑树可保存大量节点，节点数不是其平衡条件。 | 看到该词不要急着选，先判断是否真正解决题干问题 |
本题易混淆选项怎么区分
- 所有叶子节点都保存相同的关键字：错误。二叉搜索树的关键字用于有序比较，叶子关键字不要求相同。
- 每次插入都会把整棵树重建为完全二叉树：错误。红黑树通过局部旋转和重新着色恢复性质，不会每次重建整棵完全二叉树。
- 红黑树只允许保存不超过两个节点：错误。红黑树可保存大量节点，节点数不是其平衡条件。
知识点详解
红黑树是一种自平衡二叉搜索树。常见性质包括节点为红或黑、根为黑、空叶子为黑、红节点的孩子为黑，以及从任一节点到其后代空叶子的路径包含相同数量黑节点。设根的黑高为 bh，树至少包含约 2^bh-1 个内部节点，而任一路径长度不超过 2bh，因此高度受 O(log n) 限制。插入和删除通过局部旋转与重新着色恢复这些性质。
备考速记
黑高一样，红不相邻；最长只能黑红交替，至多是最短两倍。
时间复杂度在时间复杂度场景中的作用
时间复杂度在本题中的核心价值，是解决“红黑树不要求任意节点左右子树高度完全相等，但其查找时间仍为 O(log n)。支撑这一结论的关键理由是（）”这个场景问题。复习时不要只背选项名称，还要理解它为什么适用于该场景，以及它能解决哪类安全、流程或管理问题。
同类题怎么考
- 根据红黑性质判断一棵着色树是否合法。
- 解释红黑树为何不会退化为线性高度。
时间复杂度在软件设计师软考中的考法
软考选择题通常不会只考概念定义，还会把时间复杂度放到时间复杂度场景中，要求判断它的作用、适用范围或与相近概念的区别。遇到这类题时，先抓住题干中的业务场景，再看哪个选项最能解决该场景下的核心问题。
解题思路
可以先想两条极端路径。最短路径几乎全是黑节点；最长路径想尽量拉长，就在黑节点之间插红节点。但规则不允许红接红，所以最多插成黑、红、黑、红。两条路径的黑节点数又相同，于是最长最多约为最短的两倍。这个限制足以防止树退化成链表，也就保住了对数级查找。
考点定位
红黑树保证的是近似平衡，不是AVL树那样严格限制左右子树高度差。判断题看到“完全平衡”通常要警惕。
易错提醒
- 把空叶子NIL忽略后，错误计算某条路径的黑高。
- 认为根节点到每个普通叶子的总节点数必须相同。
- 把重新着色当成会破坏二叉搜索树关键字顺序的操作。
备考提示
- 画一条全黑短路径，再画一条黑红交替长路径，直观看两倍关系。
- 把AVL树的高度差约束与红黑树的颜色约束放在表中比较。
你可能还想了解
- 红黑树为什么不是完全平衡树？
- 红节点不能相邻怎样限制树高？
- 红黑树与AVL树的平衡条件有什么区别？
本文小结
红黑树依靠黑高一致和红节点不能相邻限制路径长度：最长根叶路径不超过最短路径的两倍，因此树高及查找复杂度保持O(log n)。