Wiki › Cấu trúc dữ liệu › Cây › Treap

Treap

huunguyen Updated Tháng sáu 2, 2026

Treap (ghép từ tree + heap) là một cây nhị phân tìm kiếm (BST) được ngẫu nhiên hóa: mỗi node lưu thêm một priority (độ ưu tiên) sinh ngẫu nhiên. Cây đồng thời thỏa hai tính chất: BST theo key (key trái < key node < key phải) và max-heap theo priority (priority cha $\geq$ priority con). Nhờ priority ngẫu nhiên, hình dạng cây tương đương cây sinh ra khi chèn các key theo thứ tự ngẫu nhiên, nên chiều cao kỳ vọng là $O (\log N)$ .

Treap giải các bài toán tập hợp có thứ tự động (insert / erase / tìm / k-th nhỏ nhất / đếm số phần tử $< x$ ) trong $O (\log N)$ mỗi thao tác — giống std::set nhưng mạnh hơn ở chỗ hỗ trợ hai thao tác nền tảng split (tách cây) và merge (ghép cây) cũng trong $O (\log N)$ . Hai thao tác này cho phép cài order-statistics tree (truy vấn hạng, đếm nghịch thế) và implicit treap (chèn/xóa/đảo cả một đoạn dãy) — những việc mà std::set không làm được.

Ý tưởng / Trực giác

Vì sao thêm priority ngẫu nhiên lại giúp cây cân bằng?

Nếu chỉ giữ tính chất BST, thứ tự chèn quyết định hình dạng cây. Chèn $1, 2, 3, \dots, N$ theo thứ tự tăng dần tạo ra cây "que" cao $N$ — mọi thao tác trở thành $O (N)$ .
Khi mỗi key được gán thêm một priority ngẫu nhiên và ta bắt cây tuân theo max-heap trên priority, thì node nào có priority lớn nhất buộc phải làm gốc. Trong khi đó vị trí trái/phải vẫn do key quyết định (BST). Kết hợp lại: cấu trúc cây hoàn toàn bị priority quyết định, mà priority lại ngẫu nhiên.
Một sự thật quan trọng: với một tập key cho trước, cây treap là DUY NHẤT một khi đã cố định bộ priority (giả sử priority đôi một khác nhau). Cây đó chính là cây ta nhận được nếu chèn các key theo thứ tự priority giảm dần. Vì thứ tự đó ngẫu nhiên, chiều cao kỳ vọng là $O (\log N)$ — đúng kết quả của BST chèn ngẫu nhiên.

Hai viên gạch nền tảng:

split(t, k): tách cây $t$ thành $(L, R)$ với mọi key trong $L \leq k$ và mọi key trong $R > k$ . Đi xuống theo tính chất BST, "cắt" tại biên $k$ .
merge(L, R): giả thiết mọi key trong $L$ nhỏ hơn mọi key trong $R$ , ghép lại thành một treap hợp lệ. Tại mỗi bước, node nào priority lớn hơn được đưa lên làm gốc để giữ max-heap.

Mọi thao tác khác đều viết lại được qua split/merge:

insert(k): split tại $k - 1$ rồi merge(merge(L, node), R).
erase(k): split để cô lập đúng phần chứa $k$ rồi bỏ đi và merge phần còn lại.

Vì cả split và merge chỉ đi theo một đường gốc–lá có độ dài $O (\log N)$ kỳ vọng, mỗi thao tác là $O (\log N)$ .

Ví dụ chạy tay

Chèn lần lượt các key $5, 3, 8, 1$ . Giả sử bộ sinh ngẫu nhiên cho priority (ghi trong ngoặc) như sau: $5 (20), 3 (50), 8 (10), 1 (80)$ . Vì là max-heap theo priority, node priority lớn sẽ nổi lên gốc.

Bước 1 — chèn 5(20): cây chỉ có một node.

   5(20)

Bước 2 — chèn 3(50): theo BST, $3 < 5$ nên 3 nằm bên trái 5. Nhưng priority $50 > 20$ , max-heap bị vi phạm → 3 phải nổi lên làm gốc, 5 thành con phải.

     3(50)
        \
        5(20)

Bước 3 — chèn 8(10): $8 > 3 \Rightarrow$ sang phải; $8 > 5 \Rightarrow$ sang phải nữa. Priority $10 < 20 < 50$ , không cần nổi lên.

Bước 4 — chèn 1(80): $1 < 3$ nên thuộc nhánh trái nhất. Nhưng priority $80$ là lớn nhất → 1 nổi lên thành gốc mới, toàn bộ cây cũ thành con phải của nó.

