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

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

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

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

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

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

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

Ссылки

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