Cây (Trees)¶

Cây là cấu trúc dữ liệu phân cấp đằng sau hệ thống tệp, cơ sở dữ liệu, trình biên dịch, và vô số bài toán phỏng vấn. Tệp này trình bày cây nhị phân, BST, cây cân bằng, trie, cây phân đoạn, cây Fenwick, và Union-Find, kèm theo các mẫu duyệt, tư duy đệ quy, và các bài toán tăng dần độ khó.

Một cây (tree) là một đồ thị liên thông, không chu trình (chương 13). Biến thể quan trọng nhất là cây nhị phân (binary tree): mỗi node có nhiều nhất hai con (trái và phải). Cây xuất hiện ở khắp mọi nơi: cây phân tích trong trình biên dịch, cây DOM trong trình duyệt, cây quyết định trong ML, và B-tree trong cơ sở dữ liệu.
Hiểu biết then chốt cho các bài toán về cây: hầu hết bài toán về cây được giải đệ quy. Cấu trúc là đệ quy (một cây là một gốc với hai cây con), nên lời giải cũng nên vậy. Nắm vững khuôn mẫu "giải cho cây con trái, giải cho cây con phải, kết hợp" và bạn có thể giải hầu hết bài toán về cây.

Các phép Duyệt Cây nhị phân (Binary Tree Traversals)¶

Có bốn cách chuẩn để thăm mọi node:
- Inorder (trái, gốc, phải): với BST, cách này thăm các node theo thứ tự đã sắp xếp.
- Preorder (gốc, trái, phải): hữu ích cho tuần tự hóa và sao chép cây.
- Postorder (trái, phải, gốc): hữu ích cho xóa và tính kích thước.
- Level-order (BFS): thăm các node từng cấp bằng hàng đợi.

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def inorder(root):
    if not root:
        return []
    return inorder(root.left) + [root.val] + inorder(root.right)

def preorder(root):
    if not root:
        return []
    return [root.val] + preorder(root.left) + preorder(root.right)

def postorder(root):
    if not root:
        return []
    return postorder(root.left) + postorder(root.right) + [root.val]

from collections import deque

def level_order(root):
    if not root:
        return []
    result, queue = [], deque([root])
    while queue:
        level = []
        for _ in range(len(queue)):
            node = queue.popleft()
            level.append(node.val)
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        result.append(level)
    return result

Cạm bẫy: các phép duyệt đệ quy trên tạo danh sách mới ở mỗi bước (do nối +), tốn \(O(n^2)\). Để hiệu quả, hãy truyền một danh sách kết quả và thêm vào tại chỗ:

def inorder_efficient(root, result=None):
    if result is None:
        result = []
    if root:
        inorder_efficient(root.left, result)
        result.append(root.val)
        inorder_efficient(root.right, result)
    return result

Dễ: Độ sâu Lớn nhất của Cây nhị phân¶

def max_depth(root):
    if not root:
        return 0
    return 1 + max(max_depth(root.left), max_depth(root.right))

Khuôn mẫu đệ quy: trường hợp cơ sở (null → 0), đệ quy trên các con, kết hợp (1 + max). Cùng một khuôn mẫu này áp dụng cho hàng chục bài toán về cây.

Dễ: Đảo ngược Cây nhị phân (Invert Binary Tree)¶

def invert_tree(root):
    if not root:
        return None
    root.left, root.right = invert_tree(root.right), invert_tree(root.left)
    return root

Trung bình: Tổ tiên Chung Thấp nhất (Lowest Common Ancestor)¶

Bài toán: tìm node thấp nhất là tổ tiên của cả \(p\) và \(q\).
Mẫu: nếu cả \(p\) và \(q\) đều ở cây con trái, LCA nằm trong cây con trái. Nếu cả hai ở phải, nó nằm trong cây con phải. Nếu chúng tách nhau (một trái, một phải), node hiện tại là LCA.

def lowest_common_ancestor(root, p, q):
    if not root or root == p or root == q:
        return root

    left = lowest_common_ancestor(root.left, p, q)
    right = lowest_common_ancestor(root.right, p, q)

    if left and right:
        return root  # p và q ở hai cây con khác nhau
    return left if left else right

Cạm bẫy: cách này giả định \(p\) và \(q\) đều tồn tại trong cây. Nếu chúng có thể không tồn tại, bạn cần các kiểm tra bổ sung.

Khó: Tổng Đường đi Lớn nhất trên Cây nhị phân¶

Bài toán: tìm tổng đường đi lớn nhất giữa bất kỳ hai node nào (đường đi không cần đi qua gốc).

def max_path_sum(root):
    best = [float('-inf')]

    def dfs(node):
        if not node:
            return 0
        left = max(dfs(node.left), 0)   # bỏ qua các đường đi âm
        right = max(dfs(node.right), 0)

        # đường đi qua node này (có thể là "đỉnh gập")
        best[0] = max(best[0], node.val + left + right)

        # trả về độ lợi lớn nhất node này có thể đóng góp cho cha nó
        return node.val + max(left, right)

    dfs(root)
    return best[0]

