想象你是一家图书馆的馆长。你的分类规则很简单：每本书按编号摆放，左架放小号、右架放大号，任何人按“折半查找”的套路找书，都能快速定位。但问题是，图书不断进场，管理员如果偷懒，只把新书随手往右一塞，书架就会越来越歪，最后变成一根长长的“右倾藤蔓”——找一本书得从第一层翻到最后一层，效率低到令人绝望。于是，两个性格迥异的管理员出现了：AVL 小姐是个完美主义者，绝不允许左右书架的高度差超过 1 层，稍有“歪斜”立刻重新码放；红黑树大叔则是个务实派，他不追求绝对的整齐，只给每层书架刷上红黑两种油漆，用几条简单的“颜值规则”暗中维持整体的稳定。两位管理员各有绝活，也有人在使用“旋转书架”和“油漆变色”时付出的不同代价。今天，我们就以这座图书馆为舞台，把 AVL 树和红黑树的平衡机制看个通透。

岗位关联

对于 AI 从业者而言，AVL 与红黑树是理解索引、缓存、有序容器乃至调度器设计的“底层直觉”。掌握它们的平衡哲学，你才能在数据量爆炸时依然优雅地保持 O(log n) 的性能承诺。

目录
  1. 可视化演示
  2. 失衡根源
  3. AVL严格平衡
  4. 旋转四法
  5. 红黑弱平衡
  6. 插入删除差异
  7. 性能大比拼
  8. 场景选择术
  9. AI 应用场景
  10. Python 演示
  11. 常见误区
  12. 面试题

可视化演示

展示AVL树严格平衡因子与四种旋转策略、红黑树弱平衡五条性质与变色旋转操作，切换模式掌握自平衡BST核心原理。

本节配有交互动效（进入视口后自动加载，约 3KB）。

AVL树严格平衡与四种旋转 每个节点左右子树高度差绝对值不超过1，平衡因子BF=height(left)-height(right)必须在{-1,0,1} LL型右旋RR型左旋LR型先左旋后右旋RL型先右旋后左旋，插入删除后沿路径向上检查并修复 BF = h(L) - h(R), |BF| <= 1, rotate to rebalance AVL严格平衡保证查找O(logn)但插入删除旋转开销较大

失衡根源

图书馆刚开业时只有几本书，管理员随手乱放也没关系，找一本最多翻三五层。可当藏书达到一万本时，如果书架长期“朝一个方向歪”，最坏情况就会变成一条万里长梯——每找一本书都要从第一层摸到最后一层。计算机里管这叫退化：一棵本该是“分叉生长”的二叉搜索树，因为插入顺序不巧（比如不断插入递增的编号），会退化成一条链表。

查找的时间取决于树的层数，也就是树高。完全平衡时，n 个节点的树高大约只有 \log_2 n 层；完全歪斜时，树高等于 n 层。差别有多大？n 是一百万时，\log_2 n 约等于 20，而 n 是一百万。同样找一本书，“认真整理”的管理员只需比对 20 次，而“放任自流”的管理员可能要翻一百万层。这就是失衡的代价。

所以，“让树保持平衡”不是洁癖，而是底线。AVL 小姐与红黑树大叔这两位管理员登上舞台，都是为了同一个目标：让树高永远待在对数级别。

T(n)=O(h),h平衡=⌊log⁡2n⌋,h歪斜=n\displaystyle T(n) = O(h), \quad h_{\text{平衡}} = \lfloor \log_2 n \rfloor, \quad h_{\text{歪斜}} = n
查找代价随树高线性增长：平衡时只有约 20 层（百万数据），歪斜时高达百万层。
  1. 代价函数查找次数与树高成正比，树高越高，折半查找失去意义。
    T(n)=O(h)\displaystyle T(n) = O(h)
  2. 平衡树高每层能容纳的节点翻倍，n 个节点的平衡树高为对数级别。
    h平衡=⌊log⁡2n⌋\displaystyle h_{\text{平衡}} = \lfloor \log_2 n \rfloor
  3. 歪斜树高每次只往一个方向挂新节点，树高退化为节点总数。
    h歪斜=n\displaystyle h_{\text{歪斜}} = n

