Xem cây tìm kiếm nhị phân cân bằng (Balanced BST). BST có phần tử nhỏ hơn ở con trái, lớn hơn ở con phải.
Độ phức tạp trung bình tìm kiếm là O(log n), phụ thuộc chiều cao cây. Để giữ tính chất BST, cây đôi khi bị lệch (skewed), trông như danh sách liên kết:
Lúc này tìm kiếm O(kém). Để khắc phục, tạo cây cân bằng chiều cao (height-balanced). Mỗi nút giữ cây con bên trái và bên phải có chiều cao gần bằng nhau.
Các kỹ thuật cân bằng:
- AVL Tree
- Red-Black Tree
Dạng cân bằng của ví dụ trên:
