🌳 Cây (Tree)

Mảng và linked list đều là cấu trúc tuyến tính - mỗi phần tử có nhiều nhất một “phần tử tiếp theo”. Nhưng nhiều dữ liệu trong đời sống có tính phân cấp: cây thư mục trên máy tính, sơ đồ tổ chức công ty, cây phả hệ gia đình - mỗi mục có thể có nhiều mục con. Cây (tree) là cấu trúc dữ liệu mô hình hóa chính xác kiểu quan hệ “một cha, nhiều con” này.

Binary tree là gì?

Cây nhị phân (binary tree) là dạng cây đơn giản và phổ biến nhất, trong đó mỗi node có tối đa 2 con - thường gọi là con trái và con phải.

class TreeNode:
    def __init__(self, val):
        self.val = val
        self.left = None    # con trái
        self.right = None   # con phải

Vài thuật ngữ hay dùng: root là node trên cùng (không có cha); leaf là node không có con nào; height của cây là số cạnh dài nhất từ root xuống một leaf; depth của một node là số cạnh từ root đến node đó.

Các kiểu duyệt cây

Vì cây không có thứ tự “tuyến tính” tự nhiên như mảng, có nhiều cách hợp lệ để “đi qua” tất cả các node. Chia làm hai nhóm lớn:

Duyệt theo chiều sâu (DFS) - đi sâu hết một nhánh trước khi quay lại nhánh khác, cài đặt tự nhiên bằng đệ quy. Ba biến thể khác nhau ở thời điểm “xử lý” node gốc so với hai cây con:

def preorder(node, res):    # gốc -> trái -> phải
    if node is None: return
    res.append(node.val)
    preorder(node.left, res)
    preorder(node.right, res)

def inorder(node, res):     # trái -> gốc -> phải
    if node is None: return
    inorder(node.left, res)
    res.append(node.val)
    inorder(node.right, res)

def postorder(node, res):   # trái -> phải -> gốc
    if node is None: return
    postorder(node.left, res)
    postorder(node.right, res)
    res.append(node.val)

Duyệt theo chiều rộng (BFS / level-order) - đi từng tầng một, từ trái sang phải, dùng một hàng đợi (queue) để nhớ “node nào cần ghé tiếp theo”:

from collections import deque

def level_order(root):
    if root is None:
        return []
    queue = deque([root])
    res = []
    while queue:
        node = queue.popleft()
        res.append(node.val)
        if node.left: queue.append(node.left)
        if node.right: queue.append(node.right)
    return res

Chọn kiểu duyệt nào tùy vào bài toán: inorder hữu ích khi cây có tính thứ tự (xem phần BST bên dưới); postorder phù hợp khi cần xử lý con trước cha (ví dụ tính kích thước thư mục từ file con lên); BFS phù hợp khi cần tìm đường đi ngắn nhất tính theo số cạnh, hoặc xử lý cây theo từng tầng.

Biểu diễn cây bằng mảng

Ngoài cách dùng con trỏ left/right, một cây nhị phân hoàn chỉnh (complete binary tree - các tầng đều đầy, trừ tầng cuối lấp từ trái sang phải) có thể lưu gọn trong một mảng phẳng, không cần con trỏ: nếu node đang ở chỉ số i, con trái nằm ở chỉ số 2i + 1, con phải ở 2i + 2.

# arr[i] là node, arr[2i+1] là con trái, arr[2i+2] là con phải
arr = [1, 2, 3, 4, 5, 6, 7]
#          1
#        /   \
#       2     3
#      / \   / \
#     4   5 6   7

Cách này tiết kiệm bộ nhớ (không cần lưu con trỏ) và tận dụng tính cục bộ của mảng trong cache CPU, nhưng chỉ hiệu quả khi cây gần như đầy đủ - cây “lệch” (nhiều node chỉ có 1 con) sẽ để lại rất nhiều ô trống trong mảng, lãng phí bộ nhớ. Đây chính là cách heap (trang tiếp theo) luôn được cài đặt.

Cây tìm kiếm nhị phân (BST)

Binary Search Tree (BST) là một binary tree tuân theo một quy tắc sắp xếp: với mọi node, giá trị các node bên trái nhỏ hơn giá trị node đó, và giá trị các node bên phải lớn hơn. Quy tắc này áp dụng đệ quy cho mọi cây con.

Nhờ tính chất này, tìm kiếm trên BST hoạt động giống hệt binary search trên mảng đã sắp xếp: so sánh giá trị cần tìm với node hiện tại, rồi chỉ đi tiếp về một phía (trái nếu nhỏ hơn, phải nếu lớn hơn) - mỗi bước loại bỏ toàn bộ nhánh còn lại.

def search(root, target):
    cur = root
    while cur is not None:
        if target < cur.val:
            cur = cur.left
        elif target > cur.val:
            cur = cur.right
        else:
            return cur          # tìm thấy
    return None                  # không có trong cây

Thêm node cũng theo logic tương tự - đi xuống theo đúng quy tắc so sánh cho tới khi gặp một chỗ trống rồi gắn node mới vào đó. Xóa node phức tạp hơn một chút, chia làm 3 trường hợp:

Node cần xóa không có con - xóa trực tiếp.
Node có đúng 1 con - cho con đó “thế chỗ” node bị xóa.
Node có 2 con - không thể xóa trực tiếp mà không phá vỡ tính chất BST. Giải pháp: tìm node nhỏ nhất trong cây con bên phải (hoặc lớn nhất bên trái) - đây chính là “người kế nhiệm” hợp lệ duy nhất - copy giá trị của nó lên node cần xóa, rồi xóa node kế nhiệm đó (lúc này chắc chắn có tối đa 1 con, quay về hai trường hợp trên).

Cả ba thao tác tìm/thêm/xóa đều chạy tỷ lệ với chiều cao của cây. Nếu cây “cân đối” (mỗi node có số node ở hai nhánh xấp xỉ nhau), chiều cao chỉ khoảng log n, cho độ phức tạp O(log n) - tốt. Nhưng nếu liên tục chèn dữ liệu theo thứ tự đã sắp (ví dụ 1, 2, 3, 4, 5…), cây sẽ lệch hẳn về một phía và suy biến thành linked list, độ phức tạp rơi về O(n) - mất hết lợi thế của BST.