Я знаю, что глубина идеального бинарного дерева может быть вычислена из числа узлов n, взяв логарифмическую базу 2 из (N + 1) и вычтя 1, но как рассчитать среднюю глубину?
Казалось бы, он равен сумме, деленной на общее количество узлов:
[1 + 2 + 4 + 8 + ... + (ширина последней строки)] / количество узлов
Где 1 - ширина уровня, содержащего узел root, а ширина увеличивается на каждом дополнительном уровне ниже. Не уверен, где go оттуда, хотя. Я ищу численные способы оценки того, насколько хорошо бинарные деревья сбалансированы, и возможность сравнить рассчитанную среднюю глубину со средней глубиной поиска, в результате которой будут найдены данные, была бы полезной отправной точкой.