рева, либо на самый левый элемент его правого поддер Ясно, что такие элементы не могут иметь более одного томка. Подробно это показано в рекурсивной процедур зываемой delete (4.52). Она различает три случая: *

1. Компоненты с ключом, равным х, нет.

2. Компонента с ключом х имеет не более одного потомка

3. Компонента с ключом х имеет двух потомков. -

procedure delete {х: integer; var р: ref); var q: ref;

procedure de/(var r: ref);

begin if rl.right Ф nil then del {rsight) else

---begin-gf;Arey г\:кеу; q\.comt := r\.count;

q := r; r -:= rjJeft

end ; begin {delete}

Hp - ml then writeln ( word is not in. tree) else

if x < p].key then delete(x, p.left) else

if x > p.key then delete(x, p\.right) else

begin {delete p]} q := p;

if q].right = nil then p := q].left else

if q\.left = nil then p : = qj.right else del {q\.left);

{dispose{q)}

end [delete]

Вспомогательная рекурсивная процедура del вызывается только в 3-м случае. Она спускается вдоль самой правой ветви левого поддерева удаляемого узла и затем заменяя существенную информацию (ключ и счетчик) в q\ соотвег-ствующими значениями самой правой компоненты г| этого левого поддерева, после чего от rf можно освободиться. Пр цедуру dispose {q) можно рассматривать как обратную пр цедуре new(q). Последняя занимает память для новой KOf поненты, а первая может применяться для указания вычиС' тельной системе, что память, которую занимает f, of освободить и потом вновь использовать (некоторый вид чйс ки памяти). ,

Для иллюстрации работы процедуры (4.52) мы отсыла читателя к рис. 4.28. Задано начальное дерево (а), из ко , рого последовательно удаляются узлы с ключами 13, 1 10. Полученные деревья показаны на рис. 4.28 (Ь - е).

Рис. 4.29. Распределение весов по ветвям.

Прежде всего легко найти наихудший случай. Допустим, что ключи поступают уже в строго возрастающем (или убывающем) порядке. Тогда каждый ключ вставляется непосредственно справа (или слева) от предшествующего, и построенное дерево оказывается полностью вырожденным, т. е. оно превращается в линейный список. В этом случае средние затраты на поиск равны п/2 сравнениям. Очевидно, что в таком наихудшем случае алгоритм поиска малоэффективен, и, кажется, что наши сомнения оправдываются. Конечно, встает вопрос, насколько вероятен такой случай. Точнее, мы хо-1ели бы знать длину пути поиска, усредненную по всем п ключам и усредненную по всем п\ деревьям, которые поручаются в результате п\ перестановок п исходных различных очей. Эта задача анализа алгоритмов оказывается достаточно простой и приводится здесь не телько как типичный Ример такого анализа, но и из-за практической важности порученного результата.

Пусть даны п различных ключей со значениями 1, 2, ... >,. . Предположим, что оии появляются в случайном по-Щке. Вероятность того, что первый ключ, который стано-Чтся корневым узлом, будет иметь значение i, есть 1/п. Его евое поддерево в конце работы будет содержать i - 1 уз-j,> а правое поддерево - п - г узлов (см. рис. 4.29). Пусть Р^Дняя длина пути в левом поддереве обозначается через

Анализ поиска с включениями по дереву

Довольно естественно испытывать некоторое недоверие алгоритму поиска по дереву с включениями. Во всяком дучае, до тех пор, пока мы не узнаем более детально о его аботе, мы будем испытывать некоторые сомнения. Прежде Р многих программистов беспокоит то, что обычно мы не L?eU, каким образом будет расти дерево, и не имеем ника-!ого представления о форме, которую оно примет. Мы лишь jiQSieM догадаться, что оно, скорее всего, не будет идеально сбалансированным. Поскольку среднее число сравнений, необходимых для нахождения ключа в идеально сбалансированном дереве с п узлами, приблизительно равно A = logn, jo число сравнений в дереве, сформированном этим алгоритмом, будет больше h. Но насколько больше?

(2) -1 = 1 + -(;7угХ

с, 1, а в правом поддереве Un-i. Вновь предполагается все возможные перестановки оставшихся п - 1 ключей рали вероятны. Средняя длина пути в дереве с п узлами paj>° сумме произведений уровня каждого узла и вероятности ращения к нему. Если предположить, что все узлы ищуто' с одинаковой вероятностью, то

п

n=~YJp (4.53)

где Pi есть длина пути до узла и

В дереве на рис. 4.29 мы разделяем узлы на три класса-

1. i-1 узлов в левом поддереве имеют среднюю длину пути ai-i + 1.

2. Корень имеет длину пути, равную 1.

3. п - i узлов в правом поддереве имеют среднюю длину пути an-i+\.

Следовательно, (4.53) можно представить в виде суммы трех слагаемых:

< = K-i+I)+l4 + K .+ I). (4.54)

Искомая величина а„ теперь получается как среднее а[ для всех г= I, и, т. е. для всех деревьев с ключами 1, 2, ..., п в корне:

п

=Е ++1++1)

п

Уравнение (4.55) представляет собой реккурентное соотношение для an вида a = fi(fl;i, йг, a i). Отсюда мы можем получить более простое реккурентное соотношение вида an = h{cLn-\) следующим образом:

Из (4.55) непосредственно получаем

(1) а„=1+-5]/.а,==1+( -1)а„ , + --5]г 1=1 t=i