AVL严格平衡

AVL 小姐整理书架时拿着一张体检表，每个书架层都会记录一个平衡因子（Balance Factor），即“左边比右边高几层”。她的规矩是：任何书架的平衡因子只能是 -1、0、1 三者之一——左边比右边多 1 层可以忍，多 2 层绝对不行，必须立刻重新码放。

这张体检表就是平衡因子的定义：左子树高度减右子树高度。插入新书后，她从新书的位置一路向上检查，一旦发现某个书架的平衡因子绝对值超过 1，马上判定“这里歪了”，触发旋转修复。因为管控严格，AVL 树在任意时刻都保持着近乎完美的平衡，树高被死死压在约 1.44\log_2 n 以内。

AVL 的严格换来的是极其稳定的查找性能。她的树总是矮矮胖胖，任何一次查找都差不多走同样短的路径。但代价也很明显：每次插入或删除后，她都要做一大堆检查，甚至连续做好几次旋转——因为她无法容忍哪怕 2 层的高度差。

BF=hL−hR,∣BF∣≤1\displaystyle BF = h_L - h_R, \quad |BF| \le 1
平衡因子像“体重秤”：左边书架比右边高几层一目了然，超重 2 层立即触发修复。
  1. 左减右平衡因子等于左子树高度减去右子树高度。
    BF=hL−hR\displaystyle BF = h_L - h_R
  2. 限制范围AVL 要求绝对值不超过 1，这就是“严格平衡”的含义。
    ∣BF∣≤1\displaystyle |BF| \le 1

旋转四法

当书架出现“歪斜”时，AVL 小姐就会用旋转来重新码放。所谓旋转，就是挑出三个关键节点，把中间那个“提”到父节点的位置，剩下的按大小规则重新挂接——像把一摞书从中间抽出一本放到顶部，左右两边顺势一滑，书架便恢复了整齐。

四种失衡对应四招：LL 型（左左歪斜）用一次右旋；RR 型（右右歪斜）用一次左旋；LR 型（先左后右的折线歪斜）要先左旋再右旋；RL 型则反过来先右旋再左旋。以 LL 型为例：插入导致 10 -> 20 -> 30 一路向左，此时把中间节点 20 提为新根，30 变成 20 的右子，原先 20 的右子树挂到 30 的左子——整棵树瞬间平稳。

旋转是 AVL 树维持生命的“体操动作”。只要记牢“哪边不平哪边转”，任何扭曲都能在 O(1) 次旋转内归位。

LL: 右旋一步,RR: 左旋一步,LR: 先左后右,RL: 先右后左\displaystyle\text{LL: 右旋一步,} \quad\text{RR: 左旋一步,} \quad\text{LR: 先左后右,} \quad\text{RL: 先右后左}
旋转四法如同“打架分的手势”：朝哪个方向歪，就往反方向掰回来；歪成折线就先掰直再掰正。
  1. LL 右旋连续向左偏，把中间节点提上来。
    LL⇒RotateRight\displaystyle \text{LL} \Rightarrow \text{RotateRight}
  2. RR 左旋连续向右偏，把中间节点提上来。
    RR⇒RotateLeft\displaystyle \text{RR} \Rightarrow \text{RotateLeft}
  3. LR 双旋先左后右，分两步掰直。
    LR⇒RotateLeft then RotateRight\displaystyle \text{LR} \Rightarrow \text{RotateLeft then RotateRight}
  4. RL 双旋先右后左，分两步掰正。
    RL⇒RotateRight then RotateLeft\displaystyle \text{RL} \Rightarrow \text{RotateRight then RotateLeft}

红黑弱平衡

