Анализ длины внутреннего пути в бинарном дереве поиска

Question

Я читаю главу о деревьях в книге Марка Аллена Вайса «Структуры данных и алгоритмы». Вот фрагмент текста.

Пусть D (n) - длина внутреннего пути для некоторого дерева T из n узлов. D (1) = 0. Дерево n-узлов состоит из левого поддерева i-узла и (n - i - 1) -узел правого поддерева плюс корень на глубине ноль для 0 <= i <n. D (я) это длина внутреннего пути левого поддерева по отношению к его корень. В главном дереве все эти узлы на один уровень глубже. Такой же держит для правильного поддерева. Таким образом, мы получаем повторение </p>

D (n) = D (i) + D (n - i -1) + n -1

Если все размеры поддеревьев одинаково вероятны, что верно для двоичного деревья поиска (поскольку размер поддерева зависит только от относительного ранга первого элемента, вставленного в дерево), но не двоичные деревья, тогда среднее значение как D (i), так и D (n - i -1) составляет (1 / n) сумму от j = от 0 до n-1 из D (j). Это дает

D (n) = (2 / n) (сумма от j = 0 до n-1 для D (j)) + (n-1).

Приведенная выше повторяемость получает средние значения D (n) = O (nlogn).

Ниже приведены мои вопросы по фрагменту текста выше.

1. Что автор имеет в виду "поскольку размер поддерева зависит только от относительного ранга первого элемента, вставленного в дерево"?
2. Как автор достиг среднего значения O (nlogn) из D (n)? Кто-нибудь может показать мне шаги, необходимые для достижения упомянутого результата?

Спасибо!

Answer 1

О вашей первой точке:

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

Поэтому размер поддерева зависит только от относительного ранга первого вставленного элемента.

По поводу вашего второго пункта у меня нет решения, но я бы начал так:

Вы можете сначала преобразовать сумму:

Вы знаете, что sum(j=0 to n, of j ) = n*(n-1)/2

, затем n-1 = 2/n*sum(j=0 to n-1, of 1 ) +2/n*n = 2/n*sum(j=0 to n-1, of j ) + 2

Так как D(n) = (2/n)(sum from j = 0 to n-1 of D(j)) + (n-1), вы получите новую формулу

D(n) = (2/n)(sum from j = 0 to n-1 of (D(j) + j)) + 2 (1)

теперь вы можете выразить Дн через Дн-1

вы найдете (если я прав):

D(n)= (n+1)/n*D(n-1) + 2  (2)

Затем попытайтесь выразить Dn как n * Sum (1 / k), что эквивалентно nln (n) ...

из приведенной выше формулы (2) вы получите (вы можете попробовать написать):

D(n) = n+1 * SUM( 2 /k for k=1 to n) +2 ... which is a O(n ln(n))

Скажите, если у вас есть еще вопросы по этому доказательству

Надеюсь, это поможет

---

РЕДАКТИРОВАТЬ: подробности (2)

D(n) = (2/n)(sum from j = 0 to n-1 of (D(j) + j)) + 2

=> D(n) = (2/n)(sum from j = 0 to n-2 of (D(j) + j)) + 2 + (2/n)*(D(n-1)+n-1)

=> D(n) = ((n-1)/n)* [ 2/(n-1) *(sum from j = 0 to n-2 of (D(j) + j)) + 2]  + 2 + (2/n)*D(n-1)

note: the +2 between the brackets comes  from (2/n)*(D(n-1)+n-1) =  (2/n)*D(n-1) + 2 *(n-1)/n

between the brackets [] you have D(n-1) then :

=>  D(n) = ((n-1)/n)* D(n-1)  + 2 + (2/n)*D(n-1)

=> D(n) = (n+1)/n*D(n-1) + 2