Một BST thuần có thể suy biến thành một linked list (thao tác O(n)) nếu key đến theo thứ tự đã sắp xếp. Self-balancing BST (BST tự cân bằng) — như AVL và red-black tree — tự động xoay (rotate) các node sau khi chèn/xóa để giữ chiều cao ~log n, đảm bảo các thao tác O(log n).
Không cân bằng (chèn 1,2,3,4): Cân bằng sau khi xoay:
1 2
\ / \
2 1 3
\ \
3 4
chiều cao ~ n (XẤU) chiều cao ~ log n (TỐT)
| AVL tree | Red-black tree | |
|---|---|---|
| Độ chặt cân bằng | chặt (cân bằng chiều cao) | lỏng hơn |
| Tra cứu | nhanh hơn (ngắn hơn) | hơi chậm hơn |
| Chèn/xóa | nhiều phép xoay hơn | ít phép xoay hơn |
| Tốt nhất cho | workload đọc nhiều | workload ghi nhiều |
| Thao tác | Thời gian |
|---|---|
| search | O(log n) |
| insert | O(log n) |
| delete | O(log n) |
Cả hai duy trì cân bằng qua phép xoay (rotation) — các tái cấu trúc cục bộ O(1) bảo toàn thứ tự BST trong khi giảm chiều cao.
Balanced tree là nền tảng cho ordered map và set trong các thư viện chuẩn (ví dụ Java TreeMap, C++ std::map dùng red-black tree), cho duyệt theo thứ tự cùng các thao tác logarit được đảm bảo.
Chúng là câu trả lời khi bạn cần thứ tự của một BST và một đảm bảo hiệu năng cứng chống lại đầu vào đối nghịch.