平衡树
掌握Treap、分裂合并操作和自平衡树技术
概述
平衡树是维护有序数据集合的高效数据结构。本章节深入探讨Treap的插入删除、分裂合并操作、以及各种自平衡树技术，为解决动态维护有序集合问题提供强大工具。
核心内容
1. Treap基础操作
// Treap实现
#include <iostream>
#include <random>
using namespace std;
struct TreapNode {
int key, priority, size;
TreapNode* left;
TreapNode* right;
TreapNode(int k) : key(k), priority(rand()), size(1), left(nullptr), right(nullptr) {}
};
class Treap {
private:
TreapNode* root;
int getSize(TreapNode* node) {
return node ? node->size : 0;
}
void updateSize(TreapNode* node) {
if (node) {
node->size = 1 + getSize(node->left) + getSize(node->right);
}
}
// 右旋
TreapNode* rotateRight(TreapNode* node) {
TreapNode* newRoot = node->left;
node->left = newRoot->right;
newRoot->right = node;
updateSize(node);
updateSize(newRoot);
return newRoot;
}
// 左旋
TreapNode* rotateLeft(TreapNode* node) {
TreapNode* newRoot = node->right;
node->right = newRoot->left;
newRoot->left = node;
updateSize(node);
updateSize(newRoot);
return newRoot;
}
TreapNode* insert(TreapNode* node, int key) {
if (!node) return new TreapNode(key);
if (key < node->key) {
node->left = insert(node->left, key);
if (node->left->priority > node->priority) {
node = rotateRight(node);
}
} else if (key > node->key) {
node->right = insert(node->right, key);
if (node->right->priority > node->priority) {
node = rotateLeft(node);
}
}
updateSize(node);
return node;
}
TreapNode* remove(TreapNode* node, int key) {
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 {
if (!node->left) {
TreapNode* temp = node->right;
delete node;
return temp;
} else if (!node->right) {
TreapNode* temp = node->left;
delete node;
return temp;
} else {
if (node->left->priority > node->right->priority) {
node = rotateRight(node);
node->right = remove(node->right, key);
} else {
node = rotateLeft(node);
node->left = remove(node->left, key);
}
}
}
updateSize(node);
return node;
}
// 查找第k小
int kthSmallest(TreapNode* node, int k) {
if (!node) return -1;
int leftSize = getSize(node->left);
if (k == leftSize + 1) {
return node->key;
} else if (k <= leftSize) {
return kthSmallest(node->left, k);
} else {
return kthSmallest(node->right, k - leftSize - 1);
}
}
public:
Treap() : root(nullptr) {}
void insert(int key) {
root = insert(root, key);
}
void remove(int key) {
root = remove(root, key);
}
int kthSmallest(int k) {
return kthSmallest(root, k);
}
int size() {
return getSize(root);
}
};
int main() {
Treap treap;
// 插入元素
treap.insert(5);
treap.insert(3);
treap.insert(8);
treap.insert(1);
treap.insert(7);
cout << "第3小的元素： " << treap.kthSmallest(3) << endl;
cout << "树的大小： " << treap.size() << endl;
treap.remove(3);
cout << "删除3后第3小的元素： " << treap.kthSmallest(3) << endl;
return 0;
}2. 分裂与合并操作
// Treap分裂合并实现
class SplitMergeTreap {
private:
struct Node {
int key, priority, size;
Node* left;
Node* right;
Node(int k) : key(k), priority(rand()), size(1), left(nullptr), right(nullptr) {}
};
Node* root;
void updateSize(Node* node) {
if (node) {
node->size = 1 + getSize(node->left) + getSize(node->right);
}
}
int getSize(Node* node) {
return node ? node->size : 0;
}
// 按值分裂
pair<Node*, Node*> split(Node* node, int key) {
if (!node) return {nullptr, nullptr};
if (node->key <= key) {
auto [left, right] = split(node->right, key);
node->right = left;
updateSize(node);
return {node, right};
} else {
auto [left, right] = split(node->left, key);
node->left = right;
updateSize(node);
return {left, node};
}
}
// 按大小分裂
pair<Node*, Node*> splitBySize(Node* node, int k) {
if (!node) return {nullptr, nullptr};
int leftSize = getSize(node->left);
if (leftSize >= k) {
auto [left, right] = splitBySize(node->left, k);
node->left = right;
updateSize(node);
return {left, node};
} else {
auto [left, right] = splitBySize(node->right, k - leftSize - 1);
node->right = left;
updateSize(node);
return {node, right};
}
}
// 合并两个treap
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);
updateSize(left);
return left;
} else {
right->left = merge(left, right->left);
updateSize(right);
return right;
}
}
public:
SplitMergeTreap() : root(nullptr) {}
void insert(int key) {
auto [left, right] = split(root, key);
Node* newNode = new Node(key);
root = merge(merge(left, newNode), right);
}
void remove(int key) {
auto [left, temp] = split(root, key - 1);
auto [mid, right] = split(temp, key);
root = merge(left, right);
}
// 区间操作：获取区间[l,r]
vector<int> getRange(int l, int r) {
auto [left, temp] = splitBySize(root, l - 1);
auto [mid, right] = splitBySize(temp, r - l + 1);
vector<int> result;
inorder(mid, result);
root = merge(merge(left, mid), right);
return result;
}
private:
void inorder(Node* node, vector<int>& result) {
if (!node) return;
inorder(node->left, result);
result.push_back(node->key);
inorder(node->right, result);
}
};
int main() {
SplitMergeTreap treap;
for (int i = 1; i <= 10; i++) {
treap.insert(i);
}
vector<int> range = treap.getRange(3, 7);
cout << "区间[3,7]的元素： ";
for (int x : range) {
cout << x << " ";
}
cout << endl;
return 0;
}解题技巧
🎯 操作选择
根据问题需求选择合适操作：插入删除用基础操作，区间操作用分裂合并。
⚡ 性能优化
维护子树大小信息支持第k小查询，使用随机优先级保证期望性能。
🔧 实现要点
注意更新节点信息，正确处理空指针，分裂合并操作要保持BST性质。
🧮 应用场景
动态维护有序集合，支持插入删除、第k小查询、区间操作等复杂需求。