Cấu trúc dữ liệu và Giải thuật Bài 42: Khắc phục điểm yếu của BST - Cây tự cân bằng (AVL Tree và Red-Black Tree).

Như đã phân tích ở Bài 41, Cây Nhị Phân Tìm Kiếm (BST) nguyên thủy phó mặc số phận của nó cho thứ tự dữ liệu đầu vào. Nếu dữ liệu truyền vào đã được sắp xếp sẵn, cái cây sẽ mọc dài về một phía và thoái hóa thành một Danh sách liên kết, kéo theo hiệu năng giảm thê thảm từ $O(\log n)$ xuống $O(n)$.

Để ngăn chặn thảm họa này, hệ thống cần một cơ chế "giảm xóc" tự động: Cây phải biết tự đo lường độ nghiêng của chính nó và thực hiện các động tác "vặn mình" để dàn đều trọng lượng sang hai bên. Đó là triết lý ra đời của Cây tự cân bằng (Self-Balancing Trees).

1. Trái tim của sự cân bằng: Phép xoay (Tree Rotations)

Khi phát hiện một nhánh quá nặng, cây không thể bốc bừa một Node ném sang nhánh khác, vì làm thế sẽ phá vỡ "Đạo luật vàng" của BST (Trái nhỏ hơn Cha, Phải lớn hơn Cha).

Thay vào đó, nó sử dụng Phép xoay (Rotation). Phép xoay bản chất là thao tác điều hướng lại các con trỏ (giống hệt như bài toán Đảo ngược Linked List), nhằm thay đổi vị trí Gốc (Root) cục bộ nhưng vẫn giữ nguyên thứ tự sắp xếp của dữ liệu.

Có 2 phép xoay cơ bản:

• Xoay Trái (Left Rotation): Áp dụng khi nhánh Phải quá nặng. Node cha sẽ bị "kéo tụt" xuống làm con Trái của Node con Phải. Node con Phải được đôn lên làm cha.

• Xoay Phải (Right Rotation): Áp dụng khi nhánh Trái quá nặng. Đưa Node con Trái lên làm Gốc, đẩy Node cha xuống làm con Phải.

2. Triển khai Phép xoay bằng Golang

Hãy xem một ca "phẫu thuật" con trỏ để Xoay Trái. Sự khéo léo nằm ở chỗ xử lý "Đứa con mồ côi" (nhánh con Trái của Node con Phải).

Go

type TreeNode struct {
    Val   int
    Left  *TreeNode
    Right *TreeNode
    // AVL Tree thường lưu thêm Height, Red-Black Tree lưu thêm Color
}

// Hàm Xoay Trái quanh một Node Gốc (x)
func rotateLeft(x *TreeNode) *TreeNode {
    // y là con phải của x, người sẽ được đôn lên làm Gốc mới
    y := x.Right 
    
    // T2 là nhánh con trái của y (Đứa con mồ côi khi y lên làm Gốc)
    T2 := y.Left 

    // Thực hiện xoay:
    // 1. y đẩy x xuống làm con trái của mình
    y.Left = x 
    
    // 2. x nhận T2 làm con phải mới của mình để lấp chỗ trống
    x.Right = T2 

    // Trả về y làm Gốc mới của cây con này
    return y 
}

Thao tác này chỉ thay đổi đúng 2 con trỏ, tiêu tốn thời gian vật lý $O(1)$ tuyệt đối.

3. Cây AVL: Kỷ luật thép (Cân bằng tuyệt đối)

Được đặt theo tên hai nhà khoa học Adelson-Velsky và Landis, AVL Tree duy trì sự cân bằng bằng một chỉ số gọi là Balance Factor (Hệ số cân bằng).

Hệ số cân bằng = Chiều cao nhánh Trái - Chiều cao nhánh Phải

Luật của AVL: Hệ số cân bằng của mọi Node trên cây chỉ được phép là -1, 0, hoặc 1.

