Правое вращение

Правое вращение означает следующее:

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

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

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

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

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

Ссылки

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