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 đó.