методы совершенно различны. При успешной вставке ключей в изначально пустое дерево мы выполняем то же среднее число сравнений ключей, что и в алгоритме 5.2.2Q (за небольшими исключениями). Например, в случае вставки в дерево каждый ключ сравнивается с Ki, затем каждый ключ, меньший, чем Ki, сравнивается с первым ключом, меньшим, чем Ki, и т. д.; в случае быстрой сортировки каждый ключ сравнивается с первым разделяюшдм элементом К, затем каждый ключ, меньший, чем К, сравнивается с некоторым элементом, меньшим, чем К, и т. д. Среднее количество сравнений, необходимое в обоих случаях, равно NCn - N (впрочем, в алгоритме 5.2.2Q на самом деле выполняется несколько дополнительных сравнений для ускорения внутреннего цикла).

Удаление. Иногда приходится заставлять компьютер забыть одну из записей таблицы. Мы можем легко удалить узел, поле LLINK или RLINK которого равно Л; однако, если оба поддерева не пусты, мы должны проделать некоторые специальные действия, так как ссылка не может указьшать на два места одновременно.

Рассмотрим еще раз рис. 10. Как удалить из дерева корневой узел, CAPRICORN? Одно из решений состоит в удалении следующего по алфавиту узла, ссылка LLINK которого пуста, и его вставке на место узла, который надо удалить. Например, на рис. 10 мы можем удалить GEMINI, а затем заменить CAPRICORN значением GEMINI. Это позволит сохранить порядок элементов таблицы. В приведенном далее алгоритме содержится детальное описание такого процесса.

Алгоритм D (Удаление из дерева (Tree deletion)). Пусть Q - переменная, указывающая на узел дерева поиска, представленного, как в алгоритме Т. Алгоритм предназначен для удаления этого узла, причем дерево останется бинарным деревом поиска. (На практике имеем либо Q = ROOT, либо Q = LLINK(Р), либо Q = RLINK(Р) для некоторого узла дерева. Алгоритм изменяет значение Q с учетом проведенного удаления.)

D1. [Пуста ли ссылка RLINK?] Установить Т Q. Если RLINK(Т) = Л, установить Q <- LLINK(T) и перейти к шагу D4. (Например, если Q = RLINK(P) для некоторого Р, мы можем присвоить RLINK(P) LLINK(Т).)

D2. [Поиск преемника.] Установить R <- RLINK(Т). Если LLINK(R) = Л, присвоить LLINK (R) -f- LLINK (Т), Q -f- R и перейти к шагу D4.

D3. [Поиск пустой ссылки LLINK.] Установить S LLINK(R). Затем, если LLINK(S) ф Л, присвоить R S и повторять этот шаг до тех пор, пока не будет получено LLINK(S) = Л. (Теперь S будет равно Q$, следующему за Q элементу при симметричном обходе.) И, наконец, установить LLINK (S) LLINK (Т), LLINK(R) -i- RLINK(S), RLINK(S) -f- RLINK(T), Q -f- S.

D4. [Освобождение узла.] Выполнить AVAIL T, т. e. вернуть удаленный узел в пул свободной памяти.

Читатель может проверить работоспособность данного алгоритма, удаляя узлы AQUARIUS, CANCER и CAPRICORN на рис. 10; каждый из этих случаев имеет свои особенности. Ос(,)бо придирчивый читатель, конечно, обратит внимание на то, что случай RLINK (Т) ф Л, LLINK (Т) = Л отдельно не выделен. Мы отложили обсуждение этого специального случая "на потом" поскольку в приведенном виде алгоритм обладает некоторыми интересными свойствами.

Алгоритм D представляется весьма несимметричным, и создается впечатление, что длинная цепь удалений разбалансирует дерево (и все оценки эффективности работы при этом потеряют силу). Однако "все не так, как на самом деле" и вырождения не будет.

Теорема Н (Т. Н. Хиббард (Т. N. Hibbard), 1962.) После удаления элемента из случайного дерева по алгоритму D дерево остается случайным.

[Читателям, которым математика не доставляет никакого удовольствия, настоятельно рекомендуется пропустить все до формулы (10).] Эта формулировка, естественно, несколько туманна. Сформулируем теорему более строго. Пусть Т представляет собой дерево из п элементов и пусть Р{Т) - вероятность появления Т, если его ключи вставляются в случайном порядке согласно алгоритму Т. Одни деревья более вероятны, чем другие. Пусть Q(T) - вероятность того, что после вставки случайным образом с помощью алгоритма Т п --1 элементов и удаления любого из них (выбранного наудачу) по алгоритму D получится дерево Т. При вычислении Р(Т) предполагается, что все п! перестановок ключей равновероятны; при вычислении Q{T) предполагается равновероятность (п-Н 1)! {п + 1) перестановок ключей и выбора удаляемого ключа. Теорема гласит, что для всех Т Р{Т) = Q{T).

