Правое вращение - Right rotation

Правое вращение относится к следующему

• В множество, перемещая все предметы на следующую более высокую позицию. Последний предмет перемещается на первое место, которое было освобождено.
• В список, удаляя хвост и вставив его в голова.
• В Машинный код (и язык ассемблера ) перемещая все биты в регистре вправо, причем крайний правый (младший бит ) становится крайним левым.

Вращение дерева

В двоичное дерево поиска, поворот вправо - это перемещение узла X вниз вправо. Это вращение предполагает, что у X есть левый дочерний элемент (или поддерево). Левый дочерний элемент X, R, становится родительским узлом X, а правый дочерний элемент R становится новым левым дочерним элементом X. Это вращение сделано, чтобы сбалансировать дерево; в частности, когда левое поддерево узла X имеет значительно (в зависимости от типа дерева) большую высоту, чем его правое поддерево.

Правое вращение (и левое) сохранение порядка в двоичное дерево поиска; он сохраняет свойство двоичного дерева поиска ( обход по порядку дерева даст ключи узлов в правильном порядке). Деревья АВЛ и красно-черные деревья два примера деревьев двоичного поиска, в которых используется правое вращение.

Одно вращение вправо выполняется за время O (1), но часто интегрируется в вставку и удаление узла деревья двоичного поиска. Повороты выполняются, чтобы свести к минимуму стоимость других методов и высоту дерева.

Рекомендации

• Томас Х. Кормен, Чарльз Э. Лейзерсон, Рональд Л. Ривест, и Клиффорд Штайн, 16 июля 2001 г., Введение в алгоритмы, второе издание. Макгроу-Хилл, ISBN  0-07-013151-1. Глава 13.