Cây này tuy trông như "que" vì ta cố ý chọn priority sắp xếp; trên thực tế priority ngẫu nhiên độc lập với key nên xác suất ra cây mất cân bằng rất thấp, chiều cao kỳ vọng $O (\log N)$ .

Minh họa split(t, 4) trên cây cuối (tách thành key $\leq 4$ và key $> 4$ ): đi từ gốc 1, vì $1 \leq 4$ → 1 và nhánh trái thuộc $L$ , tiếp tục split nhánh phải. Tại 3, $3 \leq 4$ → 3 thuộc $L$ , đệ quy phải. Tại 5, $5 > 4$ → 5 và nhánh phải thuộc $R$ , đệ quy trái (rỗng). Kết quả:

 L (key ≤ 4)        R (key > 4)
   1(80)               5(20)
       \                  \
       3(50)              8(10)

Cài đặt

Treap dựa trên con trỏ. Dưới đây là phiên bản order-statistics (lưu thêm size để truy vấn k-th và đếm hạng).

#include <bits/stdc++.h>
using namespace std;

// Bộ sinh số ngẫu nhiên 64-bit, gieo mầm theo thời gian để khó bị "hack"
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

struct Node {
    int key;
    unsigned priority;   // priority ngẫu nhiên, KHÔNG đổi suốt đời node
    int size;            // số node trong cây con (để làm order statistics)
    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; }   // an toàn với cây rỗng

// Cập nhật size sau khi con thay đổi — PHẢI gọi mỗi khi nối lại con
void upd(Node* t) {
    if (t) t->size = 1 + sz(t->left) + sz(t->right);
}

// Tách t thành (L, R): key trong L <= k, key trong R > k
pair<Node*, Node*> split(Node* t, int k) {
    if (!t) return {nullptr, nullptr};
    if (t->key <= k) {                 // t và nhánh trái thuộc L, đệ quy nhánh phải
        auto [l, r] = split(t->right, k);
        t->right = l; upd(t);
        return {t, r};
    } else {                           // t và nhánh phải thuộc R, đệ quy nhánh trái
        auto [l, r] = split(t->left, k);
        t->left = r; upd(t);
        return {l, t};
    }
}

// Ghép L, R (mọi key trong L < mọi key trong R) giữ max-heap theo priority
Node* merge(Node* l, Node* r) {
    if (!l) return r;
    if (!r) return l;
    if (l->priority > r->priority) {   // gốc L ưu tiên cao hơn -> làm gốc
        l->right = merge(l->right, r); upd(l); return l;
    } else {                           // gốc R ưu tiên cao hơn -> làm gốc
        r->left = merge(l, r->left); upd(r); return r;
    }
}

// Chèn key k (phiên bản cho tập hợp các key phân biệt)
void insert(Node*& t, int k) {
    auto [l, r] = split(t, k - 1);     // l: key < k, r: key >= k
    t = merge(merge(l, new Node(k)), r);
}

// Xóa MỘT bản key k (nếu có)
void erase(Node*& t, int k) {
    auto [l, tmp] = split(t, k - 1);   // tmp: key >= k
    auto [m, r]   = split(tmp, k);     // m: key == k (cô lập), r: key > k
    if (m) { delete m; }               // tránh rò bộ nhớ
    t = merge(l, r);
}

// Phần tử nhỏ thứ k (k tính từ 1) — order statistics
int kth(Node* t, int k) {
    int ls = sz(t->left);
    if (k == ls + 1) return t->key;
    if (k <= ls)     return kth(t->left, k);
    return kth(t->right, k - ls - 1);
}

// Đếm số phần tử có key < x  (hạng của x) — rất hữu ích đếm nghịch thế
int countLess(Node* t, int x) {
    if (!t) return 0;
    if (t->key < x) return sz(t->left) + 1 + countLess(t->right, x);
    return countLess(t->left, x);
}

Cách dùng đếm nghịch thế (số cặp $i < j$ mà $a_{i} > a_{j}$ ): duyệt mảng từ trái sang, trước khi chèn $a_{j}$ đếm số phần tử đã có lớn hơn $a_{j}$ = (số phần tử hiện tại) $-$ countLess(t, a_j + 1).

Độ phức tạp

