平衡树

平衡树？何方神圣

平时我们最害怕的是什么！暴力，没错，暴力的的时间复杂度通常会高得可怕，甚至使你一分不得，在“树论”上也是一样的，倘若使用普通的暴力，很难应对极端情况（比如退化成链或者接近于链），那有没有什么方法来优化掉树上暴力呢？设想一下：树上暴力之所以时间复杂度高，还不是因为树长得太奇怪了？既然改变不了自身，那就改变环境！构造一棵较为平衡的树就行了嘛（正所谓错的不是我而是这棵树啊）。
说的好，但如何构造一棵较为平衡的树呢？这意味着最好我从任意一个叶子节点出发，不超过 \(\log n\) 次就能到达根节点，而这又意味着每次向上规模至少 \(\times 2\) ，即树的任意一个节点的左右子树（因为是二叉树）大小的绝对值不超过 \(1\) 。这样构造出来的树相对比较平衡。

平衡树的插入操作

好不容易知道怎么构建一棵平衡树，现在又怎么维护它的平衡性呢？我们知道，如果在现有平衡树的基础上若尝试插入一个节点，大概率会使得这一颗树失去平衡性，久而久之就会退化成一条链（真是太可怕了），因此我们要尝试维护一棵树的平衡性！怎么维护呢？首先，我们令这个插入的破坏了树的平衡性的节点叫做麻烦节点（确实麻烦），而被这个麻烦节点破坏了平衡性的节点我们叫做被破坏节点（无论如何一定包含根节点）。那么被破坏节点和麻烦节点的关系只有可能是以下四种可能：

1. LL型，当前麻烦节点是距离当前麻烦节点最近的被破坏节点的左儿子的左儿子的子树（或本身），那么需要一次右旋（一会会讲）。
2. RR型，当前麻烦节点是距离当前麻烦节点最近的被破坏节点的右儿子的右儿子的子树（或本身），那么需要一次左旋（一会也会讲）。
3. LR型，当前麻烦节点是距离当前麻烦节点最近的被破坏节点的左儿子的右儿子（或本身），那么需要先一次右旋，接着一次左旋（顺序很重要！）。
4. RL型，当前麻烦节点是距离当前麻烦节点最劲的被破坏节点得到右儿子的左儿子（或本身），那么需要先一次左旋，接着一次右旋（顺序同样很重要！）。
   那什么是左旋/右旋呢？过程很简单，一张GIF动图就懂了！

右旋：

左旋:

看懂了吗，以下是对这两种操作的详细讲解：

右旋

由上图可知，我们先把旧根节点叫做 \(u\) ，新的根节点叫做 \(v\) ，注意：若要右旋，则 \(u\) 到 \(v\) 之间必有一条连边，且 \(v\) 是 \(u\) 的左孩子（没有右旋）。
此时，我们把 \(v\) 提上来叫做根节点，\(u\) 变成其右儿子。然后把原来 \(v\) 的整个右子树（没有就不管），变成 \(u\) 的现在的右子树。