红黑树大叔的管理方式完全不同。他不要求左右高度差小于等于 1，而是给每层书架刷上红或黑两种油漆，并立下五条规矩：根是黑的、叶子是黑的、红节点的孩子必须是黑的、从任一节点到其每个叶子的路径上黑节点数相同、新来的书先刷成红色。只要这些规矩不被破坏，他就不动手。

猛一看很玄妙，但核心效果是一条路径二倍界：任何一条从根到叶子的路径，其长度最多不会超过最短路径的两倍。因为红节点不能连续出现，而所有路径的黑节点数又必须相等——红色只是“插入时的临时缓冲”，黑节点才真正承担等距骨架。红黑树因此比 AVL 更“宽容”，树高最多约 2\log_2 n，但对数级别的性能承诺依然稳稳成立。

面对插入导致的失衡，AVL 小姐可能立刻开始旋转；红黑树大叔却常常只是拿起油漆桶，把几个节点的颜色换一换——只有颜色解决不了时，才动用旋转。这便是“变色省钱”的哲学。

hRB≤2×hmin≤2log⁡2(n+1)\displaystyle h_{\text{RB}} \le 2 \times h_{\text{min}} \le 2 \log_2 (n+1)
红黑树用颜色换自由：不追求“左右相等”，只保证“黑的一样多”，于是让树高最多翻倍。
  1. 长度约束最长路径不超过最短路径的两倍。
    hRB≤2×hmin\displaystyle h_{\text{RB}} \le 2 \times h_{\text{min}}
  2. 对数上界即使两倍关系，树高仍在 O(log n) 范围。
    2log⁡2(n+1)\displaystyle 2 \log_2 (n+1)

插入删除差异

同样是插入一个节点，AVL 和红黑树的“体力消耗”差异明显。AVL 在插入后必须向上回溯，检查每一个祖先的平衡因子，一旦发现 |BF|=2，立刻旋转修复；最坏情况下，一次插入需要 O(log n) 次旋转，因为可能一路旋转到根。删除时更甚，同样需要多次旋转来维持严格平衡。

红黑树插入新节点时默认刷成红色，多数情况下只需变色调整即可满足五条铁律，最多做两次旋转；删除时红黑树虽然也要修复，但平均旋转次数远小于 AVL。从总体趋势看：越严格的平衡，修复代价越高涨；越“宽心”的弱平衡，修复越省力。

删除操作也遵循同样的逻辑：AVL 的旋转次数会随着树高增加而增加，红黑树则因为“黑高相等”这一宽松约束，修复路径往往更短。这也是工程中写入频繁的场景更倾向红黑树的原因。

AVL 插入: 最多 O(log⁡n) 次旋转,RB 插入: 至多 2 次旋转\displaystyle \text{AVL 插入: 最多 } O(\log n) \text{ 次旋转,} \quad\text{RB 插入: 至多 2 次旋转}
AVL 像锱铢必较的审计员，账本有一分不对就翻个底朝天；红黑树像粗放但高效的经理，只要大方向不偏就只做微调。
  1. AVL 多次旋转严格平衡需要回溯所有祖先，最坏 O(log n) 次。
    AVL: Θ(log⁡n) rotations\displaystyle \text{AVL: } \Theta(\log n) \ \text{rotations}
  2. 红黑至多两次变色解决大部分问题，旋转只需常数次。
    RB: O(1) rotations\displaystyle \text{RB: } O(1) \ \text{rotations}

性能大比拼

如果要给两位管理员记一场比赛，查找环节 AVL 小姐胜出：由于她要求绝对平衡，树的平均高度更矮，查找时比较次数更少。红黑树因为路径可能达到两倍长，查找常数略大，“最长路径”也长一些。但如果比的是插入删除，红黑树大叔立刻扳回一城：他大部分时候只需变色外加至多两三次旋转，耗时稳定且局部性好，而 AVL 可能要沿着祖先链一路旋转。

