Оценка трудоемкости поиска в случайном дереве

Обозначим значения ключей, следующих в порядке возрас­тания k₁,k₂,…,k_n. Вероятность того, что в корень попадет ключ k_i, равна 1/n. Тогда в левом поддереве будет i-1 узлов, а в правом n-i узлов. Пусть a_n – средний

Выражение в правой части содержит три слагаемых:

1. искомый узел находится в левом поддереве с вероятностью (i-1)/n и средний уровень его равен a_i-1+1

2. с вероятностью 1/n это корень и его уровень 1.

3. с вероятностью (n-i)/n искомый узел находится в правом поддереве и средний уровень его a_n-i+1

Искомая величина a_n представляет собой среднее по i для всех

(1)

Отсюда следует: (2)

а из (1) можно получить: (3)

Из (3) можно найти , и, подставив это в (2), получим:

(4)

a_n можно представить в виде: (5),где . Справедливость (5) можно проверить непосредственной подстановкой (5) в (4).

По формуле Эйлера , где - постоянная Эйлера, равная 0.571… Для больших n получим:

В заключение отметим, что, хотя среднее время поиска в случайном дереве пропорционально логарифму числа узлов, тем не менее, существует досадная

Рис.42 Примеры вырожденных деревьев