Hiểu biết then chốt: tại mỗi node, có hai câu hỏi: (1) đường đi tốt nhất đi qua node này là gì (trái + node + phải)? (2) đường đi tốt nhất node này có thể đóng góp cho cha nó là gì (node + max(trái, phải), vì một đường đi không thể chia nhánh ở hai cấp)? Nhầm lẫn hai cái này là lỗi sai lầm phổ biến nhất.

Cây Tìm kiếm Nhị phân (Binary Search Trees — BSTs)¶

Một BST thỏa mãn: với mọi node, mọi giá trị trong cây con trái đều nhỏ hơn, mọi giá trị trong cây con phải đều lớn hơn. Điều này cho phép tìm kiếm, chèn, xóa \(O(\log n)\) (khi cân bằng).

def search_bst(root, target):
    if not root:
        return None
    if target < root.val:
        return search_bst(root.left, target)
    elif target > root.val:
        return search_bst(root.right, target)
    else:
        return root

def insert_bst(root, val):
    if not root:
        return TreeNode(val)
    if val < root.val:
        root.left = insert_bst(root.left, val)
    else:
        root.right = insert_bst(root.right, val)
    return root

Cạm bẫy: các thao tác BST chỉ là \(O(\log n)\) khi cây được cân bằng. Một BST xây từ các lần chèn đã sắp xếp sẽ suy biến thành danh sách liên kết: \(O(n)\) mỗi thao tác. Đó là lý do các BST cân bằng (AVL, đỏ-đen) tồn tại.

Trung bình: Kiểm tra Cây Tìm kiếm Nhị phân hợp lệ¶

def is_valid_bst(root, lo=float('-inf'), hi=float('inf')):
    if not root:
        return True
    if root.val <= lo or root.val >= hi:
        return False
    return (is_valid_bst(root.left, lo, root.val) and
            is_valid_bst(root.right, root.val, hi))

Cạm bẫy: chỉ kiểm tra left.val < root.val < right.val là sai. Ràng buộc là mọi node trong cây con trái đều nhỏ hơn, không chỉ con trực tiếp. Các giới hạn lo/hi lan truyền ràng buộc này xuống dưới.

Trung bình: Phần tử Nhỏ thứ K trong một BST¶

Mẫu: duyệt inorder một BST thăm các node theo thứ tự đã sắp xếp. Node thứ \(k\) được thăm là đáp án.

def kth_smallest(root, k):
    count = [0]
    result = [None]

    def inorder(node):
        if not node or result[0] is not None:
            return
        inorder(node.left)
        count[0] += 1
        if count[0] == k:
            result[0] = node.val
            return
        inorder(node.right)

    inorder(root)
    return result[0]

Trie (Cây Tiền tố — Prefix Trees)¶

Một trie lưu các chuỗi từng ký tự một trong một cây. Mỗi cạnh đại diện cho một ký tự, và các đường đi từ gốc đến các node được đánh dấu đại diện cho các chuỗi đã lưu. Trie cho phép tra cứu \(O(L)\) với \(L\) là độ dài chuỗi, bất kể có bao nhiêu chuỗi được lưu.

class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_end = False

class Trie:
    def __init__(self):
        self.root = TrieNode()

    def insert(self, word):
        node = self.root
        for char in word:
            if char not in node.children:
                node.children[char] = TrieNode()
            node = node.children[char]
        node.is_end = True

    def search(self, word):
        node = self.root
        for char in word:
            if char not in node.children:
                return False
            node = node.children[char]
        return node.is_end

    def starts_with(self, prefix):
        node = self.root
        for char in prefix:
            if char not in node.children:
                return False
            node = node.children[char]
        return True

Khi nào dùng: autocomplete, kiểm tra chính tả, trò chơi chữ, bảng định tuyến IP. Bất cứ khi nào bạn cần các thao tác dựa trên tiền tố.

Khó: Word Search II¶

Bài toán: cho một bảng các ký tự và một danh sách từ, tìm mọi từ có thể được tạo bằng cách đi qua các ô kề nhau.
Mẫu: xây một trie từ danh sách từ, rồi DFS từ mỗi ô dùng trie để cắt tỉa các nhánh sớm (nếu không có từ nào bắt đầu bằng tiền tố hiện tại, dừng lại).
Cạm bẫy: không có trie, bạn sẽ DFS cho mỗi từ riêng biệt: \(O(w \cdot m \cdot n \cdot 4^L)\). Trie chia sẻ tính toán tiền tố giữa các từ, giảm thiểu đáng kể công việc.

Union-Find (Disjoint Set Union — Tập hợp không giao nhau)¶

Union-Find theo dõi một tập hợp các tập hợp rời nhau. Hai thao tác: find(x) trả về đại diện của tập hợp chứa \(x\), và union(x, y) trộn các tập hợp chứa \(x\) và \(y\).

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * n
        self.count = n  # số thành phần liên thông

    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])  # nén đường đi
        return self.parent[x]

    def union(self, x, y):
        rx, ry = self.find(x), self.find(y)
        if rx == ry:
            return False  # đã liên thông
        # union by rank
        if self.rank[rx] < self.rank[ry]:
            rx, ry = ry, rx
        self.parent[ry] = rx
        if self.rank[rx] == self.rank[ry]:
            self.rank[rx] += 1
        self.count -= 1
        return True

