Cây AVL trong cấu trúc dữ liệu và giải thuật
Cây AVL là gì?
Điều gì xảy ra nếu dữ liệu nhập vào cây tìm kiếm nhị phân (BST) là ở dạng đã được sắp thứ tự (tăng dần hoặc giảm dần). Nó sẽ trông giống như sau:
Nói chung, hiệu suất trường hợp xấu nhất của cây tìm kiếm nhị phân (BST) gần với các giải thuật tìm kiếm tuyến tính, tức là Ο(n). Với dữ liệu thời gian thực, chúng ta không thể dự đoán mẫu dữ liệu và các tần số của nó. Vì thế, điều cần thiết phát sinh ở đây là để cân bằng cây tìm kiếm nhị phân đang tồn tại.
Cây AVL (viết tắt của tên các nhà phát minh Adelson, Velski và Landis) là cây tìm kiếm nhị phân có độ cân bằng cao. Cây AVL kiểm tra độ cao của các cây con bên trái và cây con bên phải và bảo đảm rằng hiệu số giữa chúng là không lớn hơn 1. Hiệu số này được gọi là Balance Factor (Nhân tố cân bằng).
Dưới đây là hình ví dụ minh họa ba cây, trong đó cây đầu tiên là cân bằng, cây thứ hai và thứ ba là không cân bằng.
Trong cây thứ hai, cây con bên trái của C có độ cao là 2 và cây con bên phải có độ cao là 0, do đó hiệu số là 2. Trong cây thứ ba, cây con bên phải của A có độ cao là 2 và cây con bên trái có độ cao là 0, do đó hiệu số 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 trái và cây con bên phải là lớn hơn 1 thì cây được cân bằng bởi sử dụng một số kỹ thuật quay AVL được trình bày 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ể thực hiện 4 loại kỹ thuật quay 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
Hai kỹ thuật quay đầu tiên là các kỹ thuật quay đơn và hai 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 từng kỹ thuật quay với hình minh họa đơ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 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 có thể thực hiện kỹ thuật quay trái đơn như sau:
Trong hình minh họa trên, nút A trở nên không cân bằng khi một nút (nút C) được chèn vào cây con bên phải của cây con bên phải của nút A. Chúng ta thực hiện kỹ thuật quay trái để làm 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 trở nên không 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 cân bằng, chúng ta thực hiện kỹ thuật quay phải như sau:
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ó bằng kỹ thuật quay phải.
Kỹ thuật quay trái-phải cây AVL
Kỹ thuật quay ghép là khá phức tạp so với hai kỹ thuật quay đơn vừa giới thiệu trên. Để hiểu kỹ thuật quay này nhanh hơn, bạn cần phải ghi chú từng hành động được thực hiện trong khi quay. Một kỹ thuật quay trái-phải 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 |
Một nút đã được chèn vào trong cây con bên phải của cây con bên trái. Điều này làm nút C trở nên không cân bằng. Với tình huống này, cây AVL có thể thực hiện kỹ thuật quay trái-phải. | |
Đầ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. | |
Bây giờ nút C vẫn không cân bằng, đó là do xuất hiện cây con bên trái của cây con bên trái. | |
Bây giờ chúng ta sẽ thực hiện kỹ thuật quay phải để làm 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ó. | |
Bây giờ cây đã cân bằng. |
Kỹ thuật quay phải-trái cây AVL
Một loại kỹ thuật quay ghép khác 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ái | Hành động |
Một nút đã được chèn 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 nút A trở nên không cân bằng bởi vì hiệu số (Balance Factor) là 2. | |
Đầu tiên, chúng ta thực hiện kỹ thuật quay phả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. | |
Bây giờ nút A vẫn không cân bằng bởi vì xuất hiện cây con bên phải của cây con bên phải của nó. Do đó cần phải thực hiện một kỹ thuật quay trái. | |
Một kỹ thuật quay trái được thực hiện làm cho B trở thành nút gốc mới của cây con. Nút A trở thành cây con bên trái của cây con B bên phải của nó. | |
Bây giờ cây đã cân bằng. |
Theo Tutorialspoint
Bài trước: Cây tìm kiếm nhị phân (Binary Search Tree)
Bài tiếp: Cây khung (Spanning Tree) trong cấu trúc dữ liệu và giải thuật
Bạn nên đọc
-
Công thức tính chiều cao hình thang: thường, vuông, cân
-
Công thức tính đường cao trong tam giác thường, cân, đều, vuông
-
Công thức tính chu vi hình tam giác
-
Công thức tính diện tích hình Elip
-
Công thức tính diện tích hình lập phương, thể tích khối lập phương
-
Công thức tính thể tích khối tròn xoay và ví dụ minh họa
Cũ vẫn chất
-
Code Thần Thú Đại Chiến mới nhất 10/2024
Hôm qua 1 -
4 cách ẩn hoặc bảo vệ một thư mục Windows tốt nhất, không cần cài thêm phần mềm
Hôm qua -
Cách đăng ký VIP Zing MP3 tải nhạc chất lượng cao
Hôm qua -
24+ bí quyết đơn giản giúp bạn thư giãn, giảm căng thẳng chỉ trong vòng 5 phút
Hôm qua -
TOP 13 nhà cung cấp hosting tại Việt Nam, tốc độ cao và bảo mật hàng đầu
Hôm qua -
Stt gọi anh là, cap tán tỉnh gọi anh là, gọi em là cực chất
Hôm qua -
Cách đổi DNS trên điện thoại iPhone, Android
Hôm qua 2 -
Tốc Chiến: Đáp án sự kiện Đố Vui cùng Kassadin
Hôm qua -
5 cách viết hoa chữ cái đầu trong Excel
Hôm qua -
Những website học lập trình miễn phí cần bookmark ngay lập tức!
Hôm qua