Привет всем!

Вот возникла такая проблема. Я сделал программу стоящую АВЛ дерево и отображающую его среднюю высоту. Среднюю высоту я округляю чтобы она была целым числом. Но мне также необходимо добавить к программе вывод теоретической оценки которая вычисляется по формуле. Я нашел формулу которая дает представление о максимальной высоте а вот о средней я не нашел. Если я правильно понял то максимальная высота вычисляется по формуле (3/2)*log2(n+1) где n -это количество вершин. А как быть с средней высотой?

Максимальная высота - это самый длинный путь от корня до листа (узла, не имеющего потомков)... То что ты написал - это оценка максимальной высоты... Вот тебе и надо проверить, совпадает оценка с реальностью, или нет.

Что касается средней высоты - считаешь длины путей до каждого листа, и делишь на количество листьев.

Да с этим я разобрался Спасибо! Программа определяет среднюю высоту, но как это подтвердить теоретическими расчетами. Т.е с максимальной понятно если подставить значения вместо n то результат получается чуть больше средней высоты определенной программой, это конечно логично ведь формула расчитывает максимальную высоту. А вот как расчитать теоретическую среднюю?

Вообще-то есть информация, что:
( отсюда: http://penguin.ewu.edu/CScD327/Spr-2000/05/12/AVL_Tree.html )

Да уж настоящий контрольный выстрел  Спасибо! буду сравнивать с тем что есть.