Int Info;

NODE *Left;

NODE *Right;

Int Rank; // для доступа по индексу

};

bool DeleteKey(NODE *Head, int Key){

// удалить Key из дерева с головой Head

NODE *Cur, *Next=NULL,*father=NULL;

// ищем узел, запоминая каждый раз отца

for(Cur=Head; Cur->Info!=Key && Cur!=NULL; Cur=Next){

if(Key<=Cur->Info){

Next=Cur->Left;

} else {

Next=Cur->Right;

}

father=Cur;

}

if(Cur==NULL){ // не нашли Key

return false;

}

// узел сur надо удалить

// может у Cur пуста правая связь ?

if(Cur->Right==NULL){

if(father->Left==Cur){

// он левый сын своего отца

father->Left=Cur->Left;

} else {

// он правый сын своего отца

father->Right=Cur->Left;

}

delete Cur;

return true;

}

// поищем последователя с пустой левой связью

// шаг вправо и вниз до упора по левым связям

Next=Cur->Right;

father=Cur;

while(Next->Left!=NULL){

father=Next;

Next=Next->Left;

}

// Next - удаляемый узел

if(father->Left==Next){

// удаляемый узел - левый сын своего отца

father->Left=Next->Right;

} else {

// удаляемый узел - правый сын своего отца

father->Right=Next->Right;

}

Cur->Info=Next->Info;

delete Next;

return true;

}

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

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

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

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.

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

9.3.2. Оптимальные деревья

Оптимальным назовем дерево, высота которого минимальна. Это означает, что у него заполнены все уровни, кроме, быть может, последнего. Алгоритм построения оптимального дерева заключается в следующем:

• отсортируем ключи и средний из них поместим в корень

• левым сыном сделаем ключ, являющийся средним среди ключей слева от корня

• правым сыном сделаем ключ, являющийся средним среди ключей справа от корня

• точно также поступим при выборе сыновей каждого из узлов.

Ниже представлен текст функции, формирующей оптимальное дерево.

const int LEFT=0;

const int RIGHT=1;

struct NODE {