AVL树

1. AVL 树介绍

AVL 树是一种高度平衡的二叉搜索树 (Binary Search Tree, BST)。它通过维持每个节点的平衡因子来保持树的平衡性，保证了在最坏情况下的操作时间接近于 \(O(\log N)\)。

2. 二叉搜索树 (BST) 的最佳与最差时间

最佳情况：当树的深度 \(d\) 最小时，BST 操作的运行时间为 \(O(\log N)\)，此时树是平衡的。
- 对于有 \(N\) 个节点的树，树的最小深度 \(d\) 为 \(d = \lfloor \log_2 N \rfloor\)。
最差情况：若树完全不平衡，例如按升序插入节点时，树会退化成一个链表，运行时间为 \(O(N)\)。
- 插入如 \(2, 4, 6, 8, 10, 12\) 的节点时，树会形成一条链，导致性能恶化。

3. 平衡与不平衡的 BST

平衡树：左子树和右子树的高度差接近，所有节点的分布较为均匀。
不平衡树：某些节点的深度过大或过小，导致树的结构接近于线性，性能退化。

4. 平衡树的几种方法

不平衡树：不做任何调整，可能会有些节点非常深。
严格平衡：始终保持树完全平衡，但维护代价高。
接近平衡：允许一些小的失衡，但通过调整节点来维持较好的平衡。
访问时调整：根据访问情况自我调整，比如自调节树。

5. 完全二叉树和满二叉树

满二叉树：每个节点要么是叶子节点，要么有两个非空子节点。
完全二叉树：除了最后一层，所有层都完全填满，并且最后一层的节点从左到右依次填充。

6. AVL 树的平衡因子

平衡因子：节点左子树的高度减去右子树的高度。
- 对于每个节点，左、右子树的高度差不超过 1，确保树的平衡。
- 每个节点都存储当前的高度或平衡因子。

7. AVL 树的操作

插入：在插入节点后，更新树的高度并检查平衡因子。如果某个节点的平衡因子不再满足要求（即高度差大于 1），通过旋转操作来恢复平衡。
删除：删除节点后同样需要更新平衡因子，并通过旋转恢复平衡。
旋转：当树失衡时，进行左旋、右旋或双旋（先左后右，或先右后左）来重新平衡。

插入详解：

在AVL树中插入节点后，可能会导致某些节点的平衡因子（balance factor）变为2或-2，破坏了树的平衡性。为了恢复平衡，AVL树通过旋转（rotation）操作来调整不平衡的子树。

AVL树的插入操作导致不平衡

当我们在AVL树中插入节点时，树的高度可能会发生变化。如果某个节点的平衡因子（其左子树高度与右子树高度之差）变为2或-2，就意味着该节点需要通过旋转来恢复平衡。

插入后高度的变化：
- 插入节点后，只会影响从插入点到根节点的路径上的节点高度。因此，在插入节点后，我们需要沿着这条路径向上检查每个节点的平衡因子并调整。
旋转的必要性：
- 如果某个节点的平衡因子变为2或-2，我们需要通过旋转调整该节点及其子树的结构。

单旋转（Single Rotation）

单旋转分为左旋和右旋。单旋转用于处理“外部情况”（Outside Case），即插入节点导致的失衡发生在某个子树的外部。

右旋转（Right Rotation）

右旋转用于处理当节点的左子树高度过高时（即平衡因子为2）。假设失衡节点为j，其左子节点为k，k的左子树高度较大，此时需要对节点j进行右旋转。

右旋转步骤：

将k的右子树作为j的左子树。
将k提升为新的根节点，j作为k的右子树。
这样就恢复了AVL树的平衡，右旋转完成。

举例：插入一个节点到j的左子树，导致j的平衡因子变为2。我们执行右旋转，结果是新的树恢复平衡。

示意图：插入导致的失衡：

    j
   /
  k
 /
X

执行右旋转后：

1
2
3

  k
 / \
X   j

双旋转（Double Rotation）

双旋转用于处理“内部情况”（Inside Case），即插入节点导致的失衡发生在某个子树的内部。这种情况需要先执行一次左旋（或右旋），再执行一次右旋（或左旋）。

左-右双旋转（Left-Right Double Rotation）

