Временная сложность правильного преобразования одного двоичного дерева поиска в другое

Question

BST T1 преобразуется справа в другой BST T2, если T2 можно получить из T1, выполняя только правые повороты на T1. Мне нужно доказать, что эту операцию можно выполнить за $ O (n ^ 2) $ с правым вращением.

Предположим, нам дано, что T1 обратимо справа в T2. Я понимаю рекурсивную природу алгоритма в том, что мы сначала переносим root T2 (который должен присутствовать в самом крайнем левом пути T1, чтобы он был преобразован вправо) в root T1, а затем повторите эту процедуру для 2 поддеревьев T1.

Однако я не могу придумать пример, который демонстрирует худшее поведение. Мне удалось подумать об этих 2 деревьях, хотя я не уверен, как доказать, является ли это наихудшим сценарием.

 Tree 1                Tree 2 

          6                  1                   
         /                    \                 
        5                      2              
       /                        \               
      4                          3               
     /                            \                  
    3                              4                
   /                                \
  2                                  6
 /                                  /
1                                  5

Дерево 1 можно преобразовать вправо в T2, повернув вправо от узла 2 вперед 5 + 4 + 3 + 2 раза.

В общем, как мне найти случай, который требует $ O (n ^ 2) $ правого поворота для преобразования одного BST в другой?

Answer 1

Эскиз доказательства:

Пусть T1=(V,E), n=#V. Рассмотрим последовательность деревьев <T1 = X_0, X_1, ..., X_(t-1), X_t = T2>, возникающих в ходе повторных (правых) поворотов, начиная с T1. Для любого данного вращения пусть «якорь вращения» обозначает узел root повернутого поддерева.

Observation # 1:
Вращение любого данного поддерева не изменяет его набор вершин.

Наблюдение № 2:
В любой последовательности s правых поворотов данного поддерева каждая вершина является якорем вращения не более одного раза. (В каждом правом повороте якорь мигрирует в правое дочернее дерево. Новый root после правого вращения начинается с левого дочернего дерева; альтернативно, обратите внимание, что при каждом повороте правое дочернее дерево увеличивается на 1 вершину; таким образом, для поддерево S, максимальное число вращений #V(S)-1).

Наблюдение № 3:
Вращение вправо не меняет число поддерев.

Количество поддерев в любое дерево эквивалентно количеству доступных корней, равному #V-1. Таким образом, последовательность правых вращений максимальной длины включает в себя O(n) поддеревья с макс. #V(S)-1 (= O(n)) вращениями для каждого из них, всего O(n^2).