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

平衡二叉树（AVL树）

基础概念

平衡二叉树 全称叫做 平衡二叉搜索（排序）树，简称 AVL树。英文：Balanced Binary Tree （BBT），注：二叉查找树(BST)

AVL什么意思
AVL 是大学教授 G.M. Adelson-Velsky 和 E.M. Landis 名称的缩写，他们提出的平衡二叉树的概念，为了纪念他们，将 平衡二叉树 称为 AVL树。

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

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

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

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

概念
结点的左子树的深度减去右子树的深度。
即： 结点的平衡因子 = 左子树的高度 - 右子树的高度 。

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

为什么需要平衡

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

“旋转”（Rotation）

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

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

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

理解了旋转后，就可以开始看具体的树型了。重点学习两种最经典的平衡二叉树：

• AVL 树：
  • 特点：最严格的平衡二叉树。查找效率极高，但为了维持严格平衡，插入和删除时频繁旋转，开销较大。
  • 适用场景：查询多、插入删除少的场景。
• 红黑树（Red-Black Tree）：
  • 特点：一种“弱平衡”的二叉树，通过给节点着色（红/黑）和五条核心规则来保证从根到叶子的最长路径不多于最短路径的两倍。它的旋转次数比 AVL 树少，综合性能更好。
  • 适用场景：工程界应用极其广泛（如 Java 的 TreeMap、C++ 的 std::map、Linux 内核调度器等）。