这是当节点的左子树的右子树高度过高时的情况。例如，当j的左子节点k的右子树导致失衡时，我们需要执行左-右双旋转。

左-右双旋转步骤：

先对节点k执行左旋，使其右子节点成为新的左子节点。
然后对节点j执行右旋，完成旋转恢复平衡。

举例：插入节点到j的左子树的右子树，导致失衡。首先对k进行左旋，再对j进行右旋。

示意图：插入导致的失衡：

  j
 /
k
 \
  i

执行左旋后：

    j
   /
  i
 /
k

再执行右旋后：

1
2
3

  i
 / \
k   j

外部情况：插入导致失衡发生在某节点的外部子树，使用单旋转（左旋或右旋）即可恢复平衡。
内部情况：插入导致失衡发生在某节点的内部子树，使用双旋转（先左旋后右旋，或先右旋后左旋）恢复平衡。

AVL树的旋转操作可以确保每次插入或删除后，树仍然保持平衡，操作的时间复杂度为O(log N)。

节点结构

struct AvlNode {
    Comparable element; // 存储元素
    AvlNode *left;     // 左子节点指针
    AvlNode *right;    // 右子节点指针
    int height;        // 节点高度
    AvlNode(const Comparable &ele, AvlNode *lt, AvlNode *rt, int h = 0)
        : element{ele}, left{lt}, right{rt}, height{h} {}
};

插入过程

常规的二叉搜索树插入：
- 插入新节点到叶子节点。
- 只需更新插入路径上节点的高度和平衡因子。
更新高度：
- 从新插入的节点向上回溯，更新每个节点的高度。
检查平衡因子：
- 如果节点的平衡因子变为 2 或 -2，则需要进行旋转来保持树的平衡。

插入函数实现

void insert(const Comparable &x, AvlNode *&t) {
    if (t == nullptr) {
        t = new AvlNode{x, nullptr, nullptr}; // 创建新节点
    } else if (x < t->element) {
        insert(x, t->left); // 递归插入到左子树
    } else if (t->element < x) {
        insert(x, t->right); // 递归插入到右子树
    }
    balance(t); // 进行平衡调整
}

平衡调整函数

void balance(AvlNode *&t) {
    if (t == nullptr) return;
    
    if (height(t->left) - height(t->right) > IMBALANCE) {
        // 左侧不平衡
        if (height(t->left->left) >= height(t->left->right)) {
            rotateWithLeftChild(t); // 单旋转
        } else {
            doubleWithLeftChild(t);  // 双旋转
        }
    } else if (height(t->right) - height(t->left) > IMBALANCE) {
        // 右侧不平衡
        if (height(t->right->right) >= height(t->right->left)) {
            rotateWithRightChild(t); // 单旋转
        } else {
            doubleWithRightChild(t);  // 双旋转
        }
    }
    t->height = max(height(t->left), height(t->right)) + 1; // 更新高度
}

单旋转和双旋转

单旋转：例如，将节点 k2 与其左子节点 k1 进行旋转。

void rotateWithLeftChild(AvlNode *&k2) {
    AvlNode *k1 = k2->left;
    k2->left = k1->right; // 将 k1 的右子树赋给 k2 的左子树
    k1->right = k2;       // k2 变为 k1 的右子树
    k2->height = max(height(k2->left), height(k2->right)) + 1; // 更新 k2 高度
    k1->height = max(height(k1->left), k2->height) + 1; // 更新 k1 高度
    k2 = k1; // 更新树根
}

双旋转：首先将 k3 的左子节点与其右子节点进行旋转，然后将 k3 与新左子节点进行旋转。

void doubleWithLeftChild(AvlNode *&k3) {
    rotateWithRightChild(k3->left); // 先右旋转
    rotateWithLeftChild(k3);         // 然后左旋转
}

示例插入

插入一系列节点时，AVL树会自动进行平衡。以下是插入操作的过程示例：

插入节点 5 和 40。
插入节点 45，造成右侧不平衡，需要进行单旋转或双旋转。
最终结构保持平衡。

AVL树的优缺点

优点：

始终保持 O(log N) 的查找、插入和删除时间复杂度。
高度平衡确保高效的操作。

缺点：

编程和调试较为复杂，维护平衡因子需要额外空间。
在频繁的插入和删除操作中，旋转的开销可能导致性能下降。