平衡树

概念讲解

什么是平衡树？

平衡树是一种二叉搜索树，通过旋转操作保持树的平衡，保证操作时间复杂度为 $O(\log n)$。

常见平衡树

FHQ Treap

核心操作

• split：分裂
• merge：合并

代码

123456789101112131415161718192021222324252627282930313233343536373839404142struct Node {
    int val, priority, size;
    Node *left, *right;
    Node(int v) : val(v), priority(rand()), size(1), left(nullptr), right(nullptr) {}
};

int getSize(Node* root) {
    return root ? root->size : 0;
}

void update(Node* root) {
    if (root) root->size = 1 + getSize(root->left) + getSize(root->right);
}

pair<Node*, Node*> split(Node* root, int val) {
    if (!root) return {nullptr, nullptr};
    if (root->val <= val) {
        auto [l, r] = split(root->right, val);
        root->right = l;
        update(root);
        return {root, r};
    } else {
        auto [l, r] = split(root->left, val);
        root->left = r;
        update(root);
        return {l, root};
    }
}

Node* merge(Node* left, Node* right) {
    if (!left) return right;
    if (!right) return left;
    if (left->priority < right->priority) {
        left->right = merge(left->right, right);
        update(left);
        return left;
    } else {
        right->left = merge(left, right->left);
        update(right);
        return right;
    }
}

考点分析

初赛考查方式

1. 程序阅读： 平衡树操作
2. 编程题： 动态排名

常见考点

• 插入删除
• 查询排名
• FHQ Treap

练习题

1. 平衡树的作用是什么？

2. FHQ Treap 的优点是什么？

3. 平衡树的时间复杂度是多少？

易错点

⚠️ 注意：

1. 平衡树是高级内容
2. FHQ Treap 实现简单
3. 注意维护 size
4. 优先级要随机