Đang chuẩn bị nút TẢI XUỐNG, xin hãy chờ
Tải xuống
Tham khảo tài liệu 'cấu trúc dữ liệu và giải thuật part 9', công nghệ thông tin, cơ sở dữ liệu phục vụ nhu cầu học tập, nghiên cứu và làm việc hiệu quả | b Tình huống 2 Chiều cao hai cây con vốn đã bằng nhau sau phép bổ sung cây con trái cao hơn 1 lệch trái . c Tinh huống 3 Cây con trái đã cao hơn 1 ệch trái sau phép bổ sung nó cao hơn 2 tính cân đôi AVL bị phá vỡ Đối với tình huống 1 chỉ cần chỉnh lý các hệ sô cân đô i ở nút đang xét. Đối với tình huống 2 chiều cao của cây có gốc là nút đang xét bị thay đổi nên không những phải chỉnh lý hệ sô cán đối ở nút đang xét mà còn phải chỉnh lý hệ sô cân đô i ử các nút tiền bối của nó. Dọc trên đường đi đã ghi nhận khi tìm kiêm cũng phải xem xét để biết có xảy ra tình huống nào trong ha tình huống đã nêu đối với nút đó không và có biện pháp xử lý thích hợp. Như vậy có khi cần phải lẩn ngược iại tới tận gô c cây. Còn đối với tình huống 3 thì đòi hỏi phái sửa lại cây con mà nút đang xét là nút gốc ta SC gọi là nút bất thường critical node để nó cân đối hũ. Có hai trường hợp phải xử lý khác nhau. Hình 10.9 mô tá các trường hợp đó. a Trường hợp LL Nút mới bổ sung làm tăng chiều cao cây con trái của nút con trái nút bất thường. Như ở hình 10.9a nút mới bổ sung làm tăng chiều cao của cây a cây con trái của nút 1. b Trường hợp 2 LR Nút mới bổ sung làm tăng chiều cao cây con phải của nút con trái nứt bất thường. Như ở hình 10.9b nút mói bổ sung làm tăng chiều cao của cây p cây con phải của nút I. Trước lúc bổ sung Sau lúc bổ sung 252 b chi cây con a có chiều cao bằng h chỉ nút bất thường ứng với khoá bằng 2 chỉ nút mới bổ sung Hình 10.9 Đối với trường hợp 1 để tái cân đối ta phải thực hiện một phép quay từ trái sang phải để đưa nút 1 lên vị trí gốc cây con nút 2 sẽ trở thành con phải của nó và p được gắn vào thành con trái của 2 . Ta thấy cách làm này tương tự như cách áp dụng luật kết hợp trong đại sô thay o.p y bằng cc py . Người ta gọi phép này là phép quay đơn single rotation . Xem hình 10.10. Hình ỈO.ỈO 253 Còn đối với trường hợp 2 thi phải thực hiện một phép quay kép double rotation đó là việc phôi hợp hai phép quay đơn quay trái đói với cây con trái 1 2 và quay phải đối với
