Thuật toán 4 — Cây, cây tìm kiếm & heap

Ở bài Cấu trúc dữ liệu chúng ta làm việc với những cấu trúc tuyến tính: mảng, danh sách liên kết, ngăn xếp, hàng đợi — dữ liệu xếp thành một dãy. Nhưng thế giới thực hiếm khi phẳng. Sơ đồ tổ chức ngân hàng có cấp trên và cấp dưới; hệ thống thư mục có folder lồng folder; một câu truy vấn muốn tìm nhanh khách hàng theo CIF phải "nhảy" qua hàng triệu bản ghi mà không quét tuần tự. Đó là lúc cấu trúc phân cấp (hierarchical) và cấu trúc ưu tiên (priority) lên tiếng.

Bài này đi qua bốn nhân vật chính: cây (tree) và cây nhị phân, cây tìm kiếm nhị phân (BST), cây cân bằng (AVL/Red-Black và đặc biệt là B-tree — nền của index cơ sở dữ liệu), và heap / hàng đợi ưu tiên cho bài toán top-K và lập lịch. Cuối cùng là trie cho tìm kiếm theo tiền tố. Tất cả minh hoạ bằng Python, gắn với use case dữ liệu và ngân hàng.

1. Cây (tree) — khi dữ liệu có cấp bậc

Cây là tập hợp các node nối với nhau, trong đó mỗi node (trừ node gốc) có đúng một node cha. Vài thuật ngữ cần nắm:

• Root (gốc): node trên cùng, không có cha.
• Leaf (lá): node không có con.
• Cha / con (parent/child): quan hệ trực tiếp giữa hai node.
• Độ sâu (depth) của một node: số cạnh từ gốc xuống node đó. Chiều cao (height) của cây: độ sâu lớn nhất.
• Cây con (subtree): một node cùng toàn bộ hậu duệ của nó.

Điểm mấu chốt: cây không có chu trình (nó là một loại đồ thị đặc biệt — xem bài Graphs), và với n node thì có đúng n − 1 cạnh.

Cây nhị phân (binary tree) là cây mà mỗi node có tối đa hai con: con trái và con phải. Đây là mô hình đơn giản nhất nhưng đủ mạnh để xây BST và heap. Biểu diễn một node bằng Python rất tự nhiên:

# (minh hoạ)
class Node:
    def __init__(self, value):
        self.value = value
        self.left = None    # cây con trái
        self.right = None   # cây con phải

Duyệt cây (traversal)

"Duyệt" là đi qua mọi node theo một thứ tự nào đó. Với cây nhị phân có ba kiểu duyệt theo chiều sâu (DFS) và một kiểu theo chiều rộng (BFS):

• In-order (trái → node → phải): với BST, cho ra dãy đã sắp xếp tăng dần.
• Pre-order (node → trái → phải): hữu ích khi cần sao chép cây hoặc ghi cấu trúc ra file (serialize).
• Post-order (trái → phải → node): dùng khi cần xử lý con trước cha, ví dụ giải phóng bộ nhớ, tính kích thước thư mục.
• BFS / level-order: duyệt theo từng tầng, dùng hàng đợi.

# (minh hoạ)
def in_order(node, out):
    if node is None:
        return
    in_order(node.left, out)   # trái
    out.append(node.value)     # node
    in_order(node.right, out)  # phải

from collections import deque

def bfs(root):
    out, q = [], deque([root])
    while q:
        n = q.popleft()
        out.append(n.value)
        if n.left:  q.append(n.left)
        if n.right: q.append(n.right)
    return out

Ý tưởng in/pre/post-order chỉ khác nhau ở chỗ đặt dòng out.append. BFS/DFS được bàn kỹ hơn cho đồ thị tổng quát ở bài Graphs — cây chỉ là trường hợp riêng.

2. BST — cây tìm kiếm nhị phân

