Cấu trúc dữ liệu và thuật toán - Cây AVL

Gửi bởi: Võ Thị Hường 13 tháng 2 2020 lúc 14:07:09

Mục lục

* * * * *

Điều gì xảy ra nếu đầu vào của cây tìm kiếm nhị phân xuất hiện theo cách sắp xếp (tăng dần hoặc giảm dần)? Sau đó nó sẽ trông như thế này -

Cấu trúc dữ liệu và thuật toán - Cây AVL

Theo quan sát, hiệu suất trong trường hợp xấu nhất của BST là gần nhất với các thuật toán tìm kiếm tuyến tính, đó là (n). Trong dữ liệu thời gian thực, chúng ta không thể dự đoán mẫu dữ liệu và tần số của chúng. Vì vậy, một nhu cầu nảy sinh để cân bằng BST hiện có.

Được đặt theo tên nhà phát minh Adelson , Velski & Landis , cây AVL là cây tìm kiếm nhị phân cân bằng chiều cao. Cây AVL kiểm tra chiều cao của cây con bên trái và bên phải và đảm bảo rằng chênh lệch không quá 1. Sự khác biệt này được gọi là Hệ số cân bằng .

Ở đây chúng ta thấy rằng cây đầu tiên được cân bằng và hai cây tiếp theo không cân bằng -

Trong cây thứ hai, cây con bên trái của C có chiều cao 2 và cây con bên phải có chiều cao 0, vì vậy sự khác biệt là 2. Trong cây thứ ba, cây con bên phải của A có chiều cao 2 và bên trái bị thiếu, vì vậy nó là 0 và sự khác biệt là 2 lần nữa. Cây AVL cho phép chênh lệch (hệ số cân bằng) chỉ là 1.

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

Nếu chênh lệch chiều cao của cây con trái và phải lớn hơn 1, cây được cân bằng sử dụng một số kỹ thuật xoay.

Xoay AVL

Để tự cân bằng, cây AVL có thể thực hiện bốn loại phép quay sau -

Xoay trái
Xoay phải
Xoay trái-phải
Xoay trái phải

Hai phép quay đầu tiên là phép quay đơn và hai phép quay tiếp theo là phép quay đôi. Để có một cây không cân đối, ít nhất chúng ta cần một cây có chiều cao 2. Với cây đơn giản này, chúng ta hãy hiểu từng cái một.

Xoay trái

Nếu một cây trở nên mất cân bằng, khi một nút được chèn vào cây con bên phải của cây con bên phải, thì chúng ta thực hiện một vòng xoay trái -

Trong ví dụ của chúng tôi, nút A đã trở nên mất cân bằng khi một nút được chèn vào cây con bên phải của cây con bên phải của A. Chúng tôi thực hiện xoay trái bằng cách biến A thành cây con trái của B.

Xoay phải

Cây AVL có thể trở nên mất cân bằng, nếu một nút được chèn vào cây con bên trái của cây con bên trái. Cây sau đó cần một vòng quay đúng.

Theo mô tả, nút không cân bằng trở thành con phải của con trái bằng cách thực hiện xoay phải.

Xoay trái-phải

Xoay đôi là phiên bản hơi phức tạp của các phiên bản xoay đã được giải thích. Để hiểu rõ hơn về chúng, chúng ta nên lưu ý từng hành động được thực hiện trong khi xoay. Trước tiên chúng ta hãy kiểm tra cách thực hiện xoay trái-phải. Xoay trái phải là sự kết hợp của xoay trái theo sau xoay phải.