Расчет баланса узлов дерева AVL по балансам дочерних узлов
Скажем, у меня есть дерево AVL, такое, что его узлы хранят свой собственный коэффициент баланса как одно целое число.
Как я могу вычислить коэффициент баланса узла N, если я знаю коэффициент баланса как его левого, так и правого дочернего элемента.
Обратите внимание, что Я НЕ БУДУ иметь высоту и высоту, так bal (N) = lHeight — rHeight это не вариант.
Решение
Короткий ответ — вы не можете.
Длинный ответ:
Рассмотрим эти два дерева:
A
/ \
B C A
/ \ / \ / \
D E F G B C
/ \ / \ / \ / \
H I J K L M N O
У них одинаковый коэффициент баланса, но они не одинаковой высоты.
Таким образом, если у вас есть только коэффициент баланса ребенка, вы не знаете, как высоко это поддерево, поэтому вы не можете использовать только это значение для расчета коэффициента баланса родителя.
Другие решения
Других решений пока нет …