Cây tìm kiếm nhị phân (BST): cách hoạt động, code và độ phức tạp

Cây tìm kiếm nhị phân giải quyết vấn đề gì

Mảng đã sắp xếp cho phép tìm nhị phân nhanh, nhưng chèn một phần tử mới làm dịch mọi phần tử phía sau. Bảng băm tra cứu và chèn nhanh, nhưng không giữ thứ tự, nên không trả lời được "khóa nhỏ nhất lớn hơn 42 là gì?" hay "liệt kê mọi khóa từ 10 đến 20". Cây tìm kiếm nhị phân giữ các khóa được sắp xếp mà vẫn chèn và xóa nhanh. Nó là nền tảng của map và set có thứ tự như TreeMap của Java và std::map của C++, vốn dùng các biến thể tự cân bằng.

Quy tắc giải thích đơn giản

Mỗi node có một khóa, một con trái tùy chọn và một con phải tùy chọn. Với mọi node: tất cả khóa trong cây con trái đều nhỏ hơn, và tất cả khóa trong cây con phải đều lớn hơn. Để tìm một khóa, bắt đầu từ gốc và so sánh: đi trái nếu khóa nhỏ hơn, đi phải nếu lớn hơn, dừng nếu bằng hoặc khi rơi ra ngoài cây.

Ví dụ minh họa: xây dựng và tìm kiếm trên cây

Chèn lần lượt 8, 3, 10, 1, 6, 14, 4. Mỗi khóa mới đi xuống từ gốc và trở thành một lá tại chỗ nó rơi ra ngoài cây.

Tìm 4 phải so sánh với 8, 3, 6, rồi 4: bốn lần so sánh trong cây có bảy khóa. Tìm 7 so sánh với 8, 3, 6 rồi thấy 6 không có con phải, nên 7 không có trong cây.

Cài đặt bằng Python

Chèn và tìm là các vòng lặp ngắn. Xóa có ba trường hợp: node không có con (xóa luôn), có một con (thay bằng con đó), hoặc có hai con (chép vào node kế nhiệm theo trung thứ tự, tức khóa nhỏ nhất của cây con phải, rồi xóa node kế nhiệm đó).

class Node:
    def __init__(self, key):
        self.key, self.left, self.right = key, None, None
def insert(root, key):
    if root is None:
        return Node(key)
    if key < root.key:
        root.left = insert(root.left, key)
    elif key > root.key:
        root.right = insert(root.right, key)
    return root                      # duplicates are ignored
def contains(root, key):
    while root and root.key != key:
        root = root.left if key < root.key else root.right
    return root is not None
def delete(root, key):
    if root is None:
        return None
    if key < root.key:
        root.left = delete(root.left, key)
    elif key > root.key:
        root.right = delete(root.right, key)
    else:
        if root.left is None:
            return root.right
        if root.right is None:
            return root.left
        succ = root.right
        while succ.left:
            succ = succ.left
        root.key = succ.key
        root.right = delete(root.right, succ.key)
    return root
def inorder(root):
    return inorder(root.left) + [root.key] + inorder(root.right) if root else []

root = None
for k in [8, 3, 10, 1, 6, 14, 4]:
    root = insert(root, k)
print(inorder(root))                 # [1, 3, 4, 6, 8, 10, 14]
print(contains(root, 4), contains(root, 7))  # True False
root = delete(root, 3)               # node with two children
print(inorder(root), root.left.key)  # [1, 4, 6, 8, 10, 14] 4

Độ phức tạp thời gian và không gian

Trường hợp xấu nhất là có thật, không chỉ trên lý thuyết: chèn các khóa đã sắp xếp (1, 2, 3, ...) vào một BST thường làm mỗi node chỉ có con phải, và cây thành danh sách liên kết. Thứ tự chèn ngẫu nhiên cho chiều cao kỳ vọng O(log n).

Các biến thể cân bằng và lỗi thường gặp

Cây tự cân bằng giữ chiều cao ở mức O(log n) bằng cách cấu trúc lại bằng các phép xoay sau khi chèn và xóa.

• Kiểm tra BST chỉ bằng cách so cha và con. Hãy truyền xuống một khoảng (low, high) hợp lệ.
• Quên trả về gốc (có thể là gốc mới) từ chèn và xóa đệ quy, nên các thay đổi bị mất.
• Đệ quy sâu trên cây suy biến: giới hạn đệ quy mặc định của Python khoảng 1000, nên một chuỗi 5000 node sẽ làm code đệ quy lỗi. Hãy dùng vòng lặp hoặc giữ cây cân bằng.
• Không quy định cách xử lý khóa trùng: hãy quyết định trùng sẽ bị bỏ qua, được đếm, hay luôn đi về một bên.

Khi nào dùng BST và các câu hỏi phỏng vấn điển hình

Dùng BST cân bằng khi bạn cần dữ liệu có thứ tự với chèn và xóa thường xuyên: truy vấn khoảng, tìm floor và ceiling, thống kê hạng, hoặc duyệt theo thứ tự đã sắp xếp. Dùng bảng băm khi chỉ cần tra cứu đúng khóa. Thư viện chuẩn của Python không có tree map; lựa chọn phổ biến là danh sách đã sắp xếp với mô-đun bisect cho dữ liệu nhỏ hoặc gần như tĩnh, hoặc gói bên thứ ba sortedcontainers.

Câu hỏi phỏng vấn điển hình: kiểm tra một BST, tìm phần tử nhỏ thứ k (duyệt trung thứ tự), tổ tiên chung thấp nhất, chuyển mảng đã sắp xếp thành BST cân bằng (chọn phần tử giữa làm gốc), và tìm node kế nhiệm trung thứ tự của một node.