举个核桃????(仅作为示例）：

右旋前的结构：

      A
     / \
    B   AR
   / \
 BL   BR

右旋后的结构:

       B
     /   \
    BL    A
         / \
       BR   AR

左旋

由上图页可知，我们先把旧根节点叫做 \(u\) ，新的根节点叫做 \(v\) ，注意：若要左旋，则 \(u\) 到 \(v\) 之间必有一条连边，且 \(v\) 是 \(u\) 的右孩子（没有左旋）。
此时，我们把 \(v\) 提上来叫做根节点，\(u\) 变成其左儿子。然后把原来 \(v\) 的整个左子树（没有就不管），变成 \(u\) 的现在的左子树。

举个栗子????：

左旋前的结构:

      A
     / \
    AL   B
        / \
      BL   BR

左旋后的结构:

       B
     /   \
    A     BR
   / \
 AL   BL

注意，左旋和右旋虽然互为逆操作，但是提取不同的节点做 \(v,u\) 两点结果不同。
接下来我们就可以实现这个插入操作了！

Code:

AVLNode* rightRotate(AVLNode *y) {
    AVLNode *x = y->left;
    AVLNode *T2 = x->right;

    x->right = y;
    y->left = T2;

    update(y);
    update(x);

    return x;
}
AVLNode* leftRotate(AVLNode *x) {
    AVLNode *y = x->right;
    AVLNode *T2 = y->left;

    y->left = x;
    x->right = T2;

    update(x);
    update(y);

    return y;
}
AVLNode* insert(AVLNode *node, int key) {
    if (!node) return new AVLNode(key);

    if (key < node->key) {
        node->left = insert(node->left, key);
    } else if (key > node->key) {
        node->right = insert(node->right, key);
    } else {
        return node;  // 重复值不插入
    }

    update(node);  // 更新高度和大小

    // 检查平衡因子
    int balance = getBalance(node);

    // LL型（左左）
    if (balance > 1 && key < node->left->key) {
        return rightRotate(node);
    }

    // RR型（右右）
    if (balance < -1 && key > node->right->key) {
        return leftRotate(node);
    }

    // LR型（左右）
    if (balance > 1 && key > node->left->key) {
        node->left = leftRotate(node->left);
        return rightRotate(node);
    }

    // RL型（右左）
    if (balance < -1 && key < node->right->key) {
        node->right = rightRotate(node->right);
        return leftRotate(node);
    }

    return node;  // 无需调整
}

顺带一提，那个所谓的平衡因子，就是当前节点左右两棵子树的大小的差，不会超过 \(1\)（用屁股想都知道）。

平衡树的删除操作：

学会了插入，是不是觉得平衡树很简单呢，不，它好像确实没有树剖难（呜呜呜）。扯远了，我们现在就来讲讲平衡树的删除操作。删除，可能使得被删除的节点缺失父亲而变成一根无根树，所以我们借鉴一下堆的想法：借东墙补西墙。就是从他的子节点中抽一个节点来代替这个节点，当然不会是乱选，规则如下：

1. 目标节点是叶子节点 $\to $ 直接删除
2. 目标节点只有一个子节点 \(\to\) 用子节点替代这个节点之后删除这个节点。
3. 目标节点有两个子节点， \(\to\) 用右子树最小节点或左子树最大节点代替这个节点，然后删除这个节点。
   没完，由于换上来节点必然（不一定）调整了平衡性，我们还要像插入一样找是LL,LR,RL还是RR然后左右旋。

举个山楂????：

        30 (0)
       /   \
    20 (0) 40 (1)
    /   \    \
 10 (0) 25 (0) 50 (0)

（括号里的是平衡因子）
删除 30 节点，步骤如下：

• 找到目标节点，时间复杂度 \(O(\log n)\)。
• 替换节点：
  • 因为 30 有两个子节点，因此找右子树最小节点（个人喜好）：
    • 因为 40 没有左子节点，所以把 30 换成 40。
      目前如下：

        40 (0)  <-- 原30被替换为40
       /   \
    20 (0)  50 (0)  <-- 原40被50替换
    /   \
 10 (0) 25 (0)

接下来，由于这个树不平衡，需要从 50 节点向上检查，发现需要右旋，直接右旋。

        40 (1)
       /   \
    20 (0)  50 (0)
    /   \
 10 (0) 25 (0)

那么我们就愉快的完成删除了，代码如下：

Code:

// 找到子树中的最小节点（用于替换待删除节点）
AVLNode* findMinNode(AVLNode* node) {
    while (node->left) node = node->left;
    return node;
}

// 删除操作
AVLNode* remove(AVLNode* node, int key) {
    if (!node) return nullptr;

    // 1. 标准BST删除
    if (key < node->key) {
        node->left = remove(node->left, key);
    } else if (key > node->key) {
        node->right = remove(node->right, key);
    } else {
        // 情况1/2：无子节点或只有一个子节点
        if (!node->left || !node->right) {
            AVLNode* temp = node->left ? node->left : node->right;
            if (!temp) {  // 无子节点
                temp = node;
                node = nullptr;
            } else {      // 有一个子节点
                *node = *temp;  // 用子节点覆盖自身
            }
            delete temp;
        } 
        // 情况3：有两个子节点
        else {
            AVLNode* temp = findMinNode(node->right);  // 找到右子树的最小节点
            node->key = temp->key;                    // 用该节点的值替换自身
            node->right = remove(node->right, temp->key); // 递归删除替换节点
        }
    }

    if (!node) return nullptr;  // 树为空则直接返回

    // 2. 更新高度和子树大小
    update(node);

    // 3. 检查平衡并调整
    int balance = getBalance(node);

    // LL型失衡
    if (balance > 1 && getBalance(node->left) >= 0) {
        return rightRotate(node);
    }
    // LR型失衡
    if (balance > 1 && getBalance(node->left) < 0) {
        node->left = leftRotate(node->left);
        return rightRotate(node);
    }
    // RR型失衡
    if (balance < -1 && getBalance(node->right) <= 0) {
        return leftRotate(node);
    }
    // RL型失衡
    if (balance < -1 && getBalance(node->right) > 0) {
        node->right = rightRotate(node->right);
        return leftRotate(node);
    }

    return node;  // 无需调整则直接返回
}

查询（查找值/排名/第 \(k\) 小/前驱后继）

是不是抢了权值线段树的活了？

1.查找是否存在某个值：

因为这棵树已经是一棵非常适合暴力的树了，可以直接递归暴力查找:

bool search(AVLNode* node, int key) {
    if (!node) return false;
    if (key < node->key) return search(node->left, key);
    else if (key > node->key) return search(node->right, key);
    else return true;  // 找到key
}

2.查找排名

排名怎么写呢？有点难搞啊。假设我们要查找的键值叫做 \(key\),那 \(key\) 的排名就是比 \(key\) 小的节点数+1吗 ，所以直接是用子树大小来算：

int getRank(AVLNode* node, int key) {
    if (!node) return 1;  // 空树时key的排名为1（最小）
    if (key < node->key) {
        return getRank(node->left, key);
    } else if (key > node->key) {
        return getSize(node->left) + 1 + getRank(node->right, key);
    } else {
        return getSize(node->left) + 1;  // 找到key，排名为左子树大小+1
    }
}

举个花生????：

      40 (size=4)
     /   \
   20 (2) 50 (1)
  /   \
10 (1) 25 (1)

getRank(root,25) 如下：

1. \(25<40\) \(\to\) 返回左子树 \(20\)
2. \(25<20\) \(\to\) 返回左子树大小（1）+ 1 + getRank(25)。
3. \(25=25\) \(\to\) 返回左子树大小(0)+1
   最终得到1+1+1=3。

3.查询k小值

都写出排名了，这 \(k\) 小值也是一样的原理，但是要借用一下快速选择算法：

int getKth(AVLNode* node, int k) {
    int leftSize = getSize(node->left);
    if (k <= leftSize) {
        return getKth(node->left, k);  // 第k小在左子树
    } else if (k == leftSize + 1) {
        return node->key;              // 当前节点就是第k小
    } else {
        return getKth(node->right, k - leftSize - 1);  // 在右子树中找第(k - leftSize - 1)小
    }
}

举个苹果????：

（完了要没有东西举了）

getKth(root, 3)：
leftSize = 2（左子树有 10, 20, 25，实际大小为2？需要检查定义）。
\(3 > 2 + 1\) → 进入右子树，\(k = 3 - 2 - 1 = 0\)（应修正逻辑，确保k正确传递）。

4.前驱/后继查询:

前驱：

前驱的定义很容易得到，即为小于key的最大节点，可以分类讨论得到：

• 如果key有左子树，前驱是左子树的最大值。
• 不然，前驱是最近的二祖先节点（且该祖先节点的右子树包含key)。

