Средняя глубина всех узлов случайного дерева.

[Anton_74]

Решил разобраться со структурой данных - деревья. Нашел книгу - Бабичев С.В. - Лекции по алгоритмам и структурам данных. 2020.
Она доступна по ссылке. https://www.babichev.org/books/AlgoBook.pdf

На 184 странице дается формула. Вывод формулы мне не совсем понятен.

Цитата:

Определение 26. Случайное бинарное дерево T размера n — дерево, получающееся из пустого бинарного дерева поиска после добавления в него n узлов с различными ключами в случайном порядке, при условии, что все n! возможных последовательностей добавления равновероятны.

Определим его среднюю глубину.
Пусть $\overline{d}(N + 1)$ — средняя глубина всех узлов случайного дерева с $N + 1 $ узлами. Как оно получилось? Вначале был добавлен какой-то узел, пусть он имеет значение $k$. Так как как все события равновероятны, то вероятность того, что первым был добавлен именно узел $k$ есть $p_k = \frac{1}{N+1}$.


И слева и справа от этого узла есть поддеревья, возможно нулевой высоты. Они начнутся с высоты 1. В левом поддереве окажутся элементы ${0, . . . , k − 1}$, в правом — ${k + 1, . . . , N}$.

Средняя высота левого поддерева равна $\overline{d}(k)$, правого — $\overline{d}(N − k)$). Математическое ожидание высоты случайного дерева, следовательно, будет равно
$\overline{d}(N + 1) = \sum\limits_{k=0}^{N}\frac{1}{N+1}(1+\frac{k}{N}\cdot\overline{d}(k) + \frac{N-k}{N}\cdot\overline{d}(N-k));$
$\overline{d}(N + 1) = \frac{2}{N(N+1)} \sum\limits_{k=0}^{N} k \cdot \overline{d}(k).$

Используя предел
$\lim\limits_{ n \to \infty}^{} (\sum\limits_{k=1}^{n} \frac{1}{k} - ln (n)) = \gamma = const, $
получаем

$\lim\limits_{ N \to \infty}^{} (\overline{d}(N) - 2 ln(N)) \to const $

Отсюда можно сделать вывод, что и средняя глубина узлов случайного бинарного дерева, и средние времена выполнения операций вставки, удаления и поиска в случайном бинарном дереве есть $ \Theta (log_2 N)$.

Мне не совсем понятен общий вывод этой формулы, ее упрощение, и каким образом там используется предел?
Подскажите, может у кого есть какие-нибудь идеи?

[mihaild]

Какое первое утверждение вам непонятно откуда взялось?

[Anton_74]

mihaild в сообщении #1503605 писал(а):

Какое первое утверждение вам непонятно откуда взялось?

Anton_74 в сообщении #1503599 писал(а):

Средняя высота левого поддерева равна $\overline{d}(k)$, правого — $\overline{d}(N − k)$). Математическое ожидание высоты случайного дерева, следовательно, будет равно
$\overline{d}(N + 1) = \sum\limits_{k=0}^{N}\frac{1}{N+1}(1+\frac{k}{N}\cdot\overline{d}(k) + \frac{N-k}{N}\cdot\overline{d}(N-k));$

Я про вот это уравнение говорил.

[mihaild]

Ну давайте смотреть. Пусть мы на первом шаге взяли $k$-й элемент. С какой вероятностью это произойдет? Сколько будет элементов в левом поддереве? Какова будет их средняя высота?

[Anton_74]

mihaild в сообщении #1503668 писал(а):

Ну давайте смотреть. Пусть мы на первом шаге взяли $k$-й элемент. С какой вероятностью это произойдет? Сколько будет элементов в левом поддереве? Какова будет их средняя высота?

Вероятность выбора k-го узла равна $p_k$, которая не зависит от $k$.
Получается по формуле МО нужно найти сумму произведения вероятностей СВ и его значений.
$M_h = \sum\limits_{i}^{} P_i \cdot h_i. $

У меня вопрос, почему справа в скобка присутствует члены со средними величинами $\overline{d}(k)$. Как формула мат ожидания свернулась в то, что указано в cкобках?

Anton_74 в сообщении #1503631 писал(а):

$(1+\frac{k}{N}\cdot\overline{d}(k) + \frac{N-k}{N}\cdot\overline{d}(N-k));$

Я понимаю, что вероятность выбор элемента слева от к-го равна $\frac{k}{N}$, по аналогии справа $\frac{N-k}{N}$.
Но почему появилась единица в скобках тоже не соображу. Может быть я неправильно понимаю определение высоты дерева?

[mihaild]

А тут кажется где-то опечатки в формулах. Подставляя $N = 0$, получаем $\overline{d}(1) = 1$, подставляя $N = 1$ получаем $\overline{d}(2) = 1$. Это получается какое-то очень странное определение высоты дерева...
На асимптотику это, впрочем, не влияет. Попробуйте сами расписать рекурренту для мат. ожидания - она должна получиться отличной от процитированной, но похожей.