[!info] related notes 数据结构中的树 二叉搜索树

AVL 树

基础概念

AVL 树是一种自平衡二叉搜索树，同时满足 BST 的键顺序约束和每个节点左右子树高度差不超过 1 的约束。“平衡二叉树”不是 AVL 的唯一同义词，红黑树等结构采用不同的平衡规则。

AVL什么意思
AVL 取自 Adelson-Velsky 和 Landis 的姓氏。

AVL树本质上是一颗二叉查找树，但是它又具有以下特点：

• 它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，
• 左右两个子树 也都是一棵平衡二叉树。

在AVL树中，任何节点的两个子树的高度最大差别为 1 ，所以它也被称为平衡二叉树 。

平衡因子（Balance Factor，简写为bf）

概念
本页约定：结点的平衡因子 = 左子树的高度 - 右子树的高度。高度从子树根向下计算，不是节点相对整棵树根的深度。

在 AVL树中，所有节点的平衡因子都必须满足： -1<=bf<=1;

为什么需要平衡

当插入的数据是递增或递减的数据（如 1, 2, 3, 4, 5），不做平衡调整的普通 BST 会退化成一个链表。退化后的树，查找、插入、删除的时间复杂度会从理想的 $O(\log n)$ 恶化到 $O(n)$。

“旋转”（Rotation）

这是学习平衡二叉树最核心、也最容易卡壳的地方。当插入或删除节点破坏了平衡时，树需要通过“旋转”来恢复平衡。你需要借助画图来理解这四种基本失衡情况及对应的调整方法：

1. LL 型（左左）：在左子树的左孩子上插入导致失衡。解决：右旋（Right Rotation）。
2. RR 型（右右）：在右子树的右孩子上插入导致失衡。解决：左旋（Left Rotation）。
3. LR 型（左右）：在左子树的右孩子上插入导致失衡。解决：先左旋后右旋。
4. RL 型（右左）：在右子树的左孩子上插入导致失衡。解决：先右旋后左旋。

经典实现（AVL树与红黑树）

AVL 与红黑树都能将树高限制在 O(log n)，从而保证查找、插入、删除的最坏时间为 O(log n)：

• AVL 树：
  • 特点：要求每个节点左右子树高度差不超过 1；插入和删除都需要维护高度与平衡，删除可能沿祖先路径多次调整。
  • 适用场景：查询多、插入删除少的场景。
• 红黑树（Red-Black Tree）：
  • 特点：一种“弱平衡”的二叉树，通过给节点着色（红/黑）和五条核心规则来保证从根到叶子的最长路径不多于最短路径的两倍。更新时的旋转与维护成本和 AVL 不同；实际性能取决于读写比例和实现，不能一概说哪种更好。
  • 适用场景：工程界应用极其广泛（如 Java 的 TreeMap 和常见 std::map 实现；C++ 标准只规定复杂度等契约，并不强制使用红黑树）。