int getPredecessor(AVLNode* node, int key) {
    if (!node) return INT_MIN;  // 无前驱
    if (key <= node->key) {
        return getPredecessor(node->left, key);  // 前驱在左子树
    } else {
        // 当前节点可能是一个候选前驱，继续向右找更大的
        int rightPredecessor = getPredecessor(node->right, key);
        return max(node->key, rightPredecessor);
    }
}

后继：

后继的定义也和前驱差不多，就是大于key的最小节点，也可以分类讨论：

• 如果key有右子树，后继是右子树的最小值。
• 否则，后继是最近的祖先节点（且该祖先的左子树包含key）。

int getSuccessor(AVLNode* node, int key) {
    if (!node) return INT_MAX;  // 无后继
    if (key >= node->key) {
        return getSuccessor(node->right, key);  // 后继在右子树
    } else {
        // 当前节点可能是一个候选后继，继续向左找更小的
        int leftSuccessor = getSuccessor(node->left, key);
        return min(node->key, leftSuccessor);
    }
}

时间复杂度分析：

常见问题Q & A:

• Q: 如果树中有重复值怎么办？
  A: 需要在节点中增加计数器（count），修改插入/删除逻辑，查询时统计重复值的数量。

• Q: 为什么查询排名用size而不用中序遍历？
  A: size将查询优化到 \(O(\log n)\)，中序遍历需要 \(O(n)\) 时间。

