Cây

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

huunguyen · Last updated 3, Tháng 4, 2026, 20:31

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 loại cây thường gặp

Cấu trúc	Mục đích chính	Độ phức tạp
BST / AVL / Red-Black Tree	Tập hợp có thứ tự	$O (\log N)$
Treap	BST linh hoạt với split/merge	$O (\log N)$
Segment Tree	Truy vấn và cập nhật đoạn	$O (\log N)$
Fenwick Tree (BIT)	Prefix sum, cập nhật điểm	$O (\log N)$
Heap	Hàng đợi ưu tiên	$O (\log N)$
Trie	Lưu và tìm kiếm xâu/số	$O (\| s \|)$

Child pages

Bình luận

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

Cây