tailieunhanh - Cấu trúc dữ liệu : CÂY CÂN BẰNG part 2

Trong 3 trường hợp lệch về bên trái, trường hợp T1 lệch phải là phức tạp nhất. Các trường hợp còn lại giải quyết rất đơn giản. Sau đây, ta sẽ khảo sát và giải quyết từng trường hợp nêu trên T/h : cây T1 lệch về bên trái. Ta thực hiện phép quay đơn Left-Left T/h : cây T1 không lệch. Ta thực hiện phép quay đơn Left-Left | 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 7 hợp lệch về bên trái. Trong 3 trường hợp lệch về bên trái trường hợp T1 lệch phải là phức tạp nhất. Các trường hợp còn lại giải quyết rất đơn giản. Sau đây ta sẽ khảo sát và giải quyết từng trường hợp nêu trên T h cây T1 lệch về bên trái. Ta thực hiện phép quay đơn Left-Left T h cây T1 không lệch. Ta thực hiện phép quay đơn Left-Left 8 Ttoán quay đơn Left-Left B1 T là gốc T1 T- pLeft T- pLeft T1- pRight T1- pRight T B2 đặt lại chỉ số cân bằng Nếu T1- balFactor LH thì T- balFactor EH T1- balFactor EH break Nếu T1- balFactor EH thì T- balFactor LH T1- balFactor RH break B3 T trỏ đến gốc mới T T1 T h cây T1 lệch về bên phải. Ta thực hiện phép quay kép Left-Right Do T1 lệch về bên phải ta không thể áp dụng phép quay đơn đã áp dụng trong 2 trường hợp trên vì khi đó cây T sẽ từ trạng thái mất cân bằng do lệch trái thành mất cân bằng do lệch phải. Hình vẽ dưới đây minh họa phép quay kép áp dụng cho trường hợp này