tailieunhanh - Cấu trúc dữ liệu và giải thuật I - Bài 14

CÁC THAO TÁC CƠ BẢN TRÊN CÂY AVL Mục tiêu Giới thiệu các thuật giải thêm hủy trên cây AVL Cài đặt các thao tác thêm hủy trên cây AVL Nội dung I. Các trường hợp mất cân bằng | ÀI 14 CÁC THAO TÁC CƠ BẢN TRÊN CÂY AVL Mục tiêu Giới thiệu các thuật giải thêm hủy trên cây AVL Cài đặt các thao tác thêm hủy trên cây AVL Nội dung Cx Các trường hợp mất cân bằng -jlI. Thêm và cân bằng lại cây thuật đặt -jlII. Hủy và cân bằng lại cây thuật đặt -jiv. Đánh giá độ phức tạp Bài tâp BÀI 14 CÁC THAO TÁC CƠ BẢN TRÊN CÂY AVL Ta nhận thấy trường hợp thêm hay hủy một phần tử trên cây có thể làm cây tăng hay giảm chiều cao khi đó phải cân bằng lại cây. Việc cân bằng lại một cây sẽ phải thực hiện sao cho chỉ ảnh hưởng tối thiểu đến cây nhằm giảm thiểu chi phí cân bằng. Như đã nói ở trên cây cân bằng cho phép việc cân bằng lại chỉ xảy ra trong giới hạn cục bộ nên chúng ta có thể thực hiện được mục tiêu vừa nêu. Như vậy ngoài các thao tác bình thường như trên CNPTK các thao tác đặc trưng của cây AVL gồm Thêm môt phần tử vào cây AVL. Hủy môt phần tử trên cây AVL. Cân bằng lại môt cây vừa bị mất cân bằng. I. CÁC TRƯỜNG HỢP MẤT CÂN BẰNG Ta sẽ không khảo sát tính cân bằng của 1 cây nhị phân bất kỳ mà chỉ quan tâm đến các khả năng mất cân bằng xảy rakhi thêm hoặc hủy một nút trên cây AVL. Như vậy khi mất cân bằng độ lệch chiều cao giữa 2 cây con sẽ là 2. Ta có 6 khả năng sau Trường hợp 1 cây T lệch về bên trái có 3 khả năng Trường hợp 2 cây T lệch về bên phải Ta có các khả năng sau Ta có thể thấy rằng các trường hợp lệch về bên phải hoàn toàn đối xứng với các trường hợp lệch về bên trái. Vì vậy ta chỉ cần khảo sát trường hợp lệch về bên trái. Trong