Несколько деревьев AVL из отсортированного списка?

Question

Я работаю над назначением дерева AVL, и у меня есть быстрый вопрос об их определении - нам дан отсортированный список, и мы должны сгенерировать дерево AVL из него за O(n) раз. Я завершил это (благодаря другой помощи от Stackru!), Но мой результат, хотя и допустимое дерево AVL, отличается от результата в приведенном примере. Можно ли создать несколько деревьев AVL из одного и того же отсортированного списка?

Спасибо!

Answer 1

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

Answer 2

Да, например, это два возможных дерева AVL для <1,2,3,4,5>:

(2 1 (3 4 5))

а также

(4 (2 1 3) 5)

где (a T1 T2) обозначает дерево с корнем a, левое дерево T1 и левое правое T2.