• Q:左子树和右子树中存的值的大小有什么规律吗？
  A:对于一个节点，其左子树的值全小于该节点，右子树全大于该节点。

那么恭喜你骚年，你学会了平衡树！

Code For Luogu P3369

#include <iostream>
#include <algorithm>
#include <climits>
using namespace std;

struct AVLNode {
    int key;
    int height;    // 当前节点高度
    int size;      // 当前子树的总节点数（用于排名查询）
    AVLNode *left, *right;
    AVLNode(int val) : key(val), height(1), size(1), left(nullptr), right(nullptr) {}
};

// 获取节点高度（空节点高度为0）
int getHeight(AVLNode* node) {
    return node ? node->height : 0;
}

// 获取子树大小（空节点大小为0）
int getSize(AVLNode* node) {
    return node ? node->size : 0;
}

// 更新节点的高度和子树大小
void update(AVLNode* node) {
    node->height = max(getHeight(node->left), getHeight(node->right)) + 1;
    node->size = getSize(node->left) + getSize(node->right) + 1;
}

// 获取平衡因子（左子树高度 - 右子树高度）
int getBalance(AVLNode* node) {
    return node ? getHeight(node->left) - getHeight(node->right) : 0;
}

// 右旋（处理LL型失衡）
AVLNode* rightRotate(AVLNode* y) {
    AVLNode* x = y->left;
    AVLNode* T2 = x->right;

    // 旋转
    x->right = y;
    y->left = T2;

    // 更新高度和大小
    update(y);
    update(x);

    return x;  // 返回新的根节点
}

// 左旋（处理RR型失衡）
AVLNode* leftRotate(AVLNode* x) {
    AVLNode* y = x->right;
    AVLNode* T2 = y->left;

    // 旋转
    y->left = x;
    x->right = T2;

    // 更新高度和大小
    update(x);
    update(y);

    return y;  // 返回新的根节点
}

// 插入操作
AVLNode* insert(AVLNode* node, int key) {
    // 1. 标准BST插入
    if (!node) return new AVLNode(key);

    if (key < node->key) {
        node->left = insert(node->left, key);
    } else if (key > node->key) {
        node->right = insert(node->right, key);
    } else {
        return node;  // 重复值不插入
    }

    // 2. 更新当前节点高度和大小
    update(node);

    // 3. 检查平衡因子并调整
    int balance = getBalance(node);

    // LL型失衡（左子树更高，且左子树的左子树更高）
    if (balance > 1 && key < node->left->key) {
        return rightRotate(node);
    }

    // RR型失衡（右子树更高，且右子树的右子树更高）
    if (balance < -1 && key > node->right->key) {
        return leftRotate(node);
    }

    // LR型失衡（左子树更高，但左子树的右子树更高）
    if (balance > 1 && key > node->left->key) {
        node->left = leftRotate(node->left);
        return rightRotate(node);
    }

    // RL型失衡（右子树更高，但右子树的左子树更高）
    if (balance < -1 && key < node->right->key) {
        node->right = rightRotate(node->right);
        return leftRotate(node);
    }

    return node;  // 无需调整
}

