Treap là BST ngẫu nhiên hóa: mỗi node lưu thêm một priority ngẫu nhiên, cây duy trì tính chất BST theo key và tính chất max-heap theo priority. Do priority ngẫu nhiên, chiều cao kỳ vọng là .
Ưu điểm so với std::set: hỗ trợ thao tác split và merge trong , dễ mở rộng để lưu thêm thông tin trên cây (tổng, lazy,...).
Cài đặt
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
struct Node {
int key, priority, size;
Node *left, *right;
Node(int k) : key(k), priority(rng()), size(1),
left(nullptr), right(nullptr) {}
};
int sz(Node* t) { return t ? t->size : 0; }
void upd(Node* t) {
if (t) t->size = 1 + sz(t->left) + sz(t->right);
}
Split
Tách cây thành hai cây: key và key .
pair<Node*, Node*> split(Node* t, int k) {
if (!t) return {nullptr, nullptr};
if (t->key <= k) {
auto [l, r] = split(t->right, k);
t->right = l; upd(t);
return {t, r};
} else {
auto [l, r] = split(t->left, k);
t->left = r; upd(t);
return {l, t};
}
}
Merge
Ghép hai cây, với mọi key trong l mọi key trong r.
Node* merge(Node* l, Node* r) {
if (!l) return r;
if (!r) return l;
if (l->priority > r->priority) {
l->right = merge(l->right, r); upd(l); return l;
} else {
r->left = merge(l, r->left); upd(r); return r;
}
}
Insert và Erase
void insert(Node*& t, int k) {
auto [l, r] = split(t, k - 1);
t = merge(merge(l, new Node(k)), r);
}
void erase(Node*& t, int k) {
auto [l, tmp] = split(t, k - 1);
auto [m, r] = split(tmp, k);
delete m;
t = merge(l, r);
}
Truy vấn k-th nhỏ nhất
int kth(Node* t, int k) { // k tính từ 1
int left_sz = sz(t->left);
if (k == left_sz + 1) return t->key;
if (k <= left_sz) return kth(t->left, k);
return kth(t->right, k - left_sz - 1);
}
Khi nào dùng Treap thay vì std::set?
- Cần split / merge theo vị trí hoặc giá trị
- Cần lưu thêm thông tin trên cây con (tổng, max, lazy propagation)
- Bài yêu cầu thao tác trên dãy có thứ tự một cách linh hoạt
Với bài chỉ cần insert/erase/find thông thường, dùng std::set đơn giản hơn.
Bình luận