к этому среднему значению число случаев, когда А; - / -2 равно -1, мы получим, что при случайном удалении в среднем операция S <- LLINK(R) на шаге D3 выполняется только

1 + {1-Hn)IN (10)

раз. Это успокаивает, так как в наихудшем случае, как показано в упр. И, удаления выполняются весьма медленно.

Хотя теорема Н вполне строга и точна, в указанном виде ее нельзя применить к последовательности удалений, следующих за вставками. После удалений форма дерева остается случайной, однако относительное распределение значений в данной форме дерева может оказаться измененным, и это может привести к тому, что первая же вставка после удаления уничтожит свойство случайности формы. Этот поразительный факт, впервые обнаруженный Гарри Кноттом (Gary Knott) в 1972 году, вам придется принять на веру (см. упр. 15). Еще более удивительны эмпирические данные, накопленные Дж. Л. Эппингером (J. L. Eppinger) {САСМ 26 (1983), 663-669, 27 (1984), 235), который обнаружил, что длина пути немного уменьшается при небольшом количестве удалений и вставок, однако затем начинает увеличиваться до тех пор, пока не достигнет стабильного состояния после выполнения примерно операций удаления/вставки. Это стабильное состояние хуже поведения случайного дерева при А, большем примерно 150. Дальнейшее исследование Кульберсона (Culberson) и Мунро (Munro) (Сотр. J. 32 (1989), 68-75; Aigorftiimfca 5 (1990), 295-311) привело к правдоподобному предположению о том, что среднее время поиска в стабильном состоянии асимптотически равно у/2М/9тт. Однако Эппингер предложил простую модификацию, при которой алгоритм D и его зеркальное отражение чередуются в одном алгоритме; он обнаружил, что это приводит к отличному стабильному состоянию, в котором длина пути снижается до примерно 88% от его обычного значения для случайных деревьев. Теоретического пояснения этого факта пока не найдено.

Как упоминалось ранее, алгоритм D не проверяет случай LLINK(T) = Л, хотя это один из простейших случаев удаления. Мы можем добавить новый шаг Dl между шагами D1 и D2.

Dli. [Пуста ли ссылка LLINK?] Если LLINK(T) = Л, установить Q -f- RLINK(T) и перейти к шагу D4.

В упр. 14 показано, что алгоритм D с этим дополнительным шагом всегда оставляет дерево с той же, если не меньшей, длиной пути, что и алгоритм D; иногда же результат оказывается даже лучше ожидаемого. При комбинировании рассмотренного метода со стратегией симметричного удаления Эппингера длина пути при повторяющихся случайных удалениях/вставках уменьшается до примерно 86% от значения, получаемого при использовании вставок без удалений.

Частота обращений. Пока что мы предполагали, что каждый ключ может стать объектом поиска с одинаковой вероятностью. Однако в более общем случае следует

рассмотреть вероятности рк поиска к-го вставленного элемента (pi -Н----\-pN - 1)-

Модифицированное выражение (2) (в предположении о случайном порядке дерево остается случайным и выполняется соотношение (5)) показывает, что среднее коли-

с AT 3 С вч (TSavT) (jJeT)

- 7\ / \

/1392 /1""

Рис. 12. 31 наиболее употребительное английское слово, вставленное в порядке уменьшения частоты.

честно сравнений в случае успешного поиска составляет

1 + Jpki2Hk - 2) =2Y,PkHk - 1.

(11)

Например, если вероятности соответствуют закону Зипфа (6.1-(8)), среднее количество сравнений сводится к

Hn-1 + H/Hn

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

На рис. 12 показано дерево, полученное в результате вставки 31 наиболее часто употребляющегося английского слова в порядке убывания частоты появления в текстах. Относительные частоты, приведенные для каждого слова, взяты из Н. F. Gaines, Cryptanalysis (New York: Dover, 1956), 226. Среднее количество сравнений при успешном поиске в этом дереве равно 4.042; соответствующее значение для бинарного поиска с использованием алгоритма 6.2.1В или 6.2.1С требует 4.393 сравнений.

Оптимальные бинарные деревья поиска. Рассмотренный материал заставляет задуматься о том, какое дерево является наилучшим для поиска в таблице ключей с заданными частотами. Например, для случая с 31 наиболее употребительным словом оптимальное дерево показано на рис. 13; оно требует в среднем всего лишь 3.437 сравнений при успешном поиске.

(12)

С it 3 OnJ) this Qith

A25 j /lb49\

GD (Э (™o (TO CQ

Л22Г Обз "ist lOS 1344 1093* 292*

509*

(which)

1291

Рис. 13. Оптимальное дерево поиска для 31 наиболее употребительного английского слова.

Приступим к задаче поиска оптимального дерева. Например, при = 3 в предположении, что ключи Ki < К2 < К3 имеют вероятности p,q,r соответственно, возможны пять деревьев:

(13)

Cost: 3p+2q+r 2p+3q+r

2p+q+2r

p+3q+2r р+29+Зг

Ha рис. 14 показаны диапазоны значений р, q, г, для которых каждое из деревьев является оптимальным; сбалансированное дерево является наилучшим примерно в 45% случаев при случайном выборе р, q, г (см. упр. 21). К сожалению, при больших имеется

(2)/(iV + l)«47(4AFiV3/2)

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

До сих пор нас интересовал успешный поиск, однако на практике неудачный поиск не менее важен (более того, в некоторых специфичных задачах именно он является определяющим; случаями успешного поиска в таких задачах можно попросту пренебречь. - Прим. перев.). Например, представленные на рис. 13 слова соответствуют примерно 36% слов обычного английского текста; остальные 64%, естественно, повлияют на структуру оптимального дерева поиска.

Сформулируем задачу следующим образом. Даны 2п-Н 1 вероятностей pi,P2, •••,Рп и qo,qi,---,q„, где

Pi - вероятность того, что аргументом поиска является Ki;

qi - вероятность того, что аргумент поиска лежит между Ki и Ki+i.