Splay Tree

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

huunguyen · Last updated 8, Tháng 4, 2026, 15:24

Splay Tree là cây nhị phân tìm kiếm tự điều chỉnh: sau mỗi thao tác, node được truy cập được đưa lên gốc (splay). Độ phức tạp $O (\log N)$ amortized cho mọi thao tác.

Ưu điểm so với AVL/Red-Black Tree:

Không cần lưu thông tin cân bằng.
Hỗ trợ split và merge tự nhiên.
Hằng số nhỏ trong thực tế.

Ứng dụng: Sequence với split/merge, order statistics, lazy propagation trên sequence động.

Thao tác Splay

Splay đưa node $x$ lên gốc bằng ba trường hợp:

Zig: $x$ là con của gốc → một lần rotate.
Zig-Zig: $x$ và cha cùng chiều → rotate cha trước, rồi rotate $x$ .
Zig-Zag: $x$ và cha khác chiều → rotate $x$ hai lần.

Cài đặt (Implicit Key Splay Tree — Sequence)

const int MAXN = 2e5 + 5;

struct Node {
    int ch[2], par, sz;
    long long val, sum, lazy;
    bool rev;
} t[MAXN];
int root, tot;

void push_up(int x) {
    t[x].sz  = t[t[x].ch[0]].sz + t[t[x].ch[1]].sz + 1;
    t[x].sum = t[t[x].ch[0]].sum + t[t[x].ch[1]].sum + t[x].val;
}

void push_rev(int x) {
    swap(t[x].ch[0], t[x].ch[1]);
    t[x].rev ^= 1;
}

void push_add(int x, long long v) {
    t[x].val += v; t[x].sum += (long long)t[x].sz * v; t[x].lazy += v;
}

void push_down(int x) {
    if (t[x].rev) {
        if (t[x].ch[0]) push_rev(t[x].ch[0]);
        if (t[x].ch[1]) push_rev(t[x].ch[1]);
        t[x].rev = 0;
    }
    if (t[x].lazy) {
        if (t[x].ch[0]) push_add(t[x].ch[0], t[x].lazy);
        if (t[x].ch[1]) push_add(t[x].ch[1], t[x].lazy);
        t[x].lazy = 0;
    }
}

bool is_root(int x) { return t[t[x].par].ch[0] != x && t[t[x].par].ch[1] != x; }
bool dir(int x)     { return t[t[x].par].ch[1] == x; }

void rotate(int x) {
    int p = t[x].par, g = t[p].par, d = dir(x);
    if (!is_root(p)) t[g].ch[dir(p)] = x;
    t[x].par = g;
    t[p].ch[d] = t[x].ch[!d]; if (t[x].ch[!d]) t[t[x].ch[!d]].par = p;
    t[x].ch[!d] = p; t[p].par = x;
    push_up(p); push_up(x);
}

void push_all(int x) {
    if (!is_root(x)) push_all(t[x].par);
    push_down(x);
}

void splay(int x, int goal = 0) {
    push_all(x);
    while (!is_root(x)) {
        int p = t[x].par;
        if (!is_root(p))
            rotate(dir(x) == dir(p) ? p : x);
        rotate(x);
    }
    if (!goal) root = x;
}

// Tìm node thứ k (1-based) trong sequence
int kth(int k) {
    int x = root;
    while (true) {
        push_down(x);
        if (t[t[x].ch[0]].sz + 1 == k) return x;
        if (k <= t[t[x].ch[0]].sz) x = t[x].ch[0];
        else { k -= t[t[x].ch[0]].sz + 1; x = t[x].ch[1]; }
    }
}

// Split: tách sequence thành [1..k] và [k+1..n]
pair<int,int> split(int k) {
    if (k == 0) return {0, root};
    if (k == t[root].sz) return {root, 0};
    int x = kth(k+1);
    splay(x);
    int L = t[x].ch[0];
    t[x].ch[0] = 0; t[L].par = 0;
    push_up(x);
    return {L, x};
}

// Merge: nối hai cây L và R (mọi key trong L < mọi key trong R)
int merge(int L, int R) {
    if (!L) return R;
    if (!R) return L;
    // Tìm rightmost của L
    root = L;
    int x = kth(t[L].sz);
    splay(x);
    t[x].ch[1] = R; t[R].par = x;
    push_up(x);
    return x;
}

Độ phức tạp

Thao tác	Độ phức tạp
Splay, insert, delete	$O (\log N)$ amortized
Split, merge	$O (\log N)$ amortized
Range query/update	$O (\log N)$ amortized

Khi nào dùng Splay Tree?

Cần split/merge trên sequence (Treap cũng làm được, nhưng Splay đơn giản hơn khi cần lazy trên node).
Thay thế cho Link-Cut Tree trong một số trường hợp (LCT thực ra dùng Splay bên trong).
Bài toán sequence động: đảo đoạn, cộng đoạn, truy vấn đoạn.

Bình luận

Không có bình luận tại thời điểm này.