Cây nhị phân trở nên hữu ích khi ta áp một quy tắc thứ tự: mọi giá trị trong cây con trái nhỏ hơn node, mọi giá trị trong cây con phải lớn hơn node. Đó là Binary Search Tree (BST). Quy tắc này biến việc tìm kiếm thành một chuỗi quyết định "đi trái hay đi phải" — chính là tìm kiếm nhị phân nhưng trên cấu trúc động, cho phép chèn/xoá mà không phải dịch cả mảng.

Muốn tìm 60: bắt đầu từ 50 → 60 > 50 nên đi phải tới 70 → 60 < 70 nên đi trái tới 60. Ba bước cho cây bảy node.

# (minh hoạ)
def bst_insert(root, value):
    if root is None:
        return Node(value)
    if value < root.value:
        root.left = bst_insert(root.left, value)
    else:
        root.right = bst_insert(root.right, value)
    return root

def bst_search(root, target):
    while root:
        if target == root.value:
            return True
        root = root.left if target < root.value else root.right
    return False

Chi phí: tìm/chèn/xoá đều là O(chiều cao cây). Nếu cây cân bằng, chiều cao ≈ log₂(n) → O(log n), rất nhanh. Nhưng có một cái bẫy chết người: nếu ta chèn dữ liệu đã sắp sẵn (1, 2, 3, 4, …), mỗi node chỉ có con phải — cây suy biến (degenerate) thành một danh sách liên kết, chiều cao = n, mọi thao tác tụt xuống O(n). Đây chính là lý do BST "trần" ít khi được dùng trong sản phẩm thực; thay vào đó người ta dùng cây tự cân bằng.

3. Cây cân bằng: AVL, Red-Black và B-tree

Cây tự cân bằng tự động xoay/tái cấu trúc sau mỗi lần chèn/xoá để giữ chiều cao ≈ O(log n), tránh suy biến.

• AVL tree: cân bằng nghiêm ngặt (chênh lệch chiều cao hai con ≤ 1). Tìm kiếm rất nhanh, nhưng chèn/xoá tốn nhiều thao tác xoay hơn.
• Red-Black tree: cân bằng "lỏng" hơn AVL nên chèn/xoá rẻ hơn một chút. Đây là nền của map/set có thứ tự trong nhiều ngôn ngữ: std::map/std::set của C++, TreeMap/TreeSet của Java. Chúng giữ khoá theo thứ tự và cho phép duyệt theo dãy, tìm khoảng (range query).

Python không có "ordered tree map" tích hợp trong thư viện chuẩn. Ở mục thực hành ta sẽ dùng thư viện sortedcontainers cho nhu cầu tương tự.

B-tree / B+tree — tại sao là "trái tim" của index CSDL

AVL và Red-Black tối ưu cho dữ liệu trong RAM. Nhưng cơ sở dữ liệu lưu index trên đĩa (disk/SSD), nơi mỗi lần đọc là một khối (block/page, thường 4–16 KB) và cực kỳ đắt so với truy cập RAM. Với dữ liệu trên đĩa, câu hỏi quyết định không phải "bao nhiêu phép so sánh?" mà là "bao nhiêu lần đọc đĩa?".

B-tree (và biến thể B+tree) trả lời câu hỏi đó: thay vì mỗi node chỉ có 2 con như BST, mỗi node B-tree chứa hàng trăm khoá và hàng trăm con, vừa khít một page trên đĩa. Kết quả là cây rất thấp và rất rộng.

Con số minh hoạ sự khác biệt (nguồn: use-the-index-luke, Wikipedia): với một triệu bản ghi, một BST cân bằng cần khoảng log₂(1.000.000) ≈ 20 tầng — tức tối đa 20 lần đọc đĩa. Một B-tree với ~100 khoá mỗi node chỉ cần log₁₀₀(1.000.000) ≈ 3 tầng — 3 lần đọc đĩa. Vì mỗi tầng thường tương ứng một lần seek đĩa, B-tree giảm I/O đi cả một bậc độ lớn.

