В дискретной математике , вращение вала представляет собой операцию на бинарное дерево , которое изменяет структуру , не нарушая порядка элементов. Вращение дерева перемещает один узел вверх по дереву и один узел вниз. Он используется для изменения формы дерева и, в частности, для уменьшения его высоты путем перемещения меньших поддеревьев вниз и более крупных поддеревьев вверх, что приводит к повышению производительности многих операций с деревом.
Существует несоответствие в различных описаниях определения направления вращения . Некоторые говорят, что направление вращения отражает направление, в котором узел движется при вращении (левый дочерний элемент, вращающийся в положение своего родителя, является правым вращением), в то время как другие говорят, что направление вращения отражает, какое поддерево вращается (левое поддерево, вращающееся в расположение его родителя - левое вращение, противоположное предыдущему). В этой статье используется подход направленного движения вращающегося узла.
Иллюстрация [ править ]
Операция правого вращения , как показано на соседнем изображении выполняется с Q как корень и , следовательно , является правым вращение на или с корнем, Q . Эта операция приводит к повороту дерева по часовой стрелке. Обратной операцией является левое вращение, которое приводит к движению против часовой стрелки (левое вращение, показанное выше, основано на P). Ключом к пониманию того, как работает вращение, является понимание его ограничений. В частности, порядок листьев дерева (например, при чтении слева направо) не может измениться (другой способ думать об этом состоит в том, что порядок, в котором листья будут посещаться при обходе по порядку, должен быть таким же после операция как раньше). Еще одно ограничение - это главное свойство двоичного дерева поиска, а именно то, что правый дочерний элемент больше, чем родитель, а левый дочерний элемент меньше, чем родительский. Обратите внимание, что правильный ребеноклевого дочернего элемента корня поддерева (например, узел B на диаграмме для дерева с корнем Q) может стать левым дочерним элементом корня, который сам становится правым дочерним элементом «нового» корня в повернутое поддерево, не нарушая ни одного из этих ограничений. Как видно на схеме, порядок листьев не меняется. Противоположная операция также сохраняет порядок и является вторым видом вращения.
Предполагая, что это двоичное дерево поиска , как указано выше, элементы должны интерпретироваться как переменные, которые можно сравнивать друг с другом. Буквенные символы слева используются в качестве заполнителей для этих переменных. В анимации справа заглавные буквенные символы используются в качестве заполнителей переменных, а строчные греческие буквы являются заполнителями для всего набора переменных. Кружки представляют отдельные узлы, а треугольники - поддеревья. Каждое поддерево может быть пустым, состоять из одного узла или состоять из любого количества узлов.
Подробная иллюстрация [ править ]
Когда поддерево вращается, сторона поддерева, на которой оно вращается, увеличивает свою высоту на один узел, в то время как другое поддерево уменьшает свою высоту. Это делает вращение дерева полезным для балансировки дерева.
Рассмотрим терминологию Root для родительского узла поддеревьев, подлежащих вращению, Pivot для узла, который станет новым родительским узлом, RS для стороны вращения и OS для противоположной стороны вращения. Для корня Q на диаграмме выше RS - это C, а OS - P. Используя эти термины, псевдокод для поворота выглядит следующим образом:
Pivot = Root.OSRoot.OS = Pivot.RSPivot.RS = КореньКорень = Поворот
Это операция с постоянным временем.
Программист также должен убедиться, что родительский элемент корня указывает на точку поворота после поворота. Кроме того, программист должен учитывать, что эта операция может привести к новому корню для всего дерева, и позаботиться об обновлении указателей соответствующим образом.
Неизменность порядка [ править ]
Вращение дерева делает обход двоичного дерева инвариантным . Это означает, что порядок элементов не изменяется, когда вращение выполняется в любой части дерева. Вот порядок обхода деревьев, показанных выше:
Левое дерево: ((A, P, B), Q, C) Правое дерево: (A, P, (B, Q, C))
Вычислить одно из другого очень просто. Ниже приведен пример кода Python, который выполняет это вычисление:
def right_rotation ( treenode ): "" "Повернуть указанное дерево вправо." "" left , Q , C = treenode A , P , B = left return ( A , P , ( B , Q , C ))Другой способ взглянуть на это:
Правый поворот узла Q:
Пусть P будет левым потомком Q.Установите левый дочерний элемент Q как правого ребенка P.[Установить родителя правого ребенка P на Q]Установите правого ребенка P на Q.[Установить родителя Q на P]
Левое вращение узла P:
Пусть Q будет правым ребенком Р.Сделайте правого потомка P левым потомком Q.[Установите для родителя левого ребенка Q значение P]Установите левым потомком Q на P.[Установить родителя P на Q]
Все остальные подключения оставлены как есть.
Есть также двойные вращения , которые представляют собой комбинации левого и правого вращения. Двойной левый поворот на X может быть определен как правое вращение на право ребенка X с последующим левым вращением на X; аналогично, двойное правое вращение в X можно определить как левое вращение у левого дочернего элемента X, за которым следует правое вращение в X.
Вращения вала используются в ряде дерева структур данных , таких как AVL деревья , красно-черных деревьев , WAVL деревьев , расширяющихся деревьев и treaps . Для них требуется только постоянное время, поскольку они являются локальными преобразованиями: они работают только на 5 узлах и не нуждаются в проверке остальной части дерева.
Вращения для ребалансировки [ править ]
Дерево можно перебалансировать с помощью вращения. После вращения сторона вращения увеличивает свою высоту на 1, в то время как сторона, противоположная вращению, уменьшает свою высоту аналогичным образом. Следовательно, можно стратегически применять вращения к узлам, левый дочерний элемент и правый дочерний элемент которых отличаются по высоте более чем на 1. Самобалансирующиеся деревья двоичного поиска применяют эту операцию автоматически. Типом дерева, в котором используется этот метод перебалансировки, является дерево AVL .
Расстояние вращения [ править ]
Можно ли вычислить расстояние вращения между двумя двоичными деревьями за полиномиальное время?
Расстояние вращения между любыми двумя двоичными деревьями с одинаковым количеством узлов - это минимальное количество поворотов, необходимых для преобразования одного в другой. С этим расстоянием набор двоичных деревьев с n узлами становится метрическим пространством : расстояние симметрично, положительно, когда даны два разных дерева, и удовлетворяет неравенству треугольника .
Вопрос о том, существует ли алгоритм с полиномиальным временем для вычисления расстояния вращения, остается открытым . Тем не менее, алгоритм Фордхэма вычисляет расстояние за линейное время, но допускает только 2 вида поворотов: (ab) c = a (bc) и a ((bc) d) = a (b (cd)). Алгоритм Фордхэма основан на классификации узлов на 7 типов, а таблица поиска используется для определения количества оборотов, необходимых для преобразования узла одного типа в другой.
Дэниел Слейтор , Роберт Тарьян и Уильям Терстон показали, что расстояние вращения между любыми двумя деревьями n- узлов (для n ≥ 11) не превышает 2 n - 6, и что некоторые пары деревьев так далеко друг от друга, как только n достаточно большой. [1] Лайонел Пурнин показал, что на самом деле такие пары существуют всякий раз, когда n ≥ 11. [2]
См. Также [ править ]
- Дерево AVL , красно-черное дерево и развернутое дерево - виды структур данных двоичного дерева поиска, которые используют вращения для поддержания баланса.
- Ассоциативность бинарной операции означает, что выполнение поворота дерева над ней не меняет конечный результат.
- Алгоритм Day-Стаут-Уоррен уравновешивает несбалансированный BST.
- Решетка Тамари , частично упорядоченный набор, в котором элементы могут быть определены как бинарные деревья, а порядок между элементами определяется вращением дерева.
Ссылки [ править ]
- ^ Слейтор, Дэниел Д .; Тарджан, Роберт Э .; Тёрстон, Уильям П. (1988), "Поворот расстояния, триангуляции, и гиперболической геометрии", журнал Американского математического общества , 1 (3): 647-681, DOI : 10,2307 / 1990951 , JSTOR 1990951 , МР 0928904.
- ^ Pournin, Лионель (2014), "Диаметр associahedra", Прогресс в области математики , 259 : 13-42, Arxiv : 1207,6296 , DOI : 10.1016 / j.aim.2014.02.035 , МР 3197650 .
Внешние ссылки [ править ]
- Учебное пособие AVL Tree Rotations (RTF) от Джона Харгроува
