ч,Т2. Сравнение

ТЗ. Перемещение влево

Успешное завершение

Т4. Перемещение вправо

LLINK = A\

Т5. Вставка в дерево

/RLINK=:A

Рис, 11. Поиск по дереву и вставка.

Первые 13 строк программы выполняют поиск, следующие И - вставку. Время работы фазы поиска составляет (7С -(- С1 - 35 -f 4) и, где

С - количество выполненных сравнений; С1 - количество сравнений, когда К < KEY(P); С2 - количество сравнений, когда К > KEY(P);

5 - 1 при успешном и О при неудачном поиске.

В среднем имеем С1 = (С + 5), поскольку С1 -f- С2 = С, а С1 - 5 имеет то же распределение вероятностей, что и С2; таким образом, время работы программы -

около (7.5С - 2.55 + 4)u. Как видим, это лучшее значение, чем при бинарном поиске с неявными деревьями (см. программу 6.2.1С). Продублировав код, как это было сделано в программе 6.2.IF, мы можем избавиться от строки 08 программы Т, уменьшая время работы до (6.5С - 2.55 + 5)и. При неудачном поиске фаза вставки займет дополнительное время - 14и или 15и.

Алгоритм Т легко адаптировать для работы с ключами и записями переменной длины. Например, если мы распределяем имеющуюся память последовательно, по принципу LIFO ("последним вошел - первым вышел"), можно очень легко создавать узлы различных размеров - первое слово в (1) может указывать размер записи. Такое достаточно эффективное использование памяти делает алгоритмы таблиц символов, основанные на деревьях, особенно привлекательными для использования в компиляторах, ассемблерах и загрузчиках.

А как насчет наихудшего варианта? Программисты зачастую скептически относятся к алгоритму Т при первом знакомстве с ним. Ведь если бы ключи из рис. 10 поступали в алфавитном порядке - AQUARIUS, ..., VIRGO - вместо календарного, алгоритм построил бы вырожденное дерево, соответствующее последовательному поиску. Все поля LLINK в этом дереве были бы пустыми. Точно так же поступление ключей в несколько необычном порядке -

AQUARIUS, VIRGO, ARIES, TAURUS, CANCER, SCORPIO, CAPRICORN, PISCES, GEMINI, LIBRA, LEO -

привело бы к построению зигзагообразного дерева, что ничуть не сокращает время поиска (постройте его сами - и убедитесь).

С другой стороны, для успешного поиска по дереву, изображенному на рис. 10, требуется в среднем всего 3 сравнений; это лишь ненамного превышает минимально возможное количество 3, которое достигается при поиске по наилучшему из возможных бинарных деревьев.

При работе с хорошо сбалансированным деревом время поиска примерно пропорционально log Л; однако в случае вырожденного дерева время поиска становится пропорциональным Л. В упр. 2.3.4.5-5 доказывается, что среднее время поиска пропорционально VN в предположении равновероятности всех бинарных деревьев с Л узлами. Чего же нам следует ожидать от алгоритма Т?

К счастью, можно доказать, что поиск по дереву требует лишь около 21пЛ « 1.386 IgA сравнений, если ключи вставляются в дерево в случайном порядке. На практике в основном встречаются хорошо сбалансированные деревья, в то время как вырожденные деревья появляются редко.

Доказать это утверждение на удивление легко. Предположим, что каждая из Л! возможных перестановок Л ключей с равной вероятностью используется для построения дерева путем последовательных вставок. Число сравнений, необходимых для поиска ключа, ровно на одно больше числа сравнений, необходимых для его вставки в дерево. Таким образом, если См - среднее количество сравнений при успешном поиске, а С - при неудачном, то

Cn = 1 +--• (2)

Однако согласно соотношению между длинами внутреннего и внешнего путей (6.2.1-(2))

Cn={i + ) См - 1. (3)

Объединяя (3) и (2), получим

{N + l)Cr,, = 2N + Cl) + C[+--- + Cn-i. (4)

Это рекуррентное соотношение легко решается: вычтя следующее равенство

iVCJv-i = 2(iV - 1) + + С( + • • • + Сг 2 из предыдущего, мы получим

(iV+l)C;v--Ctv-i = 2 + С 1, следовательно, Cjv = Cjv-i + 2/(iV + 1). Так как Cq = О, то

См = 2HN+1 - 2. (5)

Применив (3) и выполнив некоторые упрощения, получим требуемый результат:

Cv=2(l + )ffv-3. (6)

В упр. 6-8 приводится более детальная информация - можно определить не только средние значения Сдг и Cj, но и их точные распределения вероятностей.

Сортировка путем вставки в дерево. Алгоритм Т был разработан для поиска, однако он может применяться и в качестве основы алгоритма внутренней сортировки; его можно рассматривать как естественное обобщение вставки в список - алгоритма 5.2.1L. Если этот алгоритм будет корректно реализован, то среднее время его работы лишь незначительно превысит время работы лучших алгоритмов, обсуждавшихся в главе 5. После того как дерево построено, остается только симметрично его обойти (алгоритм 2.3.IT); так мы получим записи в рассортированном виде.

Тем не менее следует предпринять определенные меры предосторожности - требуются некоторые отличия на шаге Т2 при К - KEY(P) в связи с тем, что нашей целью является не поиск, а сортировка. Одно из возможных решений - считать, что К - КЕУ(Р) эквивалентно К > KEY(P). Сортировка при этом будет вполне корректна (отметим, что записи с одинаковыми ключами необязательно должны находиться в смежных узлах - важно, чтобы они последовательно встречались при симметричном обходе дерева). Однако при наличии большого количества повторяющихся ключей этот метод может дать плохо сбалансированное дерево, и процесс сортировки окажется замедленным. Еще одним решением может служить хранение списка записей с одним и тем же ключом для каждого из узлов. В этом случае потребуется дополнительное поле ссылок, однако при большом числе повторяющихся ключей такая сортировка окажется более быстрой.

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

Интересно отметить тесную взаимосвязь между анализом сортировки путем вставки в дерево и анализом "быстрой сортировки" хотя, на первый взгляд, эти