Есть ли формальное определение средней высоты бинарного дерева?
У меня есть вопрос по нахождению средней высоты двоичного дерева с помощью следующих двух методов:
Естественным решением может быть определение средней длины всех возможных путей от корня до листа, то есть
.
Другой вариант - определить его рекурсивно, то есть средняя высота узла - это среднее значение средних высот поддеревьев плюс один, то есть
с для листьев и для пустых слотов.л AVH 2 ( _ ) = 0
Исходя из моего текущего понимания, например, средняя высота дерева
1
/ \
2 3
/
4
is вторым методом, который использует рекурсию.
Тем не менее, я все еще не совсем понимаю, как сделать первый. неверно.
graph-theory
terminology
combinatorics
binary-trees
вневременный
источник
источник
Ответы:
Нет оснований полагать, что оба определения описывают одну и ту же меру. Вы также можете написать рекурсивно:AVH1
Ваши расчеты действительно верны (учитывая ваше определение); обратите внимание, что дерево примеров не сбалансировано по листам.
источник
Редактировать: Джефф делает хорошую точку в своем комментарии выше. Вы, вероятно, должны прочитать «правильный против неправильный» в следующем ответе как «удобный / непротиворечивый против непоследовательный».
Похоже, что ваш второй расчет неверен. Пусть высота поддерева с одним узлом (т.е. листом) равна 0. Тогда высота корня поддерева в:
Я думаю, что вы делаете первый расчет правильно, и 1,5 является правильным ответом.
источник