将两者换算成“常数因子”来理解：复杂度同为 O(log n)，但 AVL 的 log 底数更“大”（更矮），红黑树的常数更大（更高）。可红黑树的写操作更便宜，还会避免 AVL 在删除时那种“修完一边又发现另一边歪了”的连锁反应。一句话总结比赛结果：AVL 更适合读多写少的场景，红黑树更适合写多读少的场景。

比赛中没有绝对的胜者，只有“值不值得”。当你的场景是构建只读缓存，AVL 的严格换来极致查找；当你的场景是高频写入的数据库索引与字典结构，红黑树的宽松换来流畅更新。

AVL: 查找略快, 写慢RB: 写快, 查找略慢\displaystyle\text{AVL: 查找略快, 写慢} \qquad\text{RB: 写快, 查找略慢}
复杂度的“大 O”相同，但常数因子不同——AVL 把资源花在“读”上，红黑树把资源省在“写”上。
  1. 读性能AVL 的高度更矮，查找路径更短。
    Lookup: AVL≤RB\displaystyle \text{Lookup: AVL} \le \text{RB}
  2. 写性能红黑树的旋转次数更少，写操作更高效。
    Update: RB≤AVL\displaystyle \text{Update: RB} \le \text{AVL}

场景选择术

工程师在做技术选型时，可以套用一句口诀：读多选 AVL，写多选红黑。更确切地说，如果搜索操作极其频繁、插入删除极少，AVL 树能榨干每一次查找的性能；如果系统处于高频动态更新中，比如任务调度、内存管理、有序集合，红黑树能以更平稳的代价维持结构。

放眼真实世界，红黑树是默认偏好：Java 的 TreeMap/TreeSet、C++ STL 的 std::map/std::multimap、Linux 内核的 CFS 进程调度器，都用红黑树。这是因为业务系统里增删改是常态，红黑树把每次“整理书架”的开销压到最低。AVL 则活跃在查找密集型场景，如某些只读数据库索引或地理空间索引中，追求极致的查询响应。

回到图书馆：AVL 小姐适合接待“只查不借”的研究型读者，红黑树大叔适合应对“借借还还”的繁忙流通台。理解两种平衡机制，本质是理解“在约束与成本之间如何取舍”——这是数据结构教给工程师最宝贵的一课。

读多写少→AVL,写多读少→RB\displaystyle\text{读多写少} \rightarrow \text{AVL},\qquad\text{写多读少} \rightarrow \text{RB}
选型如选员工：查资料频繁的图书馆配 AVL 这位“人形检索机”，事务繁忙的前台配红黑树这位“高效调度员”。
  1. 读多选 AVL查找是主战场，用严格平衡换最短路径。
    Read-heavy⇒AVL\displaystyle \text{Read-heavy} \Rightarrow \text{AVL}
  2. 写多选红黑更新是主战场，用变色和少量旋转换吞吐。
    Write-heavy⇒RB\displaystyle \text{Write-heavy} \Rightarrow \text{RB}

AI 应用场景

MySQL 索引为什么不用 AVL 而是 B+ 树

阶段：数据存储与特征检索

解决的问题：AI 模型训练需要海量特征数据，尤其是向量索引与键值查询，需要同时支持“按范围扫描”与“按主键定位”。传统 AVL 树虽然能保证 O(log n) 查找，但每个节点只存一个键，磁盘 IO 次数高；红黑树同样不适合磁盘页存储。数据库中真正的索引结构是 B+ 树——它借鉴了“平衡保持”的思想，但把节点“拍扁”成磁盘页，一次 IO 读出多个键。

具体案例：训练样本按用户 ID 存储在 MySQL InnoDB 中，每当新样本批量写入，B+ 树自动分裂合并、保持平衡；特征服务按 ID 快速命中一行并返回，同时还能范围扫描某时间窗内的样本。

Java TreeMap 实现中的红黑树

阶段：特征排序与在线服务

