Avl Tree Là Gì

     

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


*

Nói chung, hiệu suất trong trường đúng theo xấu độc nhất vô nhị của cây kiếm tìm kiếm nhị phân (BST) cũng tương tự với các giải thuật tra cứu kiếm đường tính, hay còn được gọi là Ο (n). Cùng với dữ liệu thời hạn thực, chúng ta không thể dự đoán được mẫu tài liệu và đông đảo tần số của nó. Chính vì thế, điều cần thiết phải tạo ra ở đấy là phải cân bằng cây tra cứu kiếm nhị phân sẽ có.Bạn vẫn xem: Avl tree là gì

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

Bạn đang xem: Avl tree là gì

Dưới đó là hình ví dụ minh họa những cây, trong số đó cây đầu tiên là gồm độ cân bằng cao, cây thứ hai và thiết bị 3 là không cân bằng.


*

Trong cây trang bị 2, cây bé bên phải có độ cao là 0 cùng cây bé bên trái của C tất cả độ cao là 2, do đó hiệu số của nó là 2. Vào cây sản phẩm 3, cây bé bên trái bao gồm độ cao là 0 với cây nhỏ bên đề xuất của A gồm độ cao là 2, cho nên vì thế hiệu số của nó cũng là 2. Trong những khi đó cây AVL chỉ gật đầu hiệu số (hay Nhân tố cân nặng bằng) là 1.

BalanceFactor = height (left-sutree) − height (right-sutree)Nếu hiệu số thân độ cao của những cây nhỏ bên phải và cây con bên trái là cao hơn nữa 1 thì cây được cân bằng thông qua việc sử dụng một số trong những kỹ thuật xoay AVL được trình diễn như bên dưới đây.

Kỹ thuật tảo cây AVL

Để tạo nên cây tự cân bằng, một cây AVL hoàn toàn có thể được tiến hành bốn một số loại kỹ thuật tảo như sau:

Kỹ thuật cù tráiKỹ thuật quay phảiKỹ thuật con quay trái-phảiKỹ thuật quay phải-trái

2 chuyên môn quay thứ nhất là các kỹ thuật quay solo và 2 kỹ thuật quay còn lại là những kỹ thuật con quay ghép.

Phần tiếp theo họ sẽ kiếm tìm hiểu chi tiết mỗi một chuyên môn quay cùng với hình minh họa tương đối đơn giản và dễ dàng hiểu.

Kỹ thuật quay hoa quả AVL

Nếu một cây trở đề xuất không cân đối khi có một nút được chèn vào vào cây nhỏ ở bên bắt buộc của cây bé bên bắt buộc thì chúng ta sẽ triển khai kỹ thuật xoay trái 1-1 như sau:


*

Trong hình minh họa làm việc trên, nút A không thể cân bằng khi một nút (nút C) được sản xuất cây con bên nên của một cây nhỏ bên buộc phải của nút A. Họ sẽ tiến hành kỹ thuật con quay trái sẽ giúp đỡ A phát triển thành cây con bên trái của B.

Kỹ thuật quay bắt buộc cây AVL

Cây AVL đã mất cân bằng nếu một nút được tiếp tế cây con bên trái của cây bé bên trái. Để cây giữ lại được cân bằng, bọn họ sẽ triển khai kỹ thuật quay bắt buộc như bên dưới đây:


*

Như hình minh họa, nút không cân đối sẽ trở thành cây bé bên phải của cây con bên trái của chính nó khi ta tiến hành kỹ thuật cù phải.

Xem thêm: Từ Điển Anh Việt " Freely Là Gì ?, Từ Điển Anh Free Or Freely

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

Kỹ thuật quay ghép là tinh vi hơn đối với 2 kỹ thuật quay đối chọi như đã ra mắt ở trên. Để phát âm về chuyên môn quay ghép này cấp tốc hơn, bạn cần phải ghi chú mỗi một hành vi được tiến hành trong khi triển khai kỹ thuật quay. Một chuyên môn quay trái-phải chính là sự kết hợp của chuyên môn quay trái được theo sau bởi vì kỹ thuật quay phải.

Trạng tháiHành động

*

Một loại kỹ thuật cù ghép không giống đó đó là kỹ thuật tảo phải-trái. Kỹ thuật này là sự kết hợp của chuyên môn quay nên được theo sau vị kỹ thuật xoay trái.

Trạng tháiHành động

Một nút vẫn được cung ứng trong cây bé ở phía trái của cây nhỏ bên phải. Điều này đã làm cho nút A trở bắt buộc không cân nặng bằng cũng chính vì khi kia hiệu số (Balance Factor) là 2.

Đầu tiên, bọn họ cần tiến hành kỹ thuật quay phải so với nút C, để gia công cho C vươn lên là cây bé bên cần của thiết yếu cây nhỏ bên trái B. Bây giờ, nút B đã trở thành cây con bên buộc phải của nút A.

Bây giờ nút A vẫn chưa cân nặng bằng chính vì có lộ diện cây bé bên nên của cây bé bên đề xuất của chủ yếu nó. Vì thế cần phải tiến hành kỹ thuật tảo trái.

Xem thêm: Nhạc Hires Là Gì - Sự Khác Nhau Giữa Nhạc Mp3, Lossless Và Hi


Bây giờ đồng hồ cây sẽ ở trạng thái cân bằng.

kimsa88
cf68