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

Question

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

Answer 1

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

Мне удалось написать приложение, которое могло бы вычислить ответ на то, какой будет средняя высота, если вы добавите каждую возможную перестановку 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 2

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

Answer 3

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

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

Одним из способов эмпирически измерить среднюю высоту такого дерева является многократное создание пустого дерева и добавление к нему 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

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

Answer 7

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