Cấu trúc dữ liệu và Giải thuật Bài 41: Cây Nhị Phân Tìm Kiếm (Binary Search Tree - BST) và sức mạnh của O(log n).

Trong thế giới của Cấu trúc dữ liệu, chúng ta luôn bị kẹt giữa một sự đánh đổi nghiệt ngã:

• Nếu dùng Mảng đã sắp xếp (Sorted Array): Việc tìm kiếm cực kỳ nhanh nhờ Binary Search ($O(\log n)$), nhưng mỗi lần thêm một phần tử mới, bạn phải dời toàn bộ mảng mất $O(n)$.

• Nếu dùng Danh sách liên kết (Linked List): Việc chèn một phần tử mới diễn ra chớp nhoáng ($O(1)$), nhưng để tìm xem phần tử đó nằm ở đâu, bạn phải lội bộ từ đầu đến cuối mất $O(n)$.

Liệu có cỗ máy nào kết hợp được tốc độ tìm kiếm $O(\log n)$ của Mảng và tốc độ chèn linh hoạt của Danh sách liên kết? Câu trả lời chính là việc áp đặt một đạo luật phân bổ dữ liệu nghiêm ngặt lên cấu trúc Cây Nhị Phân, tạo ra Cây Nhị Phân Tìm Kiếm (Binary Search Tree - BST).

1. Đạo luật Vàng của BST

Một Cây Nhị Phân thông thường (ở Bài 40) cho phép bạn đặt dữ liệu ngẫu nhiên ở bất kỳ Node nào. Nhưng BST thì không. Để được công nhận là một BST hợp lệ, mọi Node trên cây đều phải tuyệt đối tuân thủ đạo luật phân chia lãnh thổ sau:

1. Nhánh Trái nhỏ hơn: Tất cả các Node nằm trong cây con bên TRÁI phải có giá trị nhỏ hơn Node cha.

2. Nhánh Phải lớn hơn: Tất cả các Node nằm trong cây con bên PHẢI phải có giá trị lớn hơn Node cha.

3. Quy luật này có tính đệ quy, nghĩa là nó áp dụng cho mọi Node trên cây, không chỉ riêng Node Gốc (Root).

Nhờ quy luật này, nếu bạn áp dụng phép duyệt In-order (Trái $\rightarrow$ Gốc $\rightarrow$ Phải) lên một BST, dữ liệu in ra chắc chắn sẽ tạo thành một dãy số tăng dần hoàn hảo.

2. Phép màu của không gian $O(\log n)$

Bản chất của thuật toán tìm kiếm trên BST giống hệt như trò chơi "Đoán số từ 1 đến 100".

Giả sử bạn cần tìm số 25. Đứng ở Gốc cây (có giá trị là 50).

• Vì 25 < 50, bạn biết chắc chắn 100% rằng số 25 (nếu tồn tại) chỉ có thể nằm bên nhánh Trái.

• Toàn bộ nhánh Phải (chứa các số từ 51 đến 100) lập tức bị vứt bỏ mà không cần tốn một phép so sánh nào.

Mỗi khi bạn bước xuống một tầng của cây, một nửa không gian dữ liệu bị loại bỏ. Nếu cây có 1 triệu Node, bạn chỉ mất tối đa 20 phép so sánh (vì $2^{20} \approx 1,000,000$) để tìm ra dữ liệu. Tốc độ này gọi là $O(\log n)$, nhanh đến mức gần như không thể cảm nhận được độ trễ so với việc phải quét $O(n)$ qua 1 triệu phần tử.

3. Triển khai BST bằng Golang

Khác với các phép duyệt bài trước dùng Đệ quy, thao tác Tìm kiếm (Search) và Chèn (Insert) trên BST có thể được viết bằng vòng lặp for rất tự nhiên, giúp tiết kiệm không gian Call Stack của CPU.

Go

type TreeNode struct {
    Val   int
    Left  *TreeNode
    Right *TreeNode
}

// Thao tác Tìm kiếm (Search)
func searchBST(root *TreeNode, target int) *TreeNode {
    current := root
    for current != nil {
        if current.Val == target {
            return current // Tìm thấy
        } else if target < current.Val {
            current = current.Left // Rẽ trái
        } else {
            current = current.Right // Rẽ phải
        }
    }
    return nil // Đi đến tận cùng (nil) mà vẫn không thấy
}

// Thao tác Chèn (Insert)
func insertBST(root *TreeNode, val int) *TreeNode {
    newNode := &TreeNode{Val: val}
    
    // Nếu cây rỗng, Node mới chính là Root
    if root == nil {
        return newNode
    }
    
    current := root
    for {
        if val < current.Val {
            // Rẽ trái
            if current.Left == nil {
                current.Left = newNode // Tìm thấy chỗ trống, cắm Node mới vào
                break
            }
            current = current.Left
        } else {
            // Rẽ phải
            if current.Right == nil {
                current.Right = newNode // Tìm thấy chỗ trống, cắm Node mới vào
                break
            }
            current = current.Right
        }
    }
    return root
}

4. Gót chân Achilles: Hiện tượng Suy biến (Skewed Tree)

Mặc dù mang danh là cấu trúc $O(\log n)$, BST ẩn chứa một lỗ hổng vật lý nghiêm trọng.

Điều gì xảy ra nếu bạn chèn vào BST một tập dữ liệu đã được sắp xếp sẵn (Ví dụ: 1, 2, 3, 4, 5)?

• Chèn 1: Root là 1.

• Chèn 2: Lớn hơn 1 $\rightarrow$ Rẽ phải.

• Chèn 3: Lớn hơn 2 $\rightarrow$ Rẽ phải tiếp.

Lúc này, Cây Nhị Phân không còn phân nhánh nữa. Nó mọc thẳng tắp về một phía và suy biến hoàn toàn thành một Danh sách liên kết (Linked List). Chiều cao của cây $H$ lúc này bằng đúng $N$. Mọi thao tác Search hay Insert lại trở về thảm họa $O(n)$.

5. Ứng dụng ở tầng Kiến trúc Hệ thống (Database Indexes)

Bất chấp lỗ hổng suy biến, tư duy của Cây tìm kiếm là nền móng định hình toàn bộ nền công nghiệp Cơ sở dữ liệu:

• MySQL / PostgreSQL (B-Tree & B+Tree): Khi bạn dùng lệnh CREATE INDEX trên một cột trong Laravel/Eloquent, DB Engine không quét tuần tự các dòng. Nó tạo ra một cấu trúc B+Tree (một phiên bản đa phân, cấp thấp và hoàn thiện hơn của BST). Việc tìm một user_id giữa 100 triệu record diễn ra trong vài phần nghìn giây chính là nhờ các nhánh cây rẽ hướng liên tục vứt bỏ dữ liệu không liên quan này.

• Bộ định tuyến mạng (Routing Tables): Các thuật toán tìm kiếm địa chỉ IP dài nhất (Longest Prefix Match) trong hạ tầng mạng lõi sử dụng một dạng cây tìm kiếm (Trie) để điều hướng gói tin nhanh chóng thay vì tìm kiếm tuyến tính trên hàng triệu dải IP.

Để khắc phục gót chân Achilles của BST, các nhà khoa học máy tính không thể trông chờ vào việc dữ liệu đầu vào luôn ngẫu nhiên. Họ đã thiết kế ra các bộ "giảm xóc" tự động ngay bên trong cấu trúc của Node, giúp cái cây có khả năng tự xoắn lại và dàn đều trọng lượng sang hai bên mỗi khi phát hiện sự mất cân đối.