Повороты в двоичном дереве: сохранение порядка листьев и балансировка
Tree rotation
Повороты деревьев в теории графов: локальные изменения структуры бинарного дерева без изменения порядка элементов. Оптимизация высоты и производительности.
Сравнивайте с английским: нажмите на абзац — оригинал откроется в окне. Кнопка EN под абзацем показывает его прямо в тексте.
Содержание
Введение
Локальное изменение в двоичном дереве, сохраняющее порядок листьев.
A local change in a binary tree that preserves leaf order
В дискретной математике вращение дерева — это операция над двоичным деревом, изменяющая его структуру, не нарушая при этом порядок элементов. Вращение дерева перемещает один узел вверх по дереву, а другой — вниз. Оно используется для изменения формы дерева, и в частности для уменьшения его высоты за счет перемещения меньших поддеревьев вниз и больших — вверх, что приводит к повышению эффективности многих операций с деревом. В различных описаниях существует непоследовательность в определении направления вращения. Одни утверждают, что направление вращения отражает направление движения узла при вращении (например, левый потомок, перемещающийся на место родителя, соответствует правому вращению), в то время как другие считают, что направление вращения отражает, какое поддерево вращается (левое поддерево, перемещающееся на место родителя, соответствует левому вращению, что противоположно предыдущему). В данной статье используется подход, основанный на направлении движения вращающегося узла.
In discrete mathematics, tree rotation is an operation on a binary tree that changes the structure without interfering with the order of the elements. A tree rotation moves one node up in the tree and one node down. It is used to change the shape of the tree, and in particular to decrease its height by moving smaller subtrees down and larger subtrees up, resulting in improved performance of many tree operations. There exists an inconsistency in different descriptions as to the definition of the direction of rotations. Some say that the direction of rotation reflects the direction that a node is moving upon rotation (a left child rotating into its parent's location is a right rotation) while others say that the direction of rotation reflects which subtree is rotating (a left subtree rotating into its parent's location is a left rotation, the opposite of the former). This article takes the approach of the directional movement of the rotating node.
Иллюстрация
Операция поворота вправо, как показано на соседнем изображении, выполняется с Q в качестве корня и, следовательно, является поворотом вправо относительно Q или с корнем в Q. Эта операция приводит к вращению дерева по часовой стрелке. Обратная операция – левое вращение, которое приводит к движению против часовой стрелки (левое вращение, показанное выше, имеет корень в P). Ключ к пониманию принципа работы вращения – понимание его ограничений. В частности, порядок листьев дерева (при чтении слева направо, например) не должен измениться (другой способ рассмотреть это – порядок посещения листьев при обходе дерева в порядке возрастания должен оставаться прежним после операции). Другое ограничение – основное свойство двоичного дерева поиска, а именно, что все узлы в правом поддереве больше родительского узла, а все узлы в левом поддереве меньше родительского узла. Обратите внимание, что правый потомок левого потомка корня поддерева (например, узел B на диаграмме для дерева с корнем в Q) может стать левым потомком корня, который сам становится правым потомком "нового" корня во вращаемом поддереве, не нарушая ни одного из этих ограничений. Как видно на диаграмме, порядок листьев не изменяется. Обратная операция также сохраняет порядок и является вторым типом вращения. Предполагая, что это двоичное дерево поиска, как указано выше, элементы следует интерпретировать как переменные, которые можно сравнивать друг с другом. Буквы латинского алфавита слева используются в качестве заполнителей для этих переменных. В анимации справа заглавные буквы латинского алфавита используются в качестве заполнителей для переменных, а заглавные греческие буквы – в качестве заполнителей для целого набора переменных. Круги представляют отдельные узлы, а треугольники – поддеревья. Каждое поддерево может быть пустым, состоять из одного узла или содержать любое количество узлов.
The right rotation operation as shown in the adjacent image is performed with Q as the root and hence is a right rotation on, or rooted at, Q. This operation results in a rotation of the tree in the clockwise direction. The inverse operation is the left rotation, which results in a movement in a counter clockwise direction (the left rotation shown above is rooted at P). The key to understanding how a rotation functions is to understand its constraints. In particular the order of the leaves of the tree (when read left to right for example) cannot change (another way to think of it is that the order that the leaves would be visited in an in order traversal must be the same after the operation as before). Another constraint is the main property of a binary search tree, namely that all nodes in the right subtree are greater than the parent and all nodes in the left subtree are less than the parent. Notice that the right child of a left child of the root of a sub tree (for example node B in the diagram for the tree rooted at Q) can become the left child of the root, that itself becomes the right child of the "new" root in the rotated sub tree, without violating either of those constraints. As seen in the diagram, the order of the leaves doesn't change. The opposite operation also preserves the order and is the second kind of rotation. Assuming this is a binary search tree, as stated above, the elements must be interpreted as variables that can be compared to each other. The alphabetic characters to the left are used as placeholders for these variables. In the animation to the right, capital alphabetic characters are used as variable placeholders while lowercase Greek letters are placeholders for an entire set of variables. The circles represent individual nodes and the triangles represent subtrees. Each subtree could be empty, consist of a single node, or consist of any number of nodes.
Ротации для восстановления баланса
Дерево может быть сбалансировано с помощью вращений. После вращения, сторона, вокруг которой выполнено вращение, увеличивает свою высоту на 1, а противоположная сторона уменьшает свою высоту на ту же величину. Таким образом, вращения можно стратегически применять к узлам, у которых разница в высоте между левым и правым потомками превышает 1. Самобалансирующиеся двоичные деревья поиска применяют эту операцию автоматически. Дерево AVL – это один из типов деревьев, использующих эту технику балансировки.
A tree can be rebalanced using rotations. After a rotation, the side of the rotation increases its height by 1 whilst the side opposite the rotation decreases its height similarly. Therefore, one can strategically apply rotations to nodes whose left child and right child differ in height by more than 1. Self balancing binary search trees apply this operation automatically. A type of tree which uses this rebalancing technique is the AVL tree.
Расстояние вращения
Расстояние вращения между любыми двумя двоичными деревьями с одинаковым количеством узлов — это минимальное количество вращений, необходимое для преобразования одного дерева в другое. При этом расстоянии множество двоичных деревьев с n узлами образует метрическое пространство: расстояние симметрично, положительно для различных деревьев и удовлетворяет неравенству треугольника. Остаётся открытым вопрос о существовании алгоритма, работающего за полиномиальное время, для вычисления расстояния вращения, хотя для некоторых вариантов задачи о расстоянии вращения такие алгоритмы существуют. Дэниел Слейтор, Роберт Тарджан и Уильям Терстон показали, что расстояние вращения между любыми двумя деревьями с n узлами (при n ≥ 11) не превышает 2n − 6, и что некоторые пары деревьев могут находиться на таком максимальном расстоянии, как только n станет достаточно большим. Лайонел Пурнин доказал, что такие пары действительно существуют при n ≥ 11.
The rotation distance between any two binary trees with the same number of nodes is the minimum number of rotations needed to transform one into the other. With this distance, the set of n node binary trees becomes a metric space: the distance is symmetric, positive when given two different trees, and satisfies the triangle inequality. It is an open problem whether there exists a polynomial time algorithm for calculating rotation distance, though several variants of the rotation distance problem admit polynomial time algorithms. Daniel Sleator, Robert Tarjan and William Thurston showed that the rotation distance between any two n node trees (for n ≥ 11) is at most 2n − 6, and that some pairs of trees are this far apart as soon as n is sufficiently large. Lionel Pournin showed that, in fact, such pairs exist whenever n ≥ 11.