Với B+tree, thêm hai đặc điểm quan trọng cho CSDL: (1) toàn bộ dữ liệu nằm ở tầng lá, node bên trong chỉ chứa khoá dẫn đường; (2) các lá được nối với nhau thành danh sách liên kết, nên range scan ("tất cả giao dịch từ ngày A đến ngày B") chỉ cần tìm điểm đầu rồi đi ngang qua lá — cực nhanh.

Đây chính là index mặc định (USING btree) trong PostgreSQL, MySQL, Oracle. Muốn hiểu index tăng tốc truy vấn ra sao trên thực tế, hãy xem bài Index PostgreSQL — kiến thức về B-tree ở đây là nền lý thuyết cho việc đọc EXPLAIN và quyết định tạo index nào.

4. Heap & hàng đợi ưu tiên

Chuyển sang họ ưu tiên. Nhiều bài toán không cần sắp xếp toàn bộ dữ liệu, mà chỉ cần luôn lấy được phần tử nhỏ nhất (hoặc lớn nhất) hiện tại một cách nhanh chóng. Đó là việc của heap.

Binary heap là cây nhị phân gần hoàn chỉnh (điền đầy từ trái sang phải) thoả tính chất heap:

• Min-heap: mỗi node ≤ các con → gốc là nhỏ nhất.
• Max-heap: mỗi node ≥ các con → gốc là lớn nhất.

Nhờ tính "gần hoàn chỉnh", heap được lưu gọn trong một mảng phẳng: con của node ở chỉ số i nằm ở 2i+1 và 2i+2. Chi phí:

• Lấy phần tử nhỏ/lớn nhất (peek): O(1).
• Chèn (push) và lấy-ra (pop): O(log n).
• Xây heap từ n phần tử có sẵn (heapify): O(n) — nhanh hơn chèn từng cái O(n log n).

heapq trong Python

Thư viện chuẩn heapq biến một list bình thường thành min-heap tại chỗ. Không có class riêng — bạn thao tác trực tiếp trên list.

# (minh hoạ)
import heapq

nums = [5, 1, 8, 3, 9, 2]
heapq.heapify(nums)          # O(n): biến list thành min-heap tại chỗ
print(nums[0])               # 1 -> phần tử nhỏ nhất, O(1)

heapq.heappush(nums, 0)      # O(log n)
smallest = heapq.heappop(nums)  # lấy ra 0, O(log n)

Muốn max-heap? heapq chỉ hỗ trợ min-heap, nên mẹo phổ biến là phủ định giá trị (push -x, pop rồi đảo dấu lại), hoặc dùng cặp (-priority, item).

5. Use case thực tế

Top-K giao dịch bằng heap — vì sao không sort cả bảng

Bài toán quen thuộc trong phân tích dữ liệu: "Tìm 100 giao dịch giá trị lớn nhất trong ngày" từ một luồng hàng chục triệu bản ghi.

Cách ngây thơ: sort toàn bộ n bản ghi rồi lấy 100 phần tử đầu — tốn O(n log n) và phải giữ cả n trong bộ nhớ. Với streaming (dữ liệu chảy liên tục, không nạp hết được) thì cách này bất khả thi.

Cách dùng heap: giữ một min-heap kích thước đúng bằng K = 100. Duyệt từng giao dịch: nếu heap chưa đủ K thì push; nếu đã đủ và giao dịch mới lớn hơn phần tử nhỏ nhất trong heap (chính là heap[0]) thì thay thế nó. Cuối cùng heap chứa đúng top-K. Chi phí O(n log K), bộ nhớ chỉ O(K) — khi K ≪ n thì nhanh hơn hẳn sort O(n log n) và chạy được trên stream.

# (minh hoạ)
import heapq

