王道 408 · 平衡二叉树（AVL）完整可视化

这不是单一动画，而是一整套学习页：定义、平衡因子、AVL 高度规律、查找、插入、删除、四种旋转（LL / RR / LR / RL）、遍历、复杂度、与普通二叉排序树对比。目标是：能动的尽量都动，并且服务于王道 408 的考点理解。

本节核心知识点（王道视角）

平衡二叉树定义：任一结点的左、右子树高度差绝对值不超过 1。
平衡因子 BF：BF = h(left) - h(right)，AVL 中 BF 只能取 -1, 0, 1。
查找效率：AVL 树高度为 O(log n)，故查找、插入、删除均为 O(log n)。
失衡判定：插入/删除后，从操作结点向根回溯，找到第一个失衡结点。
四种调整：LL、RR、LR、RL。
插入特点：通常只需对最小失衡子树调整一次。
删除特点：删除后可能向上继续失衡，可能需要多次调整。
高度/最小结点数规律：N(h)=N(h-1)+N(h-2)+1。
与 BST 对比：AVL 更平衡，查找更稳定，但维护成本更高。

AVL 高度与最少结点数

输入高度 h，计算高度为 h 的 AVL 树最少结点数。王道这一点经常拿来证明 AVL 高度是 O(log n)。

递推公式 N(0)=1，N(1)=2（也有教材把空树高度记为 0，此时初值略有差异；本页采用“单结点高度为 1”的习惯，更贴近直观演示）。

核心思想 最少结点时，两棵子树高度应尽量分别为 h-1 和 h-2，这样既满足平衡条件，又让结点数尽可能少。

小测验（408 风格）

AVL 实时交互：查找 / 插入 / 删除 / 遍历

先序遍历-

中序遍历（应升序）-

后序遍历-

层序遍历-

四种旋转：专门动画演示

LL 型在左孩子的左子树插入，右旋。

RR 型在右孩子的右子树插入，左旋。

LR 型在左孩子的右子树插入，先左旋左孩子，再右旋根。

RL 型在右孩子的左子树插入，先右旋右孩子，再左旋根。

操作过程记录