Ở đây chúng ta sẽ xem cây tìm kiếm nhị phân cân bằng là gì. Cây tìm kiếm nhị phân (BST) là cây nhị phân, có phần tử nhỏ hơn ở con bên trái và phần tử lớn hơn ở con bên phải.
Độ phức tạp thời gian trung bình để tìm kiếm các phần tử trong BST là O (log n). Nó phụ thuộc vào chiều cao của cây tìm kiếm nhị phân. Để duy trì các thuộc tính của cây tìm kiếm nhị phân, đôi khi cây bị lệch. Vì vậy, cây nghiêng sẽ như thế này -
Đây thực sự là một cái cây, nhưng nó giống như một danh sách được liên kết. Đối với loại cây này, thời gian tìm kiếm sẽ là O (n). Điều đó không hiệu quả đối với cây nhị phân.
Để khắc phục những vấn đề này, chúng ta có thể tạo ra một cây có chiều cao cân đối. Như vậy cây sẽ không bị cong queo. Một cách mạnh mẽ, chúng tôi sẽ cân bằng. Vì vậy, mỗi bên của một nút sẽ chứa một cây con có chiều cao gần như bằng nhau
Có nhiều kỹ thuật khác nhau để giữ thăng bằng. Một số trong số đó là -
-
Cây AVL
-
Cây đỏ đen
Dạng cân bằng chiều cao của ví dụ trên sẽ như thế này -
