Вращение деревьев — Tree rotation
В дискретной математике , вращение вала представляет собой операцию на бинарное дерево , которое изменяет структуру , не нарушая порядка элементов. Вращение дерева перемещает один узел вверх по дереву и один узел вниз. Он используется для изменения формы дерева и, в частности, для уменьшения его высоты путем перемещения меньших поддеревьев вниз и более крупных поддеревьев вверх, что приводит к повышению производительности многих операций с деревом.
Существует несоответствие в различных описаниях определения направления вращения . Некоторые говорят, что направление вращения отражает направление, в котором узел движется при вращении (левый дочерний элемент, вращающийся в положение своего родителя, является правым вращением), в то время как другие говорят, что направление вращения отражает, какое поддерево вращается (левое поддерево, вращающееся в расположение его родителя — левое вращение, противоположное предыдущему). В этой статье используется подход направленного движения вращающегося узла.
Иллюстрация
Операция правого вращения , как показано на соседнем изображении выполняется с Q как корень и , следовательно , является правым вращение на или с корнем, Q . Эта операция приводит к повороту дерева по часовой стрелке. Обратной операцией является левое вращение, которое приводит к движению против часовой стрелки (левое вращение, показанное выше, основано на P ). Ключом к пониманию того, как работает вращение, является понимание его ограничений. В частности, порядок листьев дерева (например, при чтении слева направо) не может измениться (другой способ думать об этом состоит в том, что порядок, в котором листья будут посещаться при обходе по порядку, должен быть таким же после операция как раньше). Еще одно ограничение — это главное свойство двоичного дерева поиска, а именно то, что правый дочерний элемент больше, чем родитель, а левый дочерний элемент меньше, чем родительский. Обратите внимание, что правый дочерний элемент левого дочернего элемента корня поддерева (например, узел B на диаграмме для дерева с корнем Q) может стать левым дочерним элементом корня, который сам становится правым дочерним элементом » new «корень повернутого поддерева, не нарушая ни одного из этих ограничений. Как видно на схеме, порядок листьев не меняется. Противоположная операция также сохраняет порядок и является вторым видом вращения.
Предполагая, что это двоичное дерево поиска , как указано выше, элементы должны интерпретироваться как переменные, которые можно сравнивать друг с другом. Буквенные символы слева используются в качестве заполнителей для этих переменных. В анимации справа заглавные буквенные символы используются в качестве заполнителей переменных, а строчные греческие буквы являются заполнителями для всего набора переменных. Кружки представляют отдельные узлы, а треугольники — поддеревья. Каждое поддерево может быть пустым, состоять из одного узла или состоять из любого количества узлов.
Подробная иллюстрация
Когда поддерево вращается, сторона поддерева, на которой оно вращается, увеличивает свою высоту на один узел, в то время как другое поддерево уменьшает свою высоту. Это делает вращение дерева полезным для балансировки дерева.
Рассмотрим терминологию Root для родительского узла поддеревьев, подлежащих вращению, Pivot для узла, который станет новым родительским узлом, RS для стороны вращения и OS для противоположной стороны вращения. Для корня Q на диаграмме выше RS — это C, а OS — P. Используя эти термины, псевдокод для поворота выглядит следующим образом:
Pivot = Root.OS Root.OS = Pivot.RS Pivot.RS = Root Root = Pivot
Это операция с постоянным временем.
Программист также должен убедиться, что родительский элемент корня указывает на точку поворота после поворота. Кроме того, программист должен учитывать, что эта операция может привести к новому корню для всего дерева, и позаботиться об обновлении указателей соответствующим образом.
Инвариантность порядка
Вращение дерева делает обход двоичного дерева инвариантным . Это означает, что порядок элементов не изменяется, когда вращение выполняется в любой части дерева. Вот порядок обхода деревьев, показанных выше:
Left tree: ((A, P, B), Q, C) Right tree: (A, P, (B, Q, C))
Вычислить одно из другого очень просто. Ниже приведен пример кода Python, который выполняет это вычисление:
def right_rotation(treenode): """Rotate the specified tree to the right.""" left, Q, C = treenode A, P, B = left return (A, P, (B, Q, C))
Другой способ взглянуть на это:
Let P be Q's left child. Set Q's left child to be P's right child. [Set P's right-child's parent to Q] Set P's right child to be Q. [Set Q's parent to P]
Let Q be P's right child. Set P's right child to be Q's left child. [Set Q's left-child's parent to P] Set Q's left child to be P. [Set P's parent to 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 достаточно большой. Лайонел Пурнин показал, что на самом деле такие пары существуют, когда n ≥ 11.
Смотрите также
- Дерево AVL , красно-черное дерево и развернутое дерево — разновидности структур данных двоичного дерева поиска, которые используют вращение для поддержания баланса.
- Ассоциативность бинарной операции означает, что выполнение поворота дерева над ней не меняет конечный результат.
- Алгоритм Day-Стаут-Уоррен уравновешивает несбалансированный BST.
- Решетка Тамари , частично упорядоченный набор, в котором элементы могут быть определены как бинарные деревья, а порядок между элементами определяется вращением дерева.
использованная литература
внешние ссылки
Источник
Наглядное руководство, как на самом деле инвертировать двоичное дерево
Это знаменитый вопрос, который Homebrew автор Max Howell классно ошибся в интервью Google. Надеюсь, это избавит вас от такого же несчастья!
Давайте подумаем о грубой силе — как бы мы это сделали без каких-либо хитроумных алгоритмов? Мы можем начать с очень простого ввода следующим образом:
Итак, чтобы перевернуть его по вертикали, мы начнем с 1 , где нечего переворачивать или менять местами, и он останется на месте. Мы обработали первую строку.
Переходя ко второму, мы встречаем 2 и 3 , так что мы поменяли их местами и получили:
Интересно, похоже, это перевернуло его! Неужели это так же просто, как замена местами, когда узлов больше одного?
Что, если бы у нас было более двух узлов для обмена на каждом уровне? Если бы был дополнительный уровень, он мог бы выглядеть так:
Эта последняя строка в настоящее время направлена 4 -> 5 -> 3 , но мы бы хотели, чтобы результат был 3 -> 5 -> 4 , чтобы правильно инвертировать.
Однако мы можем добиться этого, выполнив две отдельные перестановки. Обратите внимание: это то, что мы получили бы, если поменяли местами 4 и 5 , чтобы получить 5 -> 4 , а затем поменяли местами 5 -> 4 на 3 .
Итак, чтобы собрать все вместе: мы можем выполнять обход по порядку и делать своп на каждой итерации.
Предостережение, на которое указали читатели: если мы имеем дело с существенно большим двоичным деревом, то рекурсивное решение может вызвать проблемы из-за размера стека вызовов. Есть два способа обойти это:
- Использование стека для имитации рекурсии
- Используя очередь, посещая уровни один за другим в режиме BFS и меняя местами левый и правый узлы, чтобы инвертировать дерево.
Вот как выглядит окончательный код:
function invertTree(head) < if (head) < var temp = head.left; head.left = head.right; head.right = temp; invertTree(head.left); invertTree(head.right); >return head; >Источник
Малые повороты двоичного дерева
М ы уже показали, что несбалансированное ДДП имеет плохие показатели при поиске и вставке новых элементов: сложность операций стремится к n, т.о. преимущества этой структуры данных теряются. Идеальным был бы вариант, когда расстояние от вершины дерева до каждого из его листьев одинаковое или не отличается более чем на единицу. Такое сбалансированное двоичное дерево поиска будет иметь сложность порядка log(n) для операции поиска элемента, и, как следствие, вставка и удаление станут быстрее.
Двоичное дерево поиска не является самобалансирующейся структурой данных, то есть, при вставке или при удалении узлов может происходить разбалансировка дерева и увеличение времени выполнения операций. Однако, можно произвести балансировку «вручную».
Введём новую операцию — малые левый и правый повороты. Поворот дерева — это операция, которая позволяет изменить структуру дерева не меняя порядка элементов. Особенность этих операций в том, что они могут уменьшить высоту дерева. Используя эти операции для соответствующих узлов можно минимизировать высоту дерева.
Очевидно, что используя обратную операцию, наоборот, можно удлинять одну из ветвей, вытягивая её в список.
Обратите внимание – если производить поворот относительно вершины, то узел, который мы передаём, перестанет быть корнем дерева и превратится в наследника. Нужно постоянно помнить об этом, иначе можно потерять указатель на вершину дерева.
Из рисунка видно, что левый и правый малый поворот не изменяют положения ветвей L и R (Left и Right) и изменяют положение ветви C. Нужно помнить, что каждая из ветвей может быть равна NULL.
void l2rRotation(Node **root) < Node *parent = NULL, *C = NULL, *a = NULL, *b = NULL; a = (*root); parent = a->parent; b = a->right; if (b == NULL) < return; >C = b->left; b->left = a; a->right = C; if (C) < C->parent = a; > b->parent = parent; if (parent) < if (parent->left == a) < parent->left = b; > else < parent->right = b; > > a->parent = b; if (!parent) < *root = (*root)->parent; > > void r2lRotation(Node **root) < Node *parent = NULL, *C = NULL, *a = NULL, *b = NULL; b = (*root); parent = b->parent; a = b->left; if (a == NULL) < return; >C = a->right; a->right = b; b->left = C; if (C) < C->parent = b; > a->parent = parent; if (parent) < if (parent->left == b) < parent->left = a; > else < parent->right = a; > > b->parent = a; *root = (*root)->parent; >
Левый поворот позволяет укорачивать ветвь, «растянувшуюся» вправо, правый, наоборот, длинную левую ветвь. Алгоритм балансировка состоит из трёх фаз. Во-первых, мы «расплетаем» дерево, используя левый и правый поворот, превращаем его в левоассоциативную лозу (vine). У этой лозы будет m узлов. Во-вторых, мы сводим эту лозу, используя правый поворот, к дереву, у которого главная левая лоза состоит из n-1 узла, где n — это ближайшее целое число, меньше данного, равное степени двойки (целочисленный логарифм по основанию 2). В конце мы проводим следующую операцию: отмечаем, начиная с вершины, через один все узлы дерева, после чего производим относительно них поворот. Эту операцию повторяем log(n) раз. Получается сбалансированное двоичное дерево поиска.
Всё ещё не понятно? – пиши вопросы на ящик
Источник