Средняя высота бинарного дерева поиска

Question

Как вы вычисляете среднюю высоту двоичного дерева поиска при добавлении 1000 случайных целых чисел?Каков средний рост?

Answer 1

Вы можете вычислить высоту двоичного дерева, используя это рекурсивное определение:

height(empty) = 0
height(tree) = 1 + max(height(tree.left), height(tree.right))

Один из способов эмпирически измерить среднюю высоту такого дерева - многократно создать пустое дерево и добавить в него 1000 случайных элементов.Измерьте высоту каждой пробы, используя описанную выше функцию, и усредните их.

Я подозреваю, что ваша задача, вероятно, состоит в том, чтобы найти формулу для средней высоты двоичного дерева.

Answer 2

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

Мне удалось написать приложение, которое могло бы вычислить ответ на вопрос, какой была бы средняя высота, если бы вы добавили все возможные перестановки из N уникальных чисел к наивно реализованному двоичному дереву.

Ответы, которые я получил, приведены на этом графике.(Ось X - это количество элементов в дереве, синяя линия - средняя высота, а красная линия - оптимально возможная высота)

N     Average Height
2     2
16    7.039
32    9.280
64    11.679
256   16.783
343   17.896

Гранитбольшевик прав:возможно, но статистически маловероятно, что наивно реализованное дерево будет оптимальной высоты без дополнительных функций балансировки.

Сложность алгоритма составляет O (N ^ 2), и он недостаточно быстр для вычисления действительно больших чисел.

Answer 3

Это зависит от того, используете ли вы какую-либо сбалансированную древовидную структуру (например, красно-черное дерево).Поскольку вы вставляете случайные числа в двоичное дерево, было бы разумно ожидать, что средняя глубина составляет приблизительно log2 (1000) - поэтому значения 10 и 11 будут "нормальными".Я не уверен, насколько далеко это может отклониться от этого;не глубже 10 уровней, возможно, несколько глубже.Крайний случай без балансировки был бы глубиной 1000;вряд ли это произойдет со случайными числами.

Answer 4

По-видимому, простого ответа на этот вопрос не существует, хотя существует ряд числовых приближений, например:

Деврой, Люк."Замечание о высоте деревьев двоичного поиска". Журнал ACM (JACM) 33.3 (1986):489-498.

Рид, Брюс."Высота случайного двоичного дерева поиска". Журнал ACM (JACM) 50.3 (2003):306-332.

http://staff.ustc.edu.cn /~csli/graduate/algorithms/book6/chap13.htm

Эти приближения обычно принимают вид: A ln n - B ln ln n + C

Где A~4.311 и B~1.953

Поэтому, вероятно, самое полезное, что можно сказать, это то, что средняя высота для случайных вставок равна O(log n), но если вам действительно нужна числовая аппроксимация , я думаю (4.311 ln n - 1.953 ln ln n) было бы достаточно близко для большого n.

Для n=1000, что дает около 26 - что вполне соответствует экспериментальным результатам, о которых сообщалось в других источниках.

Answer 5

Этот вопрос на самом деле сложный.Ответом будет не 1000, потому что это маловероятно, но log2(1000) также маловероятно, но тем более в зависимости от того, как выращено дерево.

Если вы добавите int, пройдя по дереву, а затем наивно добавите его, дерево практически всегда будет выше log2 (1000).

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

Answer 6

это зависит от порядка добавления.Если вы начнете с наименьшего значения, то дерево будет более глубоким, потому что все новые значения будут добавлены в правильный дочерний BST.Если вы сначала добавите наибольшее значение, то левый дочерний элемент будет глубоким, в то время как правый будет пустым.

Answer 7

Независимо от того, какое дерево вы используете, средняя высота будет равна log2 (1000), как кто-то упоминал ранее.Это правда, что в зависимости от порядка вставленных чисел фактическая высота может варьироваться, но если предположить, что числа распределены случайным образом, о которых вы упоминаете, то фактическое значение чаще всего будет приближаться к ожидаемому значению (которое, опять же, равно log2 (1000))