Левое вращение - Left rotation

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

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

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

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

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

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

использованная литература

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