Thao tác	Thời gian	Vì sao
`split`, `merge`	$O (\log N)$ kỳ vọng	mỗi lời gọi đi theo đúng một đường gốc–lá; chiều cao kỳ vọng $O (\log N)$ do priority ngẫu nhiên
`insert`, `erase`	$O (\log N)$ kỳ vọng	mỗi cái là $O (1)$ lần `split`/`merge`
`kth`, `countLess`	$O (\log N)$ kỳ vọng	đi xuống một đường, mỗi node $O (1)$ nhờ `size`
Bộ nhớ	$O (N)$	mỗi phần tử một node, mỗi node $O (1)$ trường

Chiều cao là $O (\log N)$ kỳ vọng, không phải đảm bảo tuyệt đối: vẫn có xác suất cực nhỏ ra cây cao. Nhưng do priority độc lập với dữ liệu đầu vào, không tồn tại "test xấu cố định" làm chậm treap (khác với quicksort dùng pivot cố định). Đây là lý do nên gieo mầm rng theo thời gian thay vì hằng số.

⚠️ Lỗi thường gặp

Quên gọi upd sau khi nối lại con. Mỗi khi gán t->left/t->right trong split/merge, trường size của node đó đã sai. Quên upd(t) làm kth/countLess trả kết quả sai mà cây vẫn "trông đúng" — bug rất khó truy. Quy tắc: cứ đổi con là upd.
Dùng int cho priority rồi so sánh sai khi trùng. rng() của mt19937 trả unsigned; nếu ép sang int có thể ra số âm và phá thứ tự so sánh. Nếu hai priority trùng nhau, max-heap có thể bị vi phạm tinh vi. Nên dùng unsigned/mt19937_64, hoặc xử lý hòa priority nhất quán.
Gieo mầm rng bằng hằng số cố định. mt19937 rng(12345) khiến bộ priority luôn giống nhau giữa các lần chạy — người ra đề có thể dựng test đẩy treap về dạng "que". Hãy gieo theo chrono::steady_clock (hoặc trộn thêm địa chỉ con trỏ) để chống hack.
Sai biên split khi chèn: muốn "key < k thuộc L" thì phải split(t, k-1) chứ không phải split(t, k). Nhầm $\pm 1$ ở đây làm phần tử bằng $k$ rơi nhầm phía, dẫn tới chèn/xóa sai bản.
Đệ quy quá sâu (stack overflow). split/merge đệ quy theo chiều cao cây; với $N$ lớn và test bất lợi, đệ quy có thể vài chục nghìn mức. Thường vẫn ổn nhưng nếu giới hạn stack chặt, hãy tăng stack hoặc chuyển sang phiên bản lặp.
Rò bộ nhớ / dùng con trỏ đã delete. Trong erase, sau khi cô lập node bằng split phải delete rồi mới merge phần còn lại; đừng merge nhầm node vừa xóa vào cây.

Biến thể / Mở rộng

Implicit treap (treap theo chỉ số): thay vì so theo key, dùng size cây con trái làm "vị trí ngầm". Lúc này split tách theo số lượng phần tử (k phần tử đầu / phần còn lại), cho phép chèn/xóa/đảo (với lazy reverse) cả một đoạn dãy trong $O (\log N)$ — thứ std::set hoàn toàn không làm được.
Lazy propagation trên treap: gắn cờ lazy (cộng đoạn, gán đoạn, đảo đoạn) y như segment tree, đẩy lazy xuống con trong split/merge trước khi đi tiếp.
Lưu thêm thông tin tổng hợp: ngoài size, có thể giữ tổng/min/max của cây con để trả lời truy vấn đoạn, biến treap thành một "BBST đa năng".
So với segment tree: treap mạnh khi cần chèn/xóa phần tử ở giữa dãy hoặc tập key thưa và động; segment tree nhanh hơn (hệ số nhỏ, không đệ quy ngẫu nhiên) khi tập chỉ số cố định.

Bài tập luyện

Ảnh cân bằng (bphoto) — (Advanced) với mỗi phần tử cần đếm số phần tử lớn hơn ở bên trái và bên phải; order-statistics treap (hoặc BIT) đếm hạng khi quét dãy.
Cắt tóc (haircut20) — (Advanced) đếm số nghịch thế theo từng ngưỡng cắt; bài luyện thẳng kỹ thuật countLess khi chèn dần phần tử vào treap.
Kệ Thuốc Phép (matchstk) — (Advanced) số phép đổi chỗ liền kề tối thiểu chính bằng số nghịch thế của hoán vị tương ứng; đếm bằng cấu trúc order-statistics động.
Sắp Xếp Chỗ Ngồi (seating) — (Veteran) quản lý dãy ghế động với thao tác trên đoạn liên tiếp; implicit treap với thông tin tổng hợp (đoạn trống dài nhất) giải được trực tiếp.