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

При заданном наборе значений возможно наличие множества различных деревьев двоичного поиска, которые могут быть сформированы из этих значений. Например, для значений 1, 2 и 3 есть пять BST, которые мы можем сделать из этих значений:

1      1      2      3      3
 \      \    / \    /      /
  2      3  1   3  1      2
   \    /           \    /
    3  2             2  1

Многие структуры данных, основанные на сбалансированных бинарных деревьях поиска, используют повороты деревьев в качестве примитива для изменения формы BST без нарушения необходимых инвариантов бинарного дерева поиска. Вращения дерева можно использовать для перемещения узла выше его родителя, как показано здесь:

                rotate
         u      right           v
        / \     ----->         / \
       v   C                  A   u
      / \       <-----           / \
     A   B      rotate          B   C
                 left

Учитывая BST, содержащий набор значений, всегда ли возможно преобразовать этот BST в любой другой произвольный BST для того же набора значений? Например, можем ли мы преобразовать любой из пяти приведенных выше BST в любой другой BST, просто используя повороты дерева?

Источник

2 ответа

Решение

Ответ на ваш вопрос зависит от того, разрешено ли вам иметь одинаковые значения в BST, которые могут отличаться друг от друга. Например, если ваш BST хранит пары ключ / значение, то не всегда возможно превратить один BST для этих пар ключ / значение в другой BST для тех же пар ключ / значение.

Причина этого заключается в том, что обход узлов в BST остается неизменным независимо от того, сколько выполнено поворотов дерева. В результате невозможно выполнить преобразование из одного BST в другое, если обход узлов не будет выполнен иначе. В качестве очень простого случая предположим, что у вас есть BST, содержащий две копии числа 1, каждая из которых снабжена различным значением (скажем, A или B). В этом случае нет способа превратить эти два дерева друг в друга, используя повороты деревьев:

       1:a            1:b
         \             \
         1:b           1:a

Вы можете проверить это, используя грубое (очень маленькое!) Множество возможных деревьев, которые вы можете сделать с помощью поворотов. Однако достаточно заметить, что обход по порядку первого дерева дает 1:a, 1:b, а обход по второму дереву дает 1:b, 1:a. Следовательно, никакого количества поворотов будет недостаточно для преобразования между деревьями.

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

В качестве простого базового случая, если в дереве нет узлов, существует только один возможный BST, содержащий эти узлы: пустое дерево. Поэтому всегда можно выполнить преобразование между двумя деревьями с нулевыми узлами в них, поскольку начальное и конечное дерево всегда должны быть одинаковыми.

Для индуктивного шага, давайте предположим, что для любых двух BST из 0, 1, 2, .., n узлов с одинаковыми значениями всегда можно преобразовать один BST в другой, используя повороты. Мы докажем, что при любых двух BST, сделанных из одинаковых значений n + 1, всегда возможно преобразовать первое дерево во второе.

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

while (target node is not the root) {
    if (node is a left child) {
        apply a right rotation to the node and its parent;
    } else {
        apply a left rotation to the node and its parent;
    }
}

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

Теперь это дает нам очень простой рекурсивный алгоритм, который мы можем использовать для преобразования любого BST в другой BST с использованием поворотов. Идея заключается в следующем. Сначала посмотрите на корневой узел второго дерева. Найдите этот узел в первом дереве (это довольно легко, так как это BST!), Затем используйте приведенный выше алгоритм, чтобы вытащить его до корня дерева. На данный момент мы превратили первое дерево в дерево со следующими свойствами:

  1. Корневой узел первого дерева является корневым узлом второго дерева.
  2. Правое поддерево первого дерева содержит те же узлы, что и правое поддерево второго дерева, но, возможно, с другой формой.
  3. Левое поддерево первого дерева содержит те же узлы, что и левое поддерево второго дерева, но, возможно, с другой формой.

Следовательно, мы могли бы затем рекурсивно применить этот же алгоритм, чтобы левое поддерево имело ту же форму, что и левое поддерево второго дерева, и чтобы правое поддерево имело ту же форму, что и правое поддерево второго дерева. Поскольку эти левые и правые поддеревья должны иметь строго не более n узлов каждый, по нашей индуктивной гипотезе мы знаем, что это всегда можно сделать, и поэтому алгоритм будет работать так, как задумано.

Подводя итог, алгоритм работает следующим образом:

  1. Если два дерева пусты, мы закончили.
  2. Найдите корневой узел второго дерева в первом дереве.
  3. Примените вращение, чтобы привести этот узел к корню.
  4. Рекурсивно измените левое поддерево первого дерева, чтобы оно имело ту же форму, что и левое поддерево второго дерева.
  5. Рекурсивно измените правое поддерево первого дерева, чтобы оно имело ту же форму, что и правое поддерево второго дерева.

Чтобы проанализировать время выполнения этого алгоритма, обратите внимание, что для применения шагов 1 - 3 требуется не более O(h) шагов, где h - высота первого дерева. Каждый узел будет выведен в корень некоторого поддерева ровно один раз, поэтому мы делаем это всего O(n) раз. Поскольку высота дерева с n узлами никогда не превышает O(n), это означает, что выполнение алгоритма занимает не более O (n2) времени. Вполне возможно, что это будет намного лучше (например, если два дерева уже имеют одинаковую форму, то это выполняется за время O(n)), но это дает хорошую границу наихудшего случая.

Надеюсь это поможет!

Источник

Для бинарных деревьев поиска это на самом деле можно сделать за O(n).

Любое дерево можно "выправить", то есть поместить в форму, в которой все узлы являются либо корнем, либо левым потомком.

Эта форма уникальна (чтение из корня дает порядок элементов)

Дерево расправляется следующим образом:

  • Для любого правого ребенка выполните левое вращение вокруг себя. Это уменьшает количество правых потомков на 1, поэтому дерево выпрямляется за O(n) поворотов.

Если A можно выпрямить в S за O(n), а B - в S за O(n), то, поскольку вращения обратимы, можно повернуть A -> S -> B за O(n).

Источник
Другие вопросы по тегам