Với nén đường đi và union by rank, cả hai thao tác chạy trong \(O(\alpha(n)) \approx O(1)\) phân bổ (Ackermann nghịch đảo, thực tế là hằng số).
Khi nào dùng: các thành phần liên thông, phát hiện chu trình trong đồ thị vô hướng, MST của Kruskal, nhóm các mục tương đương.

Trung bình: Số lượng Thành phần Liên thông¶

def count_components(n, edges):
    uf = UnionFind(n)
    for u, v in edges:
        uf.union(u, v)
    return uf.count

Trung bình: Kết nối Dư thừa (Redundant Connection)¶

Bài toán: tìm cạnh mà, khi bị xóa, làm cho đồ thị thành một cây (nghĩa là cạnh tạo ra chu trình).
Mẫu: xử lý các cạnh từng cái một. Cạnh đầu tiên mà cả hai đầu mút đã ở trong cùng một thành phần tạo ra chu trình.

def find_redundant(edges):
    uf = UnionFind(len(edges) + 1)
    for u, v in edges:
        if not uf.union(u, v):
            return [u, v]  # đã liên thông → cạnh này tạo ra chu trình

Cây Phân đoạn (Segment Trees) và Cây Fenwick¶

Cây phân đoạn (Segment trees) trả lời các truy vấn trên một đoạn (tổng, min, max trên một mảng con) và hỗ trợ cập nhật điểm, cả hai trong \(O(\log n)\).
Cây Fenwick (Binary Indexed Trees) là một lựa chọn đơn giản, nhanh hơn cho các truy vấn tổng tiền tố và cập nhật điểm. Chúng dùng một mẹo thao tác bit khéo léo: mỗi vị trí lưu một tổng một phần bao phủ một phạm vi được xác định bởi bit được bật thấp nhất.

class FenwickTree:
    def __init__(self, n):
        self.n = n
        self.tree = [0] * (n + 1)

    def update(self, i, delta):
        i += 1  # đánh chỉ số từ 1
        while i <= self.n:
            self.tree[i] += delta
            i += i & (-i)  # cộng bit được bật thấp nhất

    def prefix_sum(self, i):
        i += 1
        total = 0
        while i > 0:
            total += self.tree[i]
            i -= i & (-i)  # bớt đi bit được bật thấp nhất
        return total

    def range_sum(self, l, r):
        return self.prefix_sum(r) - (self.prefix_sum(l - 1) if l > 0 else 0)

Khi nào dùng: các bài toán đòi hỏi các truy vấn trên đoạn lặp đi lặp lại kèm cập nhật. Cây Fenwick được ưu tiên khi bạn chỉ cần tổng tiền tố; cây phân đoạn khi bạn cần các thao tác trên đoạn tùy ý (min, max, GCD).

Tóm tắt các Cạm bẫy Thường gặp¶

Cạm bẫy	Ví dụ	Sửa
Chỉ kiểm tra con trực tiếp cho BST	`left.val < root.val` bỏ sót các vi phạm sâu hơn	Truyền các giới hạn `lo`/`hi`
Nối danh sách \(O(n^2)\) trong đệ quy	`inorder(left) + [val] + inorder(right)`	Thêm vào danh sách dùng chung
Quên trường hợp cơ sở	Đệ quy vô hạn trên cây rỗng	`if not root: return`
Nhầm đường-qua so với đường-đến-cha	Tổng đường đi lớn nhất: chia nhánh ở hai cấp	Trả về một nhánh đến cha, theo dõi hai nhánh riêng
Fenwick 1-indexed so với 0-indexed	Lệch một đơn vị trong mảng cây	Luôn `i += 1` khi nhập
Union-Find không nén đường đi	\(O(n)\) mỗi lần find trong trường hợp xấu nhất	`self.parent[x] = self.find(self.parent[x])`

Bài tập Tự luyện (NeetCode)¶

Các Mẫu Cây nhị phân¶

Invert Binary Tree — đệ quy cơ bản
Maximum Depth of Binary Tree — độ sâu đệ quy
Same Tree — duyệt đồng thời
Subtree of Another Tree — đệ quy lồng nhau
Binary Tree Level Order Traversal — BFS kèm theo dõi cấp
Binary Tree Maximum Path Sum — DFS với best toàn cục
Serialize and Deserialize Binary Tree — preorder + cờ null

Các Mẫu BST¶

Validate Binary Search Tree — lan truyền giới hạn
Kth Smallest Element in a BST — duyệt inorder
Lowest Common Ancestor of a BST — khai thác thứ tự BST

Trie¶

Implement Trie — các thao tác trie cơ bản
Design Add and Search Words — trie + DFS với ký tự đại diện
Word Search II — quay lui dẫn hướng bởi trie

Union-Find¶

Number of Connected Components — union-find cơ bản
Redundant Connection — phát hiện chu trình qua union-find