// 找到子树中的最小节点（辅助删除操作）
AVLNode* findMinNode(AVLNode* node) {
    while (node->left) node = node->left;
    return node;
}

// 删除操作
AVLNode* remove(AVLNode* node, int key) {
    // 1. 标准BST删除
    if (!node) return nullptr;

    if (key < node->key) {
        node->left = remove(node->left, key);
    } else if (key > node->key) {
        node->right = remove(node->right, key);
    } else {
        // 情况1：节点是叶子或只有一个子节点
        if (!node->left || !node->right) {
            AVLNode* temp = node->left ? node->left : node->right;
            if (!temp) {  // 无子节点
                temp = node;
                node = nullptr;
            } else {     // 有一个子节点
                *node = *temp;  // 用子节点覆盖自身
            }
            delete temp;
        } 
        // 情况2：节点有两个子节点
        else {
            AVLNode* temp = findMinNode(node->right);  // 找到右子树的最小节点
            node->key = temp->key;                    // 用该节点的值替换自身
            node->right = remove(node->right, temp->key);  // 递归删除替换节点
        }
    }

    if (!node) return nullptr;  // 树为空则直接返回

    // 2. 更新高度和大小
    update(node);

    // 3. 检查平衡并调整
    int balance = getBalance(node);

    // LL型失衡
    if (balance > 1 && getBalance(node->left) >= 0) {
        return rightRotate(node);
    }
    // LR型失衡
    if (balance > 1 && getBalance(node->left) < 0) {
        node->left = leftRotate(node->left);
        return rightRotate(node);
    }
    // RR型失衡
    if (balance < -1 && getBalance(node->right) <= 0) {
        return leftRotate(node);
    }
    // RL型失衡
    if (balance < -1 && getBalance(node->right) > 0) {
        node->right = rightRotate(node->right);
        return leftRotate(node);
    }

    return node;  // 无需调整
}

// 查询值的排名（比key小的数的个数 +1）
int getRank(AVLNode* node, int key) {
    if (!node) return 1;
    if (key < node->key) {
        return getRank(node->left, key);
    } else if (key > node->key) {
        return getSize(node->left) + 1 + getRank(node->right, key);
    } else {
        return getSize(node->left) + 1;
    }
}

// 查询第k小的数
int getKth(AVLNode* node, int k) {
    int leftSize = getSize(node->left);
    if (k <= leftSize) {
        return getKth(node->left, k);
    } else if (k == leftSize + 1) {
        return node->key;
    } else {
        return getKth(node->right, k - leftSize - 1);
    }
}

// 查询前驱（比key小的最大数）
int getPredecessor(AVLNode* node, int key) {
    if (!node) return INT_MIN;
    if (key <= node->key) {
        return getPredecessor(node->left, key);
    } else {
        return max(node->key, getPredecessor(node->right, key));
    }
}

// 查询后继（比key大的最小数）
int getSuccessor(AVLNode* node, int key) {
    if (!node) return INT_MAX;
    if (key >= node->key) {
        return getSuccessor(node->right, key);
    } else {
        return min(node->key, getSuccessor(node->left, key));
    }
}

int main() {
    AVLNode* root = nullptr;
    int Q, op, x;
    cin >> Q;
    while (Q--) {
        cin >> op >> x;
        switch (op) {
            case 1:  // 插入x
                root = insert(root, x);
                break;
            case 2:  // 删除x
                root = remove(root, x);
                break;
            case 3:  // 查询x的排名
                cout << getRank(root, x) << endl;
                break;
            case 4:  // 查询第k小的数
                cout << getKth(root, x) << endl;
                break;
            case 5:  // 查询x的前驱
                cout << getPredecessor(root, x) << endl;
                break;
            case 6:  // 查询x的后继
                cout << getSuccessor(root, x) << endl;
                break;
        }
    }
    return 0;
}