Chuyển tới nội dung chính

Cây cân bằng & AVL (giới thiệu)

Bạn sẽ học được gì

Bài BST cho thấy cây có thể lệch thành O(n). Cây AVL sửa điều đó: nó tự cân bằng sau mỗi lần chèn/xóa bằng phép xoay, giữ chiều cao luôn ~log n. (Bài giới thiệu — nắm ý tưởng, chưa cần thuộc cài đặt.)

1. Ý tưởng: giữ cây không lệch​

Cây AVL là một BST có thêm luật: tại mọi nút, chiều cao hai cây con không lệch nhau quá 1. Nếu một thao tác làm lệch quá → cây tự xoay lại cho cân.

Hệ số cân bằng của một nút = (chiều cao cây con trái) − (chiều cao cây con phải). AVL giữ hệ số này luôn ở −1, 0, hoặc +1.

Cân bằng (OK):          Lệch (vi phạm AVL):
     3                       1
    / \                       \
   1   5                       2          ← hệ số = -2, phải xoay!
                                \
                                 3

2. Phép xoay: cách cây tự sửa​

Khi một nút lệch quá, AVL thực hiện phép xoay (rotation) — sắp xếp lại vài con trỏ để hạ chiều cao mà vẫn giữ tính chất BST. Ví dụ "xoay trái" khi cây nghiêng phải:

   xoay trái quanh A:
     A                  B
      \               /   \
       B      ──▶    A     C
        \
         C
   (cao 3, lệch)    (cao 2, cân)

Có 4 loại xoay: trái, phải, trái-phải, phải-trái — tùy hướng lệch. Điểm cốt lõi cần nhớ: xoay là O(1) (chỉ đổi vài con trỏ), và sau xoay cây lại cân.

3. Vì sao quan trọng: O(log n) ĐẢM BẢO​

Vì luôn cân, AVL đảm bảo chiều cao ~log n → tìm/chèn/xóa luôn O(log n), kể cả khi chèn dữ liệu đã sắp xếp (thứ làm BST thường suy biến). Chèn/xóa tốn thêm chi phí xoay nhưng vẫn O(log n).

Đang tải trình chạy code…

Với 1 triệu phần tử: BST lệch cao 1.000.000 (tìm kiếm thảm họa), AVL chỉ cao ~29 → tìm kiếm tức thì.

4. AVL vs BST thường​

BST thườngAVL
Tìm/chèn/xóaO(log n) nếu may, O(n) nếu lệchO(log n) đảm bảo
Tự cân bằngkhôngcó (bằng xoay)
Chi phí chèn/xóathấpcao hơn chút (kiểm tra + xoay)
Dùng khidữ liệu ngẫu nhiên, đơn giảncần đảm bảo hiệu năng
🎬 Trực quan hóa tương tác — VisuAlgo
Chèn các phần tử theo thứ tự sắp xếp để thấy phép xoay tự động giữ cây cân bằng. So sánh với BST thường sẽ thấy sự khác biệt rõ rệt.
Nguồn: visualgo.net — Steven Halim, NUS. Dùng cho lớp học; ảnh chụp/video cần ghi nguồn URL.

5. Mẫu nhận diện​

  • Cần BST nhưng đảm bảo O(log n) trong mọi tình huống → cây tự cân bằng (AVL).
  • Dữ liệu vào có thể đã sắp xếp / theo thứ tự → BST thường nguy hiểm, dùng AVL.
  • Trong thực tế ít khi tự cài AVL — dùng cấu trúc cân bằng có sẵn của ngôn ngữ (xem bài red-black).

6. 🎮 Trò chơi: Hiểu AVL​

🎮 Hiểu AVLCâu 1/4· Điểm 0· 🔥 0

AVL = BST tự cân bằng. Hệ số cân bằng giữ trong {-1,0,1}; lệch quá thì xoay (O(1)).

Khi một nút lệch quá, AVL làm gì?

7. Quiz kiểm tra nhanh​

📝 Quiz kiểm tra nhanh
1. Cây AVL là?
2. AVL đảm bảo độ phức tạp tìm/chèn/xóa là?
3. Đánh đổi của AVL so với BST thường?
📚 Đọc thêm & Luyện tập
🎬 Video
🏋️ Luyện tập

8. Hoàn thành​

…

☑️ Tiếp theo: 2.5.4 — Cây đỏ-đen (red-black tree).