Д. Кнут - Искусство программирования том 3 (2-е издание) - 2001 (Часть 2) (1119371), страница 19
Текст из файла (страница 19)
Пусть Ь| 52... ܄— перестановка множества (1, 2,..., и). Мы определим (н+1)э удалений, по одному для каждой пары т',,у (1 < 1,.у < и + 1). Удаление для 1 < т' таково: Ь',... Ь*, ДЬ; Ьып ... Ь,', (Ь;+1) Ь„' ... Ь'„. Р) Здесь и далее Ь~~ означает либо Ью либо Ь| + 1, в зависимости от того, является ли Ьа меньше, чем помеченный элемент. Такое удаление соответствует случаю 2.
Удаление для 1 > ) таково: Ь',... Ь',,СЬ,)Ь',....Ь„'; (8) оно соответствует случаю 1. И наконец, если 1 = 1, мы имеем другой случай 1, а именно Ь~... Ь',, (й+1) Ь,'... Ь'„. В качестве примера примем и = 4 и рассмотрим 25 удалений, приводящих к перестановке 3 1 4 2.
1 = 1 СЗ)3 1 4 2 4Д31 5 2 4 1СЗ)5 2 4 1 5®2 4 1 5 2СЗ) т'= 2 ®4 1 5 2 3(5)1 4 2 4 2О15 3 4 2 5(1)3 4 2 5 3(1) т'=3 ®1 4 5 2 4(1)2 5 3 3 1(5)4 2 3 1 5042 3 1 5 2(4) у =4 031 5 4 2 4О15 2 3 3 1Д45 2 3 1 4Д52 4 1 5 ЗС2) ,у=5 ®1 5 2 4 4(1)5 3 2 3 1С4)2 э 4 1 5С2)З 3 1 4 2О5 Помеченный элемент всегда находится в 1-й позиции; для фиксированного 1 мы строили и + 1 различных удалений, по одному для каждого 1. Таким образом, для каждой перестановки Ьг Ьт... Ь„построено (и+ 1)т различных удалений. Так как возможны только (а+ 1)~п) удалений, мы должны найти их все. 3 Доказательство теоремы Н не только описывает результат удалений, но также помогает проанализировать среднее время удаления.
В упр. 12 показана, что при удалении случайного элемента из случайной таблицы шаг Р2 будет выполняться меньше чем в половине случаев, Теперь рассмотрим, как часто выполняется цикл на шаге РЗ. Предположим, что мы удаляем узел на уровне( и внешний узел, при симметричном обходе следующий непосредственно за ним, находится на уровне Ь. Например, при удалении узла САРК1СОйй на рис. 10 1 = 0 и я = 3, так квк узел Я находится на уровне 3.
Если й = 1+ 1, то на шаге Р1 Ю.1МК(Т) = Л; если й > 1+ 1, то на шаге РЗ мы выполним присвоение $ +- 551МК(й) ровно Й вЂ” 1 — 2 рвз. Среднее значение 1 равно (длина внутреннего пути)/Ю; среднее значение Ь— (длина внешнего пути — расстояние до крайнего слева внешнего узла)/Х. Расстояние до крайнего слева внешнего узла равно числу лево-правых минимумов вставляемой последовательности, так что среднее значение этой величины согласно анализу в разделе 1.2. 10 составляет Нл.
Поскольку длина внешнего пути превышает длину внутреннего пути на 2Х, среднее значение Ь вЂ” 1 — 2 равно -Нн/Х Добавляя к этому среднему значению число случаев, когда й -1-2 равно — 1, мы получим, что при случайном удалении в среднем операция 8 +- 111ИКЯ) на гпаге РЗ выполняется только (10) раз. Это успокаивает, так как в наихудшем случае, квк показано в упр. 11, удаления выполняются весьма медленно. Хотя теорема Н вполне строга н точна, в указанном виде ее нельзя применить к последовательности удалений, следующих за вставками. После удалений форма дерева остается случайной, однако относительное распределение значений в данной форме дерева может оказаться измененным, и это может привести к тому, что первая же вставка после удаления уипчпюжиш свойство случайности формы.
Этот поразительный факт, впервые обнаруженный Гарри Кноттом (Сагу Кпоы) в 1972 году, вам придется принять на веру (см, упр. 15), Еще более удивительны эмпирические данные, накопленные Дж. Л. Эппингером (1, 7. Ерр)пйег) (САСМ 26 (1983), 663-669, 27 (1984), 235), который обнаружил, что длина пути немного уменьшается при неболыпом количестве удалений и вставок, однако затем начинает увеличиваться до тех пор, пока не достигнет стабильного состояния после выполнения примерно пз операций удаления/вставки.
Это стабильное состояние хуже поведения случайного дерева при Л", большем примерно 150. Дальнейшее исследование 1(ульберсона (Сп!Ъегвоп) н Мунро (Мппго) (Сошр.,). 32 (1989), 68-75; А(Кот(йпшса 3 (1990), 295-311) привело к правдоподобному предположению о том, что среднее время поиска в стабильном состоянии асимптотически равно,/2Л'/9х. Однако Эппингер предложил простую модификацию, при которой алгоритм Р и его зеркальное отражение чередуются в одном алгоритме; он обнаружил, что это приводит к отличному стабильному состоянию, в котором длина пути сяижается до примерно 88% от его обычного значения для случайных деревьев. Теоретического пояснения этого факта пока не найдено. Как упоминалось ранее, алгоритм Р не проверяет случай Ы.1ЫК(1) = Л, хотя это один из простейших случаев удаления.
Мы можем добавить новый шаг Р1-' между шагами Р1 и Р2, Шьз. (Пуста ли ссылка Ы.1КК7) Если 1Д.1КК(7) = Л, установить Ц +- Ы.1ИК(Т) и перейти к шагу Р4. В упр. 14 показано, что алгоритм Р с этим дополнительным шагом всегда оставляет дерево с той же, если не меньшей, длиной пути, что и алгоритм Р; иногда же результат оказывается даже лучше ожидаемого. Прн комбинировании рассмотренного метода со стратегией симметричного удаления Эццингера длина пути при повторяющихся случайных удалениях/вставках уменьшается до примерно 86% от значения„получаемого прн использовании вставок без удалений. Частота обращений. Пока что мы предполагали, что каждый ключ может стать объектом поиска с одинаковой вероятностью.
Однако в более общем случае следует рассмотреть вероятности рь поиска и-го вставленного элемента (рг + ° + рл = 1). Модифицированное выражение (2) (в предположении о случайном порядке дерево остается случайным и выполняется соотношение (5)) показывает, что среднее коли- Рис 12. 31 наиболее употребятельнсе английское слово, вставленное в порядке уменьшения частоты. честно сравнений в случае успешного поиска составляет 1+~ "рь12Н,-2) =-г'~ раН, — 1, Например, если вероятности соответствуют закону Зипфа 16.1-(8)), среднее количество сравнений сводится к Нл — 1+ Ни /Н~д (г) (12) в предположении, что ключи будут вставляться в порядке уменьшения нх важности (см.
упр. 18). Эта величина примерно в два раза меньше величины, предсказываемой в результате анализа случая с равными частотами, н меньше, чем в случае бинарного поиска. На рис. 12 показано дерево, полученное в результате вставки 31 наиболее часто употребляющегося английского слова в порядке убывания частоты появления в текстах. Относительные частоты, приведенные для каждого слова, взяты из Н. Г.
Сешеа, Сгургала)ув1а 1Неи Уогк'. Вотег, 1966), 226, Среднее количество сравнений при успешном поиске в этом дереве равно 4.042; соответствующее значение для бинарного поиска с использованием алгоритма 6.2.1В или 6.2.1С требует 4.393 сравнений. Оптимальные бинарные деревья поиска. Рассмотренный материал заставляет задуматься о том, какое дерево является наилучшим для поиска в таблице ключей с заданными частотами. Например, для случая с 31 наиболее употребительным словом оптимальное дерево показано на рис, 13; оно трсбутт в среднем всего лишь 3.437 сравнений при успешном поиске. Рис. 13. Оптимальное дерево поиска для 31 наиболее употребителыюго английского слова.
Приступим к задаче поиска оптимального дерева. Например, при Ж = 3 в предпсаоженин, что ключи К~ < КЗ < Кз имеют вероятности р, д, г соответственно„ возможны пять деревьев: П1 1Ч Ъ 1 И (13) Сове Зр+Зд+г Зр-ьзд+г 2р+д+2г р+Зд+2г р+2д+Зг На рис. 14 показаны диапазоны значений р, д, г, для которых каждое из деревьев является оптимальным; сбалансированное дерево является наилучшим примерно в 45% случаев при случайном выборе р, д, г (см.
упр. 31). К сожалению, при больших К имеется ('~ )/(К+ 1) 4 'у(,уя ЮЗ~З) бинарных деревьев, так что перебрать их все и найти наилучшие — совершенно неразрешимая задача. Поэтому отбит познакомиться с ними поближе, чтобы, лучше узнав свойства бинарных деревьев, найти среди них оптимальные. До сих пор нас интересовал успешный поиск, однако на практике неудачный поиск не менее важен (более того, в некоторых специфичных задачах именно он является определяющим; случаями успешного поиска в таких задачах можно попросту пренебречь. — 11рим.
перев.). Например, представленные на рис. 13 слова соответствуют примерно 36% слов обычного английского текста; остальные 64%, естественно, повлияют на структуру оптимального дерева поиска. сформулируем задачу следующим образом. Даны 2п + 1 вероятностей рг,рэ, .. „р„и до, дм..., д„, где р; — вероятность того, что аргументом поиска является К;; д, — вероятность того, что аргумент поиска лежит между К~ и К;+1.
Рис. 1а. на этой диаграмме показано, какое из пяти деревьев (13) является наилучшим в случае относительных частот (р о„г) ключей (кп кт, кэ). тот факт, что р+ д+ г = 1, делает диаграмму двумерной несмотря на наличие трех координат, (Пусть яо представляет собой вероятность того, что аргумент поиска меньше, чем Км а о„— вероятность того, что аргумент поиска больше„чем К„.) Таким образом, р1 + рт + ' + ро + ае + В + ° + ая = 1 и мы хотим найти бинарное дерево, минимизирующее ожидаемое количество сравнений при поиске, а именно ~ р; (уровень(Я) + 1) + ~~~ ое уровень((Е), з=г ь=е где Я вЂ” у-й внутренний узел при симметричном обходе, а Б ) — (к+1)-й внешний узел; корень дерева находится на нулевом уровне.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
