Всегда ли возможно превратить один BST в другой, используя не более O(n) поворотов дерева?

Question

Этот предыдущий вопрос спрашивает, всегда ли возможно превратить один BST для набора значений в другой BST для того же набора значений, просто используя повороты дерева (ответ - да). Однако всегда ли можно сделать это, используя не более O(n) полных поворотов дерева?

Answer 1

Да, всегда можно превратить один BST в другой, используя не более O(n) поворотов дерева. Этот ответ следует тому же общему подходу, что и другой ответ, выбирая некоторую каноническую форму дерева T* и ограничивая количество поворотов, необходимых для превращения произвольного дерева в наше каноническое дерево. Затем вы можете превратить произвольное дерево T₁ в другое дерево T₂, преобразовав T₁ в T*, а затем преобразовав T* в T₂.

Как предлагается в комментариях, вы можете выбрать свое каноническое дерево в качестве вырожденного связанного списка. Для деревьев из n узлов эта верхняя граница ограничивает число вращений, необходимых при 2n − 2.

В статье " Расстояние вращения, триангуляция и гиперболическая геометрия" Даниэль Слеатор, Роберт Тарджан и Уильям Терстон доказали, что расстояние вращения между любыми двумя двоичными деревьями n узлов не больше 2n − 6 (лучше, чем граница, которую мы получаем при преобразовании в связанный список).

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

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

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

Answer 2

Да, это всегда возможно. Я боюсь, что лучшее, что я могу сделать сейчас, - это дать вам глупый алгоритм, который доказывает, что это возможно, хотя я подозреваю, что должен быть гораздо лучший способ сделать это.

Алгоритм Day-Stout-Warren - это алгоритм, который, начиная с любого BST, использует повороты дерева для преобразования его в идеально сбалансированный BST. Он работает за время O(n) и делает O(n) полных вращений.

Итак, предположим, что вы хотите превратить одно дерево T₁ в другое дерево T_2, используя повороты дерева. Запустите Day-Stout-Warren на обоих деревьях, чтобы преобразовать их в одно и то же сбалансированное дерево T*, и запишите вращения, которые вам нужно было сделать в обоих случаях. Затем вы можете превратить T₁ в T₂, сначала выполнив все повороты, необходимые для идеально сбалансированного T₁, затем запустив обратное вращение, необходимое для превращения T₂ в сбалансированное дерево. Это превращает T₁ в T*, а затем превращает T * в T₂. Поскольку алгоритмы Дей-Стаута-Уоррена совершают только O(n) полных вращений, это также делает только O(n) полных вращений.

Я чувствую, что должен быть лучший способ сделать это, но я не совсем уверен, как этого добиться. Если я что-нибудь придумаю, я дам вам знать!