def top_k_transactions(transactions, k=100):
    """transactions: iterable các (amount, txn_id). Trả về top-K theo amount."""
    heap = []  # min-heap theo amount; heap[0] là 'ngưỡng' nhỏ nhất đang giữ
    for amount, txn_id in transactions:
        if len(heap) < k:
            heapq.heappush(heap, (amount, txn_id))
        elif amount > heap[0][0]:            # lớn hơn ngưỡng -> đáng giữ
            heapq.heapreplace(heap, (amount, txn_id))  # pop nhỏ nhất, push mới
    return sorted(heap, reverse=True)        # sắp K phần tử để trả kết quả

# Cách viết tắt tương đương của thư viện chuẩn, cũng O(n log K):
# heapq.nlargest(100, transactions, key=lambda t: t[0])

heapq.nlargest(k, ...) / nsmallest(k, ...) chính là đóng gói sẵn kỹ thuật này (độ phức tạp O(n log k)) — nên dùng khi không cần logic thay thế thủ công. Cùng ý tưởng áp dụng cho top-N khách hàng theo số dư, N sản phẩm bán chạy, streaming top-N trên dashboard thời gian thực.

Hàng đợi ưu tiên: lập lịch & triage cảnh báo

Một priority queue luôn phục vụ phần tử ưu tiên cao nhất trước, bất kể thứ tự đến — khác với hàng đợi FIFO thường (xem Cấu trúc dữ liệu). Heap là hiện thực tự nhiên của nó.

Use case ngân hàng rõ nhất là triage cảnh báo AML: hệ thống giám sát giao dịch sinh ra hàng nghìn alert mỗi ngày, đội điều tra không thể xử lý theo thứ tự đến. Ta đẩy alert vào priority queue với điểm rủi ro làm độ ưu tiên; điều tra viên luôn nhận alert rủi ro cao nhất trước.

# (minh hoạ)
import heapq
import itertools

class PriorityQueue:
    def __init__(self):
        self._heap = []
        self._counter = itertools.count()  # phá vỡ hoà (tie) theo thứ tự đến

    def push(self, item, priority):
        # priority cao = ưu tiên hơn -> phủ định để dùng min-heap làm max-heap
        heapq.heappush(self._heap, (-priority, next(self._counter), item))

    def pop(self):
        _, _, item = heapq.heappop(self._heap)
        return item

alerts = PriorityQueue()
alerts.push("Alert #A200 (chuyển tiền lớn bất thường)", priority=95)
alerts.push("Alert #A201 (giao dịch nhỏ lặp lại)",      priority=40)
alerts.push("Alert #A202 (khách hàng rủi ro cao)",      priority=88)

print(alerts.pop())  # #A200 -> điểm 95, xử lý trước
print(alerts.pop())  # #A202 -> điểm 88

Lưu ý cái itertools.count(): khi hai phần tử cùng độ ưu tiên, Python sẽ so sánh tiếp phần tử thứ hai của tuple; một số đếm tăng dần bảo đảm so sánh luôn xác định (theo thứ tự đến) và tránh việc phải so sánh trực tiếp item — vốn có thể không so sánh được.

k-way merge: gộp nhiều luồng đã sắp

Khi cần trộn nhiều file/luồng đều đã sắp xếp thành một dãy sắp xếp duy nhất (ví dụ external sort, gộp log theo timestamp từ nhiều node), heap giải quyết trong O(n log k) với k là số luồng: luôn giữ trong heap phần tử nhỏ nhất hiện tại của mỗi luồng, lấy ra cái nhỏ nhất rồi nạp phần tử kế tiếp của đúng luồng đó. Python đóng gói sẵn:

# (minh hoạ)
import heapq

s1 = [1, 4, 7, 10]
s2 = [2, 5, 8]
s3 = [3, 6, 9, 12]

for x in heapq.merge(s1, s2, s3):   # lười (lazy), O(n log k)
    print(x, end=" ")               # 1 2 3 4 5 6 7 8 9 10 12

6. Trie — cây tiền tố cho autocomplete