Доказательство. По условию теоремы равновероятны не деревья, а перестановки, поэтому доказывать теорему мы будем, рассматривая в качестве случайных объектов перестановки. Сначала определим удаление из перестановки, а затем докажем, что случайный элемент, удаленный из случайной перестановки, оставляет перестановку случайной.

Пусть oi 02 ... On+i - перестановка множества {1,2,... ,п-Н1}; мы хотим определить операцию удаления щ, которая даст в результате перестановку bib-.-bn множества {1,2,... ,п}. Эта операция должна соответствовать алгоритмам Т и D, так что, если мы начнем с дерева, сконструированного последовательностью вставок 01,02,...,а„+1, и удалим а,, перенумеровав затем ключи от 1 до п, получится дерево, которое может быть построено последовательностью вставок bi Ьг • • • Ьп-

Такую операцию удаления можно легко определить. Возможны два случая.

Случай 1. Oi = п + 1 или а, -Н 1 = Oj для некоторого j < i. (Это соответствует условию RLINK(aj) = Л.) Удаляем из последовательности и вычитаем единицу из каждого элемента, большего, чем Oj.

Случай 2. Oi -Ь 1 = Oj для некоторого j > i. Заменим а, элементом Oj, удалим uj из его первоначального положения и вычтем единицу из каждого элемента, большего, чем а.

Рассмотрим, например, перестановку 4 6 1 3 5 2. Если пометить элемент, который должен быть удален, кружком, получим

06 1352 = 45132 46 105 2 = 3 5 1 4 2

401352=41352 461302=45132.

4 603 52 = 35124 4613 50= 3 5 1 2 4

Поскольку имеется {п + 1)\{п + 1) возможных операций удаления, теорема будет доказана, если мы сможем показать, что каждая перестановка {1,2,..., п) является результатом в точности (п + 1) удалений.

Пусть bib2...bn - перестановка множества {1,2,..., п}. Мы определим (п+1) удалений, по одному для каждой пары г, j (1 < i,j < п + 1). Удаление для i < j таково:

b[... bU®bi+i ...bj x{bi+l)bj ...bn. (7)

Здесь и далее b означает либо bk, либо 6 + 1, в зависимости от того, является ли Ьк меньше, чем помеченный элемент. Такое удаление соответствует случаю 2. Удаление для i > j таково:

b[...b ,(bj)bl..bn; (8)

оно соответствует случаю 1.

И наконец, если i = j, мы имеем другой случай 1, а именно

b[...bU&bl..bn. (9)

В качестве примера примем п = 4 и рассмотрим 25 удалений, приводящих к перестановке 3 14 2.

Помеченный элемент всегда находится в г-й позиции; для фиксированного i мы строили п + 1 различных удалений, по одному для каждого j. Таким образом, для каждой перестановки fti • • - Ьп построено (п + 1) различных удалений. Так как возможны только (п + 1)п! удалений, мы должны найти их все.

Доказательство теоремы Н не только описывает результат удалений, но также помогает проанализировать среднее время удаления. В упр. 12 показано, что при удалении случайного элемента из случайной таблицы шаг D2 будет выполняться меньше чем в половине случаев.

Теперь рассмотрим, как часто вьшолняется цикл на шаге D3. Предположим, что мы удаляем узел на уровне / и внешний узел, при симметричном обходе следующий непосредственно за ним, находится на уровне к. Например, при удалении узла CAPRICORN на рис. 10 / = О и А; = 3, так как узел [t] находится на уровне 3. Если А; = / + 1, то на шаге D1 RLINK(T) = Л; если А; > Z + 1, то на шаге D3 мы выполним присвоение S f- LLINK (R) ровно А; - / - 2 раз. Среднее значение / равно (длина внутреннего пути)/Л; среднее значение А; -

(длина внешнего пути - расстояние до крайнего слева внешнего узла) /N.

Расстояние до крайнего слева внешнего узла равно числу лево-правых минимумов вставляемой последовательности, так что среднее значение этой величины согласно анализу в разделе 1.2.10 составляет Hn- Поскольку длина внешнего пути превышает длину внутреннего пути на 2Л, среднее значение А; - / - 2 равно -Hn/N. Добавляя