Ngay khi có một thao tác Chèn (Insert) hoặc Xóa (Delete) làm hệ số này vượt ra ngoài ngưỡng (ví dụ +2 hoặc -2), AVL Tree sẽ lập tức kích hoạt các phép Xoay (Xoay Trái, Xoay Phải, hoặc Xoay Kép) để nắn lại cây ngay lập tức.

• Ưu điểm: Cây luôn cực kỳ nông. Tốc độ Tìm kiếm (Read) đạt mức tối ưu nhất có thể.

• Nhược điểm: Kỷ luật quá khắt khe. Nếu hệ thống của bạn liên tục ghi (Write) dữ liệu mới, cây AVL sẽ phải Xoay liên tục, gây tiêu hao tài nguyên CPU khổng lồ.

4. Red-Black Tree: Sự thỏa hiệp hoàn hảo (Cân bằng tương đối)

Để giải quyết bài toán "Xoay quá nhiều" của AVL, Red-Black Tree (Cây Đỏ Đen - RBT) ra đời. Thay vì đo chiều cao chi ly, RBT sơn màu Đỏ hoặc Đen cho từng Node và đưa ra 4 luật lệ mang tính "thỏa hiệp":

1. Mỗi Node chỉ có thể là Đỏ hoặc Đen.

2. Gốc (Root) luôn là Đen.

3. Hai Node Đỏ không bao giờ được phép đứng liền kề nhau (Cha Đỏ thì Con bắt buộc phải Đen).

4. Đi từ bất kỳ Node nào xuống tận cùng (Leaf), số lượng Node Đen đi qua phải luôn bằng nhau.

Nhờ 4 luật lệ này, RBT đảm bảo một tính chất toán học quan trọng: Nhánh dài nhất của cây không bao giờ dài quá gấp đôi nhánh ngắn nhất.

Nó cho phép cây hơi nghiêng một chút, đổi lại, số lần phải kích hoạt Phép xoay khi Chèn/Xóa giảm đi đáng kể so với AVL Tree. RBT mang lại hiệu năng cân bằng tuyệt vời giữa Read và Write, cùng duy trì ở mức $O(\log n)$.

5. Ứng dụng ở tầng Kiến trúc Lõi

Red-Black Tree không phải là lý thuyết sách vở. Nó là trái tim vận hành của những hạ tầng phần mềm quyền lực nhất thế giới:

• Linux CFS (Completely Fair Scheduler): Trình lập lịch cấp phát CPU của hệ điều hành Linux nhân (Kernel) không dùng Queue. Nó dùng một cây Red-Black Tree. Các tiến trình (Process) được lưu trong RBT dựa trên vruntime (thời gian đã chạy). Tiến trình chạy ít nhất sẽ luôn nằm ở tận cùng bên trái của cây. OS chỉ việc bốc Node tận cùng bên trái ra để cấp CPU với tốc độ $O(\log n)$, đảm bảo sự công bằng tuyệt đối cho hàng ngàn thread đang chạy.

• Thư viện chuẩn của ngôn ngữ (Standard Libraries): Trong C++, std::map và std::set được cài đặt bằng Red-Black Tree. Trong Java, TreeMap cũng là Red-Black Tree. (Lưu ý: Golang không có built-in Tree Map, kiểu map của Go là Bảng băm).

• Tiền đề cho Cơ sở dữ liệu: Tư duy của RBT và AVL được mở rộng thành cây đa phân (B-Tree và B+Tree), cấu trúc đằng sau mọi công cụ Indexing của MySQL, PostgreSQL, và Oracle.

Cây Nhị Phân Tìm Kiếm đã giải quyết xuất sắc bài toán tìm kiếm với tốc độ $O(\log n)$. Nhưng ngành Khoa học máy tính luôn khao khát tốc độ tuyệt đối: Liệu có cách nào để tìm một bản ghi giữa 1 tỷ bản ghi mà chỉ mất đúng 1 bước nhảy $O(1)$ thay vì 30 bước nhảy của Cây? Ở chương tiếp theo, chúng ta sẽ đập tan các cấu trúc Node và mượn sức mạnh của các hàm băm toán học để đạt được phép màu này.