解决的问题：推荐系统的特征字典需要按 key 有序存储并快速增删。AVL 树在频繁更新时旋转成本太高，红黑树以“变色为主、旋转为辅”的策略保证每次操作 O(log n)，且实现相对简单、空间开销小。

具体案例：在线推荐服务用 TreeMap<Long, Feature> 保存用户最近 N 个行为特征，新行为到达时插入、旧行为过期时删除，红黑树让这个窗口始终有序且高效，相关候选特征可以直接取“前 K 个”。

Linux CFS 进程调度器中的红黑树

阶段：任务调度与资源管理

解决的问题：AI 训练任务往往需要并行运行多个进程，操作系统需要按“虚拟运行时间”快速找到下一个要执行的进程。红黑树适合这种“频繁插入（新任务） + 频繁删除（任务完成） + 找最小（最该调度）”的高频场景。

具体案例：训练平台上数十个 PyTorch 训练进程并发执行，Linux 内核用红黑树按 vruntime 排序，每次调度 O(log n) 找到最小节点，兼顾公平与效率。

Python 演示

python126 行
class Node:    def __init__(self, key):        self.key = key        self.left = None        self.right = None        self.parent = None        self.red = True  class RedBlackTree:    def __init__(self):        self.root = None     def rotate_left(self, x):        y = x.right        x.right = y.left        if y.left:            y.left.parent = x        y.parent = x.parent        if not x.parent:            self.root = y        elif x == x.parent.left:            x.parent.left = y        else:            x.parent.right = y        y.left = x        x.parent = y     def rotate_right(self, x):        y = x.left        x.left = y.right        if y.right:            y.right.parent = x        y.parent = x.parent        if not x.parent:            self.root = y        elif x == x.parent.right:            x.parent.right = y        else:            x.parent.left = y        y.right = x        x.parent = y     def insert(self, key):        node = Node(key)        if not self.root:            self.root = node            node.red = False            return        cur = self.root        while cur:            parent = cur            if key < cur.key:                cur = cur.left            else:                cur = cur.right        node.parent = parent        if key < parent.key:            parent.left = node        else:            parent.right = node        self.fix_insert(node)     def fix_insert(self, z):        while z.parent and z.parent.red:            p = z.parent            g = p.parent            if p == g.left:                u = g.right                if u and u.red:                    p.red = False                    u.red = False                    g.red = True                    z = g                else:                    if z == p.right:                        z = p                        self.rotate_left(z)                    z.parent.red = False                    g.red = True                    self.rotate_right(g)            else:                u = g.left                if u and u.red:                    p.red = False                    u.red = False                    g.red = True                    z = g                else:                    if z == p.left:                        z = p                        self.rotate_right(z)                    z.parent.red = False                    g.red = True                    self.rotate_left(g)        self.root.red = False     def inorder(self, node, out):        if not node:            return        self.inorder(node.left, out)        out.append((node.key, 'R' if node.red else 'B'))        self.inorder(node.right, out)  def main():    rbt = RedBlackTree()    for key in [10, 20, 30, 15, 25, 5, 1]:        rbt.insert(key)    out = []    rbt.inorder(rbt.root, out)    print('inorder:', out)    print('root:', rbt.root.key, 'red' if rbt.root.red else 'black')    h = 0    stack = [(rbt.root, 1)]    while stack:        node, d = stack.pop()        if node:            h = max(h, d)            stack.append((node.left, d + 1))            stack.append((node.right, d + 1))    print('height:', h, 'log2n:', 3)  if __name__ == '__main__':    main()
目的：演示红黑树插入操作如何在“变色”与“旋转”之间巧妙切换，最终保持根黑、红子黑、黑高一致的五大铁律。
  1. if key < cur.key: cur = cur.left按二叉搜索树规则找插入位置，左小右大。
  2. node.red = True新节点默认红色，降低破坏黑高的概率。
  3. self.rotate_left(z)右偏时左旋，把中间节点提升为父节点。
  4. u = g.right检查叔节点，决定是“变色”还是“旋转”。
  5. while z.parent and z.parent.red连续红色违规时才需要修复。
  6. self.root.red = False最后把根强制涂黑，保证性质二成立。

