Докажите максимальное количество поворотов для двух деревьев, чтобы стать равными

Question

В книге " Введение в алгоритмы - креативный подход", вопрос 4.24:

Пусть T1 и T2 два произвольных дерева, каждое из которых имеет n узлов. Докажите, что достаточно применить не более 2n поворотов к T1, чтобы оно стало равным T2.

Для бинарных деревьев поиска я разобрался с алгоритмом:

1. Найдите элемент, который равен корню T2, назовем его target-root.

2. Используя стратегию вращения AVL, поверните целевой корень, чтобы сделать его новым корнем T1.
   Во время этого процесса может быть выполнено несколько вращений.

3. Для левого поддерева T1 и T2 обработайте их, как указано выше, рекурсивно.
   Для правого поддерева T1 и T2 обработайте их, как указано выше, рекурсивно.

Этот алгоритм, в худшем случае, работает в O(N^2).

Я не совсем понимаю фразу "произвольные деревья" и не могу понять, как сделать T1 равным T2.

Может ли кто-нибудь помочь в этом вопросе?

Answer 1

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

Вот псевдокод для алгоритма:

 //Method to make T1 equivalent to T2

    alignTree(T1,T2) {

     if(length(T1)==1)
        return

     else {

        Node k = FindRoot(T1,T2)
        rotateAbout(k)
        align(T1.left,T2.left)
        align(T1.right,T2.right)
     }


    }

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

Нет вращений : как вы можете видеть в псевдокоде, нет вращения эквивалентно pre-order обход дерева, которое O(N)

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