Расчет баланса узлов дерева AVL по балансам дочерних узлов

Question

Расчет баланса узлов дерева AVL по балансам дочерних узлов

Скажем, у меня есть дерево AVL, такое, что его узлы хранят свой собственный коэффициент баланса как одно целое число.

Как я могу вычислить коэффициент баланса узла N, если я знаю коэффициент баланса как его левого, так и правого дочернего элемента.

Обратите внимание, что у меня нет rHeight и lHeight, поэтому bal(N) = lHeight - rHeight не вариант.

0

c++ data-structures binary-tree avl-tree tree-balancing

Источник

user1925742 27 дек '13 в 18:33

1 ответ

Решение

Другие вопросы по тегам c++ data-structures binary-tree avl-tree tree-balancing

user1711796 27 дек '13 в 18:54 2013-12-27 18:54 · Accepted Answer · 2013-12-27 18:54

Короткий ответ - вы не можете.

Длинный ответ:

Рассмотрим эти два дерева:

           A
        /     \
     B           C                   A
   /   \       /   \                / \
  D     E     F     G              B   C
 / \   / \   / \   / \
H   I J   K L   M N   O

У них одинаковый коэффициент баланса, но они не одинаковой высоты.

Таким образом, если у вас есть только коэффициент баланса ребенка, вы не знаете, как высоко это поддерево, поэтому вы не можете использовать только это значение для расчета коэффициента баланса родителя.