Разные AVL-деревья из одного бинарного дерева поиска?

Question

Меня смущает, можем ли мы генерировать более одного дерева AVL из данного BST.

Я пытался сделать это, и я получаю ответ, но я не знаю, так ли этоправильно или неправильно.

Answer 1

Конечно. Рассмотрим следующий BST:

       [4]
       /
     [3]
     /
   [2]
   /
 [1]

Может быть реорганизовано как минимум в 2 разных дерева, которые являются правильными AVL:

#1:             #2:
     [3]             [2]
    /   \           /   \
 [1]     [4]     [1]     [4]
   \                     /
   [2]                 [3]