Trie (cây tiền tố) là cây mà mỗi cạnh mang một ký tự; đường đi từ gốc tới một node đánh dấu tạo thành một chuỗi. Điểm mạnh: tìm/kiểm tra một chuỗi hay liệt kê mọi chuỗi có cùng tiền tố tốn thời gian tỉ lệ với độ dài chuỗi, gần như không phụ thuộc số lượng từ đã lưu.

Use case: autocomplete tên khách hàng (gõ "Ngu" → gợi ý "Nguyễn Văn A", "Nguyễn Thị B"…), gợi ý mã sản phẩm, khớp mã/định tuyến (longest-prefix match cho số tài khoản, mã bưu điện, IP routing).

# (minh hoạ)
class Trie:
    def __init__(self):
        self.children = {}
        self.is_end = False

    def insert(self, word):
        node = self
        for ch in word:
            node = node.children.setdefault(ch, Trie())
        node.is_end = True

    def starts_with(self, prefix):
        node = self
        for ch in prefix:
            if ch not in node.children:
                return False
            node = node.children[ch]
        return True   # có ít nhất một từ mang tiền tố này

Chi tiết về thao tác trên chuỗi (khớp mẫu, biến thể của trie) được bàn kỹ ở bài về xử lý chuỗi trong series; ở đây chỉ cần nắm ý tưởng cấu trúc.

7. Thực tế: dùng gì cho việc gì

• heapq (thư viện chuẩn): mặc định cho mọi nhu cầu heap / priority queue / top-K / k-way merge. Nhớ nó là min-heap; muốn max thì phủ định giá trị.
• sortedcontainers (bên thứ ba): cung cấp SortedList, SortedDict, SortedSet giữ phần tử luôn theo thứ tự với chèn/xoá/tìm O(log n) — thay thế thực dụng cho "ordered tree map" mà Python thiếu, khi bạn cần vừa thứ tự vừa range query trong RAM.
• Cây / B-tree tự cài: hầu như không cần. Với dữ liệu lớn cần index, hãy để cơ sở dữ liệu lo — B-tree đã được cài đặt, tối ưu và kiểm chứng hàng chục năm. Việc của kỹ sư dữ liệu là hiểu B-tree để tạo và tối ưu index đúng chỗ, đọc kế hoạch thực thi, và biết khi nào index không giúp ích.

Ghi nhớ

• Cây mô hình hoá quan hệ phân cấp; cây nhị phân có ba kiểu duyệt DFS (in/pre/post-order) và một kiểu BFS — in-order trên BST cho dãy đã sắp.
• BST cho tìm/chèn/xoá O(log n) khi cân bằng, nhưng suy biến về O(n) nếu dữ liệu vào đã sắp → cần cây tự cân bằng.
• AVL / Red-Black giữ cân bằng trong RAM; Red-Black là nền của map/set có thứ tự ở nhiều ngôn ngữ.
• B-tree / B+tree nhiều con mỗi node → cây thấp → ít lần đọc đĩa → là cấu trúc index của CSDL. Một triệu bản ghi: ~3 tầng thay vì ~20 của BST.
• Heap: peek O(1), push/pop O(log n), heapify O(n). Dùng heapq (min-heap).
• Top-K: giữ heap kích thước K → O(n log K), bộ nhớ O(K), chạy được trên streaming — đừng sort cả tập.
• Priority queue (heap) cho lập lịch / triage theo độ ưu tiên; heapq.merge cho k-way merge.
• Trie cho tìm theo tiền tố / autocomplete, chi phí theo độ dài chuỗi.
• Thực chiến: heapq + sortedcontainers; index thì để CSDL lo, ta hiểu để tối ưu.

Đọc tiếp

• Cấu trúc dữ liệu — mảng, danh sách, ngăn xếp, hàng đợi (nền cho cây & heap).
• Sorting & searching — tìm kiếm nhị phân, tư duy O(log n).
• Graphs — cây là đồ thị đặc biệt; BFS/DFS tổng quát.
• Index PostgreSQL — B-tree index trong thực tế.
• Giám sát giao dịch & AML — nguồn của bài toán triage cảnh báo bằng priority queue.