常见误区

误区AVL 树是绝对平衡的树，左右子树高度必须一模一样，否则就失衡。

正解AVL 允许左右子树高度差为 1，即平衡因子 ∈ {-1, 0, 1}。只有高度差达到 2 时才需要旋转。它追求的是“大约齐整”，而不是绝对对称——像书架允许左边比右边高一层，但不允许高两层。

为何常见：因为“严格平衡”四个字容易让人联想到“完全相等”，忽视了平衡因子本身的容差。

误区红黑树中任意两条从根到叶子的路径，长度精确地呈两倍关系。

正解五条性质保证的是“最长路径不超过最短路径的两倍”，而不是每条路径都恰好两倍。红色节点不能连续，加上每条路径黑高相同，才有了这个上界。好比说“最胖的人不超过最瘦的人两倍”，不代表每个人都正好是两倍。

为何常见：把“上限”误读成“精确值”——这是数学建模里常见的边界混淆。

误区既然 AVL 更平衡，那它的查找性能一定碾压红黑树。

正解两者的复杂度同为 O(log n)，AVL 只是高度常数更小。在百万级数据下，AVL 树高约 20 层，红黑树最多约 40 层，实际比较次数差距往往只有几次，CPU 缓存与数据局部性常常让差距可忽略。

为何常见：过度关注理论模型中的树高，忽略了真实硬件中常数的力量。

误区红黑树用变色替代了旋转，所以它从不旋转。

正解红黑树是变色 + 旋转的组合拳。变色优先，但遇到“红色节点出现在错误方向”（所谓 zig-zag 形态）时，仍需旋转把路径掰直。旋转成本高但次数少，变色成本低但使用频繁——两者分工协作。

为何常见：把“变色为主”简化成“不变色”，丢掉了红黑树修复策略中“旋转兜底”的细节。

误区红黑树插入删除都不需要多少处理，删除也一样轻松。

正解红黑树的删除修复比插入复杂得多，可能涉及“双黑”与多种情况分支；但它的旋转次数仍是 O(1) 级别，而 AVL 删除可能需要沿着祖先链反复旋转。复杂度上红黑树更可控，但实现难度并不低。

为何常见：只看到“插入方便”的表象，忽视删除修复的真正难点。

面试题

Q1. AVL 树的平衡因子（Balance Factor）是指什么？

单选题 · easy

  • A.左子树节点数减右子树节点数
  • B.左子树高度减右子树高度← 正确答案
  • C.树高减去节点数
  • D.红黑节点的数量差

答案：B。平衡因子的定义是左子树高度减右子树高度，AVL 要求其绝对值不超过 1。A 选项描述的是“节点数差”，与高度无关；C 和 D 更是张冠李戴。

Q2. 向一棵 AVL 树依次插入 10、20、30，会触发哪种失衡与旋转？

单选题 · easy

  • A.LL 型，右旋
  • B.RR 型，左旋← 正确答案
  • C.LR 型，先左后右
  • D.RL 型，先右后左

答案：B。插入顺序 10 → 20 → 30 形成连续向右的“右右歪斜”，即 RR 型，需要一次左旋把 20 提为新根。10、20、30 是递增序列，绝不是左右折线，所以排除 LR/RL。

Q3. 关于红黑树的五条性质，下列说法正确的是？

单选题 · mid

  • A.红节点的孩子必须是黑色，根可以随意涂色
  • B.每个叶子节点（NIL）是红色
  • C.从任一节点到其每个叶子的路径上，黑节点数必须相同← 正确答案
  • D.新插入的节点默认是黑色

