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

Cây

huunguyen Updated Tháng sáu 2, 2026

Cây là đồ thị liên thông không có chu trình với $N$ đỉnh và $N - 1$ cạnh.

Khái niệm cơ bản

Cây có gốc (rooted tree) là cây trong đó một đỉnh được chọn làm gốc.

Cha (parent): đỉnh liền kề gần gốc hơn
Con (children): các đỉnh liền kề xa gốc hơn
Lá (leaf): đỉnh không có con
Độ sâu (depth): khoảng cách từ gốc, $depth [root] = 0$
Chiều cao (height): độ sâu lớn nhất trong cây
Cây con của $u$ (subtree): gồm $u$ và toàn bộ hậu duệ của $u$

Duyệt cây (DFS)

const int MAXN = 2e5 + 5;
vector<int> adj[MAXN];
int par[MAXN], dep[MAXN];

void dfs(int u, int p) {
    par[u] = p;
    for (int v : adj[u])
        if (v != p) {
            dep[v] = dep[u] + 1;
            dfs(v, u);
        }
}
// dep[root] = 0; dfs(root, -1);

DFS in/out time (Euler Tour)

Gán thời điểm vào (tin) và ra (tout) cho mỗi đỉnh:

int tin[MAXN], tout[MAXN], order[MAXN], timer_dfs = 0;

void dfs(int u, int p) {
    tin[u] = ++timer_dfs;
    order[timer_dfs] = u;
    for (int v : adj[u])
        if (v != p) dfs(v, u);
    tout[u] = timer_dfs;
}

$v$ thuộc cây con của $u$ $\Leftrightarrow$ tin[u] <= tin[v] && tout[v] <= tout[u]
Truy vấn/cập nhật toàn bộ cây con của $u$ = truy vấn đoạn [tin[u], tout[u]] → kết hợp với BIT/Segment Tree

Đường kính cây

Đường đi dài nhất giữa hai đỉnh bất kỳ. Tìm bằng hai lần BFS:

BFS từ đỉnh bất kỳ → tìm đỉnh xa nhất $u$
BFS từ $u$ → tìm đỉnh xa nhất $v$
Đường kính = $dist (u, v)$

pair<int,int> farthest(int src, int n) {
    vector<int> dist(n+1, -1);
    queue<int> q;
    q.push(src); dist[src] = 0;
    int far = src;
    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (int v : adj[u])
            if (dist[v] == -1) {
                dist[v] = dist[u] + 1;
                q.push(v);
                if (dist[v] > dist[far]) far = v;
            }
    }
    return {far, dist[far]};
}

auto [u, d1]       = farthest(1, n);
auto [v, diameter] = farthest(u, n);

Tổ tiên chung thấp nhất (LCA)

$LCA (u, v)$ là tổ tiên chung gần nhất của $u$ và $v$ .

Binary Lifting — $O (N \log N)$ tiền xử lý, $O (\log N)$ /truy vấn

Lưu $up [u] [k]$ = tổ tiên thứ $2^{k}$ của $u$ .

const int LOG = 18;
int up[MAXN][LOG], dep[MAXN];

void dfs(int u, int p) {
    up[u][0] = p;
    for (int i = 1; i < LOG; i++)
        up[u][i] = up[up[u][i-1]][i-1];
    for (int v : adj[u])
        if (v != p) { dep[v] = dep[u] + 1; dfs(v, u); }
}
// up[root][0] = root; dep[root] = 0; dfs(root, root);

int lca(int u, int v) {
    if (dep[u] < dep[v]) swap(u, v);
    int diff = dep[u] - dep[v];
    for (int i = 0; i < LOG; i++)
        if ((diff >> i) & 1) u = up[u][i];
    if (u == v) return u;
    for (int i = LOG-1; i >= 0; i--)
        if (up[u][i] != up[v][i]) { u = up[u][i]; v = up[v][i]; }
    return up[u][0];
}

int dist(int u, int v) {
    return dep[u] + dep[v] - 2 * dep[lca(u, v)];
}

Các trang chi tiết — lộ trình học

Nhóm Cây gồm 16 trang con. Gợi ý thứ tự học từ nền tảng đến nâng cao:

1. Cấu trúc nền tảng (học trước tiên)

Trang	Mục đích chính	Độ phức tạp
Heap / Hàng đợi ưu tiên	Lấy min/max động, hàng đợi ưu tiên	$O (\log N)$ /thao tác
Cây nhị phân tìm kiếm (BST)	Tập hợp có thứ tự (`set`/`map`)	$O (\log N)$ trung bình
Fenwick Tree (BIT)	Prefix sum + cập nhật điểm	$O (\log N)$
Segment Tree	Truy vấn + cập nhật đoạn (lazy)	$O (\log N)$
Trie	Lưu/tìm xâu; 01-Trie cho XOR	$O (‖ s ‖)$

2. BST cân bằng / nâng cao

Trang	Mục đích chính
Treap	BST ngẫu nhiên, split/merge, implicit treap
Splay Tree	BST tự cân bằng amortized, thao tác trên dãy

3. Kỹ thuật truy vấn trên cây

Trang	Mục đích chính
Binary Lifting	LCA, tổ tiên thứ $k$ , $O (\log N)$ /truy vấn
Heavy-Light Decomposition	Truy vấn/cập nhật trên đường đi
Centroid Decomposition	Đếm/đường đi theo phân rã trọng tâm
DSU on Tree	Gộp thông tin cây con (small-to-large)
Virtual Tree	Nén cây theo tập đỉnh quan trọng

4. Segment Tree nâng cao

Trang	Mục đích chính
Persistent Segment Tree	Truy vấn lịch sử, $k$ -th trên đoạn
Segment Tree Beats	Cập nhật min/max trên đoạn
Li Chao Tree	Bao lồi đường thẳng, tối ưu DP

5. Cây động

Trang	Mục đích chính
Link-Cut Tree	Rừng cây động, link/cut, truy vấn đường đi