分数更新后，哈希表能迅速找到记录，却不能直接回答新排名。00 篇的参照实现在排名时扫描所有记录，第 k 名查询则重新排序。若查询与更新交替发生，前一次排序结果很快失效。有序树可以沿搜索路径定位分数，再用子树中的元素数量跳过整段候选；树高必须受控，否则有序输入会使路径退化成链。

本篇把这两件事分开证明：AVL 高度约束保证路径短，子树大小保证排名正确。增强字段算错时，树仍可能平衡、搜索仍可能成功，排名却已经错误。因此验证必须同时覆盖键序、高度、平衡和计数。

重复键放在哪里

教学容器是多重集，允许相同键出现多次。每个不同键只占一个节点，节点保存 key、出现次数 count、高度 height、子树元素总数 size 和左右孩子。定义空树高度为 0，叶子为 1；空树大小为 0。令 n 为包含重复项的元素数，d 为不同键数，因此 d≤n。

操作 结果与边界
add(key) 增加一次出现；相同键只增加计数
discard(key) 删除一次出现，成功返回 True，不存在返回 False
count(key) 返回出现次数，不存在返回 0
rank(key) 返回严格小于 key 的元素数，键不必存在
select(k) 返回排序后第 k 个键，k 从 1 开始；越界抛 IndexError

这里的 rank 是多重集操作，与 00 篇 rank(record_id) 不同。榜单继续使用 (-score, id) 作为树键，记录排名等于树的 rank(key)+1。ID 单调分配且不复用，所以重复分数对应不同的元组键；纯整数多重集的重复计数则单独接受测试。修改分数需要删除旧元组，再插入新元组，同时更新 ID 到分数的字典，不能原地改节点键而保留原链接。

比较模型假设键比较和计数操作为常数成本；元组比较最多检查这里固定的两个字段。Python 整数位长增长时应另外计入算术和比较成本。容器要求一致的全序，不接受比较结果不满足传递性的键。NaN 一类不满足通常全序假设的值不在输入契约内。

子树大小怎样回答查询

每个节点 x 必须满足

s(x)=s(x.left)+x.count+s(x.right).s(x)=s(x.left)+x.count+s(x.right).

求严格小于 t 的元素数时，若 t≤x.key，右子树与当前节点都不计入，继续搜索左子树；若 t>x.key，左子树所有元素和当前节点的重复项都符合条件，累加 size(left)+count，继续搜索右子树。到达空树时返回累计值。每一步排除的区域互不相交，已计入的区域全部小于 t，未决区域恰是当前子树，这就是循环不变量。

选择第 k 项时，记 L 为左子树大小。k≤L 就进入左树；L<k≤L+count 就返回当前键；否则进入右树并把 k 减去 L+count。每次下移都保持“目标是当前子树内第 k 项”，子树规模严格减少，因此查询终止。根上的总大小先用于检查 k 是否处于合法范围。

例如多重集 [2,2,5,7] 中，5 节点的左子树大小为 2。rank(5)=2，select(2)=2，select(3)=5。如果把 size 误写成节点数，搜索 5 仍成功，select(2) 却可能错误地返回 5。这是只检查中序键去重列表无法发现的反例。

旋转先维护什么

AVL 要求每个节点左右子树高度差绝对值不超过 1。更新沿搜索路径回溯，先从孩子重新计算高度和大小，再修复失衡。右旋的局部结构如下，A、B、C 表示整棵子树：

1
2
3
4
5
    y                  x
   / \                / \
  x   C      ->      A   y
 / \                    / \
A   B                  B   C

旋转前后的中序序列都是 A、x、B、y、C；节点的键和重复计数未改变，所以多重集不变。指针改动后必须先重算下降的 y，再重算上升的 x。反过来会让 x 读到 y 的旧大小。这一更新顺序来自字段依赖，而不是“旋转代码通常这样写”的惯例。左旋完全对称。

当左侧过高但左孩子偏右时，先左旋左孩子，再右旋当前节点；右左情形对称。双旋中间状态不要求整棵子树已经平衡，但每次原子旋转返回后，其局部高度与大小缓存必须对应实际链接。完整更新返回后，沿途所有节点才必须满足 AVL 平衡条件。

删除与插入共用这些字段公式，却不能只修复第一次失衡后就一律停止。删除可能使修复后子树进一步变矮，影响祖先；教学实现逐层回溯到根。若当前键仍有多个副本，只减 count，仍须更新沿途大小。

删除只有一个副本且拥有两个孩子的节点时，可以用右子树最小节点替换。若后继有多个副本，必须把后继的键和整份计数移到当前位置，再从原位置移除整个后继节点。只复制一个键并随便递减后继，会让同一键散落到两个节点，破坏左右子树严格不等的不变量。

高度与更新成本

设 N(h) 是高度为 h 的 AVL 树所需最少节点数。空树 N(0)=0，叶子 N(1)=1；高度 h 的最省节点布局有一侧高 h−1，另一侧高 h−2，因此

N(h)=1+N(h−1)+N(h−2).N(h)=1+N(h-1)+N(h-2).

N 随高度单调，故 N(h)≥2N(h−2)+1。递推展开得到节点数随 h 指数增长，反过来 h=O(log(d+1))。这针对每个合法树形成立，没有对输入分布或随机种子取期望。

查找、rank、select 最多走一条根到叶路径，最坏时间为 O(log(d+1))。插入和删除也只修改一条搜索路径及每层常数次旋转，每次旋转只更新常数个节点，所以更新最坏时间相同。重复计数改变而不增加节点时，仍须走到该键并维护祖先大小，不能因此把整次操作算成常数。

存储占用 O(d) 个节点，递归更新栈占 O(log(d+1))；这是逻辑单元计数，不是 Python 进程字节数。逐个插入 n 项建树给出 O(n log(n+1)) 的通用上界，已有排序输入可以另做线性建树，但本实现没有该接口。若每次操作后递归审计整棵树，验证额外花 O(d)，不能把带全树审计的测试程序计时说成更新的对数成本。

可复跑的验证

教学代码位于 examples/advanced-algorithms/avl.py，独立检查位于同目录 check_avl.py。从仓库根运行：

1
python3 examples/advanced-algorithms/check_avl.py

参照使用排序列表与标准库二分，检查每步增删后的多重集、严格排名、选择及异常边界；树的递归审计从真实孩子重算高度和大小，不直接相信缓存。穷举小键操作序列只能覆盖声明的有限输入，一般正确性仍由搜索分区、旋转保序和字段归纳承担。

本次实际运行通过 9330 条长度1–5的小键操作序列，加上有序、逆序、重复后继与元组用例，共9336条序列、45324次操作、1374次旋转检查。原始输出保存为 results/avl.json；该输出是教学实现的有限检查，没有测量性能。配套契约检查卡列出边界。

练习

  1. 对 [3,1,2,2] 逐项插入，画出双旋前后树形，给每个节点填写 count、height、size。删除一个 2 后，哪些字段必须改变？
  2. 为 00 篇榜单写一个适配层，用字典维护 ID 到分数，用本篇 AVL 维护 (-score,id)。与 ReferenceBoard 重放同一序列；解释为什么只更新字典会使 get 正确而 rank 错误。

增强树的设计步骤是先写聚合量的递归定义，再找出结构更新改变了哪些依赖。只要字段能由节点自身与孩子的字段在常数时间内重算，旋转就能局部修复；字段若依赖整条祖先路径，则不能直接套用这个结论。

参考资料