答案：C。红黑树性质要求“从任一节点到其每个叶子的所有路径上黑色节点数相同”，这是黑高相等的核心。A 错在根必须为黑；B 错在叶子（NIL）为黑；D 错在新节点默认是红色。

Q4. 红黑树插入的新节点为什么默认涂成红色？

单选题 · easy

  • A.红色在计算机中显示更快
  • B.红色不改变黑高，尽量少破坏规则← 正确答案
  • C.红色帮助查找
  • D.红色表示节点已删除

答案：B。新节点为红不会影响所在路径的黑色节点数，因此最多只可能破坏“红节点不能连续”这一条规则，修复成本更低。若默认黑色，则可能直接破坏黑高相等，修复代价更大。

Q5. 在查找性能上，AVL 树通常略优于红黑树，原因是？

单选题 · mid

  • A.AVL 使用了更快的硬件指令
  • B.AVL 树更矮，平均比较次数更少← 正确答案
  • C.红黑树常驻磁盘
  • D.AVL 每个节点存两个 Key

答案：B。AVL 的严格平衡让树高更矮，查找路径更短，因此平均比较次数更少。红黑树允许高度最多两倍，比较次数略多。两者复杂度同为 O(log n)，只是常数因子差异。

Q6. 关于 LR 型失衡的处理，以下说法正确的有？

多选题 · mid

  • A.先对失衡节点的左孩子做左旋← 正确答案
  • B.再对失衡节点做右旋← 正确答案
  • C.直接对失衡节点做一次右旋即可
  • D.属于双旋操作，共旋转两次← 正确答案

答案：ABD。LR 型是先左后右的双旋：先对左孩子左旋将其“掰直”，再对失衡节点右旋。C 只做一次右旋处理的是 LL 型，而非 LR 型。

Q7. 在大量插入删除的写多读少场景下，红黑树比 AVL 更合适，主要原因是？

单选题 · hard

  • A.红黑树查找更快
  • B.红黑树插入删除的旋转次数平均更少← 正确答案
  • C.红黑树不需要维护颜色
  • D.红黑树永远不旋转

答案：B。红黑树用变色代替大量旋转，插入时最多两次旋转，删除时旋转次数也可控；AVL 在删除时可能沿祖先链多次旋转。写密集场景中，红黑树的维护开销更低。A 错误因为 AVL 查找更快；C、D 与事实不符。

Q8. 一棵有 n 个节点的 AVL 树，高度 h 满足什么关系？

单选题 · easy

  • A.h 等于 n
  • B.h = log2(n) 精确值
  • C.h = O(log n)← 正确答案
  • D.h = n/2

答案：C。AVL 树的最坏高度约为 1.44 log2(n)，因此 h = O(log n)。A 是歪斜树的特征；B 的“精确值”说法不严谨；D 是随机猜测。

Q9. 下列哪些容器或系统在底层使用了红黑树？

多选题 · hard

  • A.Java 的 TreeMap← 正确答案
  • B.C++ STL 的 std::map← 正确答案
  • C.Python 的 list
  • D.Linux CFS 进程调度器← 正确答案

答案：ABD。Java TreeMap、C++ std::map 和 Linux CFS 都以红黑树为底层结构，支持有序性与高效动态维护。Python 的 list 是动态数组，与红黑树无关。

Q10. AVL 与红黑树的本质区别是什么？

单选题 · extreme

  • A.AVL 是弱平衡，红黑是严格平衡
  • B.AVL 用颜色维持平衡，红黑用高度差维持平衡
  • C.AVL 是严格平衡，红黑是弱平衡，两者都用旋转+（红黑）变色维持结构← 正确答案
  • D.AVL 只支持查找，红黑只支持插入

答案：C。AVL 用平衡因子实现严格平衡，红黑树用颜色规则实现弱平衡。两者都依赖旋转恢复结构，但红黑树额外用变色减少旋转次数。A 把两者说反了；B 张冠李戴；D 严重错误——两者都支持完整增删查。