Я работаю над назначением дерева AVL, и у меня есть быстрый вопрос об их определении - нам дан отсортированный список, и мы должны сгенерировать дерево AVL из него за O (n) раз. Я завершил это (благодаря другой помощи от StackOverflow!), Но мой результат, хотя и допустимое дерево AVL, отличается от результата в приведенном примере. Можно ли создать несколько деревьев AVL из одного и того же отсортированного списка?
Спасибо!
Да. Рассмотрим вырожденный случай дерева только с двумя узлами. В этом случае любой узел может быть корневым, а другой - листом. Эти два значения эквивалентны с точки зрения общего баланса.
Да, например, это два возможных дерева AVL для <1,2,3,4,5>:
(2 1 (3 4 5))
и
(4 (2 1 3) 5)
где (a T1 T2) обозначает дерево с корнем a, левое дерево T1 и левое правое T2.