Trang chủ > Khác > Cấu trúc dữ liệu và giải thuật > Cây AVL - AVL Tree (Cấu trúc dữ liệu và giải thuật)

Cây AVL - AVL Tree (Cấu trúc dữ liệu và giải thuật)

Điều gì sẽ xảy ra nếu dữ liệu nhập vào cây tìm kiếm nhị phân (BST) là ở dưới dạng đã được sắp thứ tự (giảm dần hoặc tăng dần). Nó sẽ trông giống như hình dưới đây:

Cây AVL - AVL Tree ảnh 1

Nói chung, hiệu suất trong trường hợp xấu nhất của cây tìm kiếm nhị phân (BST) cũng tương đương với các giải thuật tìm kiếm tuyến tính, hay còn gọi là Ο (n). Với dữ liệu thời gian thực, chúng ta không thể dự đoán được mẫu dữ liệu và những tần số của nó. Chính vì thế, điều cần thiết phải phát sinh ở đây là phải cân bằng cây tìm kiếm nhị phân đang có.

Cây AVL (viết tắt của tên các nhà phát minh Landis, Adelson, và Velski) là cây tìm kiếm nhị phân được đánh giá là có độ cân bằng cao. Cây AVL có thể kiểm tra độ cao của các cây con bên phải và cây con bên trái và bảo đảm chắc chắn rằng hiệu số giữa chúng là không lớn hơn 1. Hiệu số này còn được gọi là Balance Factor (Nhân tố cân bằng).

Dưới đây là hình ví dụ minh họa các cây, trong đó cây đầu tiên là có độ cân bằng cao, cây thứ 2 và thứ 3 là không cân bằng.

Cây AVL - AVL Tree ảnh 2

Trong cây thứ 2, cây con bên phải có độ cao là 0 và cây con bên trái của C có độ cao là 2, do đó hiệu số của nó là 2. Trong cây thứ 3, cây con bên trái có độ cao là 0 và cây con bên phải của A có độ cao là 2, do đó hiệu số của nó cũng là 2. Trong khi đó cây AVL chỉ chấp nhận hiệu số (hay Nhân tố cân bằng) là 1.

BalanceFactor = height (left-sutree) − height (right-sutree)

Nếu hiệu số giữa độ cao của các cây con bên phải và cây con bên trái là cao hơn 1 thì cây được cân bằng thông qua việc sử dụng một số kỹ thuật quay AVL được trình bày như dưới đây.

Kỹ thuật quay cây AVL

Để làm cho cây tự cân bằng, một cây AVL có thể được thực hiện bốn loại kỹ thuật quay như sau:

  • Kỹ thuật quay trái
  • Kỹ thuật quay phải
  • Kỹ thuật quay trái-phải
  • Kỹ thuật quay phải-trái

2 kỹ thuật quay đầu tiên là các kỹ thuật quay đơn và 2 kỹ thuật quay còn lại là các kỹ thuật quay ghép.

Phần tiếp theo chúng ta sẽ tìm hiểu chi tiết mỗi một kỹ thuật quay với hình minh họa tương đối đơn giản và dễ hiểu.

Kỹ thuật quay trái cây AVL

Nếu một cây trở nên không cân bằng khi có một nút được chèn vào trong cây con ở bên phải của cây con bên phải thì chúng ta sẽ thực hiện kỹ thuật quay trái đơn như sau:

Cây AVL - AVL Tree ảnh 3

Trong hình minh họa ở trên, nút A không còn cân bằng khi một nút (nút C) được thêm vào cây con bên phải của một cây con bên phải của nút A. Chúng ta sẽ thực hiện kỹ thuật quay trái để giúp A trở thành cây con bên trái của B.

Kỹ thuật quay phải cây AVL

Cây AVL đã không còn cân bằng nếu một nút được thêm vào cây con bên trái của cây con bên trái. Để cây giữ được cân bằng, chúng ta sẽ thực hiện kỹ thuật quay phải như dưới đây:

Cây AVL - AVL Tree ảnh 4

Như hình minh họa, nút không cân bằng sẽ trở thành cây con bên phải của cây con bên trái của nó khi ta thực hiện kỹ thuật quay phải.

Kỹ thuật quay trái-phải cây AVL

Kỹ thuật quay ghép là phức tạp hơn so với 2 kỹ thuật quay đơn như đã giới thiệu ở trên. Để hiểu về kỹ thuật quay ghép này nhanh hơn, bạn cần phải ghi chú mỗi một hành động được thực hiện trong khi thực hiện kỹ thuật quay. Một kỹ thuật quay trái-phải chính là sự kết hợp của kỹ thuật quay trái được theo sau bởi kỹ thuật quay phải.

Trạng thái Hành động
Cây AVL - AVL Tree ảnh 5
Một nút đã được thêm vào trong cây con ở bên phải của cây con bên trái. Điều này đã giúp nút C trở nên không còn cân bằng. Với tình huống này, cây AVL có thể thực hiện các kỹ thuật quay trái-phải.
Cây AVL - AVL Tree ảnh 6
Đầu tiên, thực hiện phép quay trái trên cây con ở bên trái của C. Điều này đã làm cho A trở thành cây con ở bên trái của B.
Cây AVL - AVL Tree ảnh 7
Bây giờ nút C vẫn chưa cân bằng, đó là vì đã xuất hiện cây con bên trái của cây con bên trái.
Cây AVL - AVL Tree ảnh 8
Bây giờ chúng ta sẽ thực hiện kỹ thuật quay phải để giúp cho B trở thành nút gốc mới của cây này. Nút C bây giờ đã trở thành cây con bên phải của chính cây conở bên trái của nó.
Cây AVL - AVL Tree ảnh 9
Bây giờ cây đã cân bằng.
Kỹ thuật quay phải-trái cây AVL
Kỹ thuật quay phải-trái cây AVL

Một loại kỹ thuật quay ghép khác đó chính là kỹ thuật quay phải-trái. Kỹ thuật này là sự kết hợp của kỹ thuật quay phải được theo sau bởi kỹ thuật quay trái.

Trạng tháiHành động
Cây con trái của cây con phảiMột nút đã được thêm vào trong cây con ở bên trái của cây con bên phải. Điều này đã làm cho nút A trở nên không cân bằng bởi vì khi đó hiệu số (Balance Factor) là 2.
Quay cây con phảiĐầu tiên, chúng ta cần thực hiện kỹ thuật quay phải đối với nút C, để làm cho C trở thành cây con bên phải của chính cây con bên trái B. Bây giờ, nút B đã trở thành cây con bên phải của nút A.
Cây không cân bằngBây giờ nút A vẫn chưa cân bằng bởi vì có xuất hiện cây con bên phải của cây con bên phải của chính nó. Do đó cần phải thực hiện kỹ thuật quay trái.
Quay trái cây AVLMột kỹ thuật quay trái được thực hiện đã giúp cho B trở thành nút gốc mới của cây con. Nút A giờ đây đã trở thành cây con bên trái của cây con B bên phải của nó.
Cây AVL cân bằngBây giờ cây đã ở trạng thái cân bằng.