Phép quay cây nhị phân

Trong khoa học máy tính, Phép quay trên các cây nhị phân là một phép biến đổi làm thay đổi vai trò cha con giữa 2 nút trên cây. Có hai phép quay là quay phải hoặc quay trái. Phép quay phải chuyển một nút cha thành con phải của nút con bên trái, phép quay trái chuyển một nút cha thành con trái của nút con phải. Đồng thời, với sự thay đổi đó, một sự điều chỉnh cho các nút con trước đây của nút mới chuyển thành nút cha. Phép quay bảo toàn thứ tự giữa của các nút trên cây, nghĩa là trước và sau một hoặc nhiều phép quay, danh sách duyệt các đỉnh theo thứ tự giữa (trung thứ tự) không thay đổi. Nhờ vậy nếu một cây nhị phân là cây tìm kiếm nhị phân của một dãy khóa thì sau khi quay nó vẫn là cây tìm kiếm nhị phân của dãy khóa đó.

Phép quay cây nhị phân tại gốc

Mô tả

Phép quay phải

Giả sử R0 là nút gốc của cây và có nút con trái là L. Phép quay phải chuyển L thành gốc của cây và gốc R cũ trở thành con phải của cây. Khi đó con phải trước đây của L là LR bị tách khỏi L, để giữ nguyên tính chất của cây nhị phân tìm kiếm, ta phải cho liên kết trái của R trỏ tới LR. Như vậy giả mã của phép quay phải tại gốc T.root của cây T có thể viết như sau

RIGHT-ROTATE(T)
 R0=T.root;
 L=R0.Left;
 If L=NULL then return False
 R0.Left=L.Right;
 L.Right=R0;
 T.root=L;

Phép quay trái

Giả sử R0 là nút gốc của cây và có nút con phải là R. Phép quay phải chuyển R thành gốc của cây và gốc R0 cũ trở thành con trái của cây T. Khi đó con trái trước đây của R là RL bị tách khỏi mối nối trái của R, còn mối nối phải của R0 lại tách khỏi R, do đó ta có thể cho liên kết phải của R0 trỏ tới RL. Như vậy giả mã của phép quay trái tại gốc T.root của cây T có thể viết như sau

LEFT-ROTATE(T)
 R0=T.root;
 R =R0.Right;
 If R=NULL then return False
 R0.Right=R.Left;
 R.Left=R0;
 T.root=R;

Chú ý

Sau này ta sẽ gọi phép quay cây T tại gốc đơn giản là phép quay cây T. Một số người so sánh phép quay với tính chất kết hợp của phép toán, chẳng hạn phép cộng như hình bên.

Phép quay tại một đỉnh trong của cây

Giả sử U là một đỉnh trong của cây nhị phân T. Ký hiệu cha của U là P. Khi đó nếu U có con trái L, ta sẽ gọi phép quay phải cây con gốc U là phép quay phải cây T tại đỉnh U. Tương tự, nếu U có con phải, ta gọi phép quay trái cây con gốc U là phép quay trái cây T tại đỉnh U. Như vậy cũng có thể xem phép quay cây T tại một đỉnh là trường hợp tổng quát của phép quay tại gốc. Mã giả của phép quay tổng quát này được xét thêm trường hợp U không là gốc.

RIGHT-ROTATE(T,U)
L=U.Left;
If L=NULL then return False
U.Left=L.Right;
L.Right=U;
if U=T.root then T.root=L 
 else begin
P=U.parent;
if U=P.right then P.right=L
else  P.Left=L
 end;
LEFT-ROTATE(T,U)
R=U.Right;
If R=NULL then return False
U.Right=R.Left;
R.Left=U;
if U=T.root then T.root=R 
else begin
P=U.parent;
if U=P.right then P.right=R
else  P.Left=R
end;

Các phép quay phải hoặc trái được gọi chung là phép quay.