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[sửa | sửa mã nguồn]
Mô tả[sửa | sửa mã nguồn]
Phép quay phải[sửa | sửa mã nguồn]
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[sửa | sửa mã nguồn]
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ú ý[sửa | sửa mã nguồn]
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[sửa | sửa mã nguồn]
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.
Tính chất của phép quay[sửa | sửa mã nguồn]
- Phép quay giữ nguyên danh sách duyệt trung thứ tự của cây;
- Phép quay biến một cây tìm kiếm nhị phân thành cây tìm kiếm nhị phân.
Ứng dụng của phép quay trên cây nhị phân[sửa | sửa mã nguồn]
Phép quay được ứng dụng để tái cân bằng khi thực hiện phép chèn hoặc xóa trên các cây tìm kiếm nhị phân AVL hay cây đỏ đen, cây tìm kiếm nhị phân tối ưu.