Virt N. Algoritmy struktury dannyh = programmy (ru)(T)(410s) (522393), страница 42
Текст из файла (страница 42)
4,29 мы разлеляем узлы на три класса: 1. ! — 1 узлов в левом поддереве имеют среднюю длину пути а: ~ + 1. 2. Корень имеет длину пути, равную 1. 3. л — ! узлов в правом поддереве имеют среди!ою длину пути а,;+ 1. Следовательно, (4.53) можно представить в виде суммы трех слагаемых: ан' = (а~, + 1) — '+! ° — + (а„, + 1) — "' .
(4 54) Искомая величина а„теперь получается как среднее а„' для всех ! = 1, ..., и, т. е. для всех деревьев с ключами 1,2, ...лая корне: а„= — „~~) ~(а;, +1) — + — +(а„, +1) " ! ! н =1+ — „, ~~ ((! — !)а;,+(и — !)а„Д= (4,55) 1 ! и н-л 2 = 1+ — „, ~~~ (! — 1)ас-л =1+-т ~ ! ° а,. 2 л ! л ! Уравнение (4.55) представляет собой реккурентное соотношение для а, вила а,= !л(аь ам ..., а, л), Отсюда мы можем получить более простое реккурентное соотношение вида а„= !т(ан 1) следующим образом; Из (4.55) непосредственно получаем и-т (1) а„=1+ — „, ) ! а! — — 1+ — „, (а — 1)а„, + —,~ 1 ао 2 . 2 2 $ 1 с-! л-т 2 (2) а„,=1+ „, ез ! ам т ! 4.4.
Яре»о»сед»ьге структуры з47 Умножив (2) на (и — 1/и)2, мы получим »-2 (3) †, ~ ! а, = , (д„ , — 1) и, подставив (3) в (1), получим д ((иг 1)а + йи 1) »»г (4.56) Оказывается, что а, можно представить в нерекурсивиой, за- крытой форме с помощью гармонической функции О» 1+ я+ з+'' +»' 1 1 1 а»=2» »+1 (4.57) мы получаем для больших и соотношение а„м 2 (1п (и) + у) — 3 = 21п (и) — с. Поскольку средняя длина пути в идеально сбалансированном дереве приблизительно равна а'„ = 1од (и) — 1, (4,58) опуская постоянное слагаемое, которое становится незначительным для больших и, мы получаем 1пп —," = —" = 2 1п 2 = 1. 386. в 10К» (4.59) Что дает нам результат этого анализа (4.59)? Иэ него мы можем сделать вывод, что, стараясь всегда строить идеально сбалансированное дерево вместо «случайного» дерева, получаемого программой 4.4, мы могли бы, по-прежнему предполагая, что все ключи появляются с равной вероятностью, ожидать среднего выигрыша в клине пути поиска не более 39%.
Ударение следует сделать на слове «среднего»„ поскольку, разумеется, выигрыш может быть намного больше в неудачном случае, когда формируемое дерево полностью вырождается в список, но вероятность этого случая невелика (если все перестановки и ключей равновероятны). В связи '(Недоверчивый читатель может проверить, что (4.57) удовлетворяет рекурсивному соотношению (4.56).) Из формулы Эйлера (используя константу 7»н 0,577) ~г» 2+1п(и)+ ш»г + ''* 1 4. еЧииаиииеекие иифорыияиоикые геруктуры 24В с этим следует отметитьь что ожидаемая средняя длина пути в «случайном» дереве растет тоже строго логарнфмически по отношению к числу его узлов, несмотря на то что в худ. шем случае длина пути увеличивается в линейной зази. снмости.
Цифра 39 ф, накладывает ограничения на объем дополнительных затрат, которые имеет смысл вкладывать в какую- либо доперестройку структуры дерева прн включении элементов. Разумеется, отношение г между частотой обращений (понска) к узлам (информации) в частотой включений существенно влияет на границу, до достижения которой эти затраты выгодны. Чем больше этот коэффициент, тем больше выигрыш от такой процедуры перестройки.. Цифра 39 $ достаточно низка, и в большинстве случаев выигрыш от такой процедуры по сравнению с простым алгоритмом нключення в дерево не оправдывает затрат, если только число узлов н соотношение между поиском и включением не оказываются велики (илн если можно не опасаться худшего случая), 4.4.б. Сбаланснраванныа деревья Из предыдущих рассуждений ясно, что процедура включения, восстанавливающая идеальную сбалансированность структуры дерева, вряд ли будет выгодна, поскольку такое восстановление после случайного включения — довольно сложная операция.
11о ее можно упростить, если дать менее строгое определение «сбалансированности». Такой несовершеиныи критерий сбалансированности может потребовать более про стой перестройки дерева при небольшом уменьшении среднего быстродействия поиска, Одно такое определение сбалансированности было дано Адельсаном-Вельским и Ландисом 1ч.1]. Крите(иий сбалансированности следующий: Дерево является сбалангпроаанньт тогда и то,иько тогда, когда для каждого узла высота его двух поддеревьев различается не более чем на !. Деревья, удовлетворяющие этому условию, часто называют АВЛ-деревьямн (по фамилиям их изобретателей).
Мы будем называть их просто сбалансироааннымн деревья,ки, так как их критерий сбалансированности оказывается наиболее подходящим. (Отметим, что все идеально сбалансированные деревья являются также АБЛ-сбалансированными,) Это определение не только простое, но такнсе приводит к легко выполнимой балансировке, а средняя длина поиска остается практически такой же, как у идеально сбалансированного дерева, 4.4. Древовидные структуры Со сбалансированнымн деревьями можно выполнять следующие операции за 0(1одм) единицу времени даже в худшем случае: 1.
!1айти узел с данным клю шм. 2.' Включить узел с данным клктчом. 3. Удалить узел с данным ключом. Это является прямым следствием теоремы, доказанной Лдельсоном-Вельским и Ландисом, которая утверждает, что свалансиРованнос ДеРево никогДа не бУДет более чем на 45 втв выше соответствующего идеально сбалансированного дерева независимо от количестна узлов. Если мы обозначим высоту сбалансированного дерева с м узлами через йь(м), то !оп (и + 1) ( Ьь (и) ( 1.4404 ° 1оп (и + 2) — 0.328 (4.60) Разумеется, оптимум достигается, если дерево идеально сбалансировано, при а = 2' — 1. Но какова структура наихудпгбго АВЛ-сбалансированного дерева? "Чтобы найти'максимальную высоту й всех сбалансированных деревьев с и узлами, возьмем фиксированное й и попробуем построить сбалансированное дерево с минимальным количеством узлов.
Такая стратегия рекомендуется, поскольку, как и в случае минимального й, это значение может быть достигнуто только при некоторых, определенных значениях л. 72 Рвс, 4.30. Деревья Фвбове |чя высотой 2, 3 я 4, Обозначим такое дерево с высотой й черсз Т„. Очевидно, что То — пустое дерево, а Т| — дерево с одним узлом. Чтобы построить дерево Ть для й ) 1, мы зададим корень с двумя поддеревьями, которые также имеют минима,тьное число узлов. Следовательно, поддеревья также являются Т-деревьями.
Очевидно, что одно поддерево обязано иметь высоту Й вЂ” 1, а другому позволено иметь высоту на единицу меньше, т. е. й — 2, г(а рнс. 4,30 показаны деревья высотой 2, 3 и 4. Поскольку принцип их организации напоминает принцип построения чисел Фибопаччи, подобные деревья называются деревьями Фабоначни, Они определяются следующим образом: 1.
Пустое дерево есть дерево Фябоначчи с высотой О. 4. Динами«еение ин4ормаяионные егррнгары 2. Один узел есгь дерево Фибоначчи с высотой 1. 3. Если Те 1 и Ти, — деревья Фибоначчи с высотой Ь вЂ” 1 и й — 2, то Т» = (Те „ х, Т, еУ есть дерево Фибоначчи с высотой Ь. 4. Никакие другие деревья не являются деревьями Фибоначчн. Число узлов в Тн определяется простым рекуррентным соотношением: »(о —— 0, йг,=1, и' л = й(в-1 + 1 + йГн-е (4.61) )не — это количества узлов, для которых можно получить наи.
худший случай (верхнюю границу 6) из (4.60). 4.4.7. Включение а сбалансированное дерево Посмотрим, что может произойтн, когда в сбалансирован. ное дерево включается новый узел, Пусть дан корень г с левым и правым поддеревьями Т. и (г, Предположим, что в Ь Рие 4.ЗК Сбелеиснровеиное дерево, включается новый узел, вызывая увеличение его высоты на 1. Возможны трн случая: 1. йе = йн. 1. и !с' становятся неравной высоты, но критерий сбалансированности не нарушается.
2. й, "' й„: !. и !с приобретают равную высоту, т. е, сбалансированность даже улучшается. 3. 6, ) 6н. критерий сбалансированности нарушается, н дерево нужно перестраивать. Рассмотрим дерево на рис. 4.31, Узлы с ключами 9 и 1! можно вставить без балансировки; дерево с корнем 10 становится односторонним (случай 1), а с корнем 8 улзчшает свою сбалансированность (случай 2). Однако включение узлов 1, 3, 5 или 7 требует последующей балансировки. При внимательном изучении этой ситуации можно обнаружить, что имеются лишь две существенно различные возмож« 2б1 4.4. Дуввовидкмв структдрм ности, требующие индивидуального подхода. Оставшиеся могут быть получены симметричными преобразованиями этих двух. Случай ! определяется включением ключа 1 или 3 в дерево на рис. 4.31, случай 2 — включением узла б или 7. Рис.
4.32. 11ссбалаисированность, воаиикаюшаи кри вклюисиин. Эти дна случая в общем виде показаны на рнс. 4.32, где поддеревья обозначены прямоугольниками, а увеличение высоты при включении указано перечеркнутыми квадратами, Простые преобразования этих двух структур восстанавливают Сл Рис. 4.ЗЗ. Восстаиовлснис баланса. нужную сбалансированность. Их результат приведен на рис. 4,33; отметим, что допускаются перемещения лишь в вертикальном направлении, в то время как относительное горизонтальное расположение показанных узлов и поддеревьев должно оставаться без изменений. Ллгоритм включения и балансировки полностью определяется способом хранения информации о сбалансированности дерева.
Крайнее решение состоит в хранении этой информа- 252 4. динами«есние инсрормационные структуры ции полностью неявно в самой структуре дерева. По в этом случае показатель сбалансированности узла должен заново вычисляться каждый раз, когда узел затрагивается включением, что приводит к чрезвычайно высоким затратам. Другая крайность — явно хранить показатель сбалансированности в информации, связанной с каждым узлом, Тогда определение (4.48) типа узла расширяется до (уре лоде = тесвгй йеу: глтевег,' соаМ: )л~вяег; 1еГ( т)ййг: гет) Ьай — 1., +1 епв (4.62) В дальнейшем мы будем интерпретировать показатель сбалансированности узла как высоту его правого поддерева минье высота его левого поддерева и будем строить алгоритм, исходя из узлов описанного в (4.б2) типа.
В общих чертах процесс включения узла состоит из последовательности таких трех этапов: 1. Следовать по пути поиска, пока не окажется, что ключа нет в дереве. 2. Включить новый узел и определить новый показатель сбалансированности. 3. Пройти обратно по пути поиска и проверить показатель сбалансированности у каждого узла. Хотя этот метод требует некоторой избыточной проверки (сели сбалансированность устансвлена, то для предков соответствующего узла ее проверять уже не надо), мы будем вначале придерживаться этой, очевидно, корректной схемы, так как ее можно реализовать с помощью простого расширения уже разработанной процедуры поиска с включением из программы 4.4.
Эта процедура описывает операцию поиска для каждого отдельного узла, и благодаря рекурсивной формулировке се можно дополнить операцией, выполняемой «по дороге назад вдоль пути поиска». На каждом шаге должна передаваться информация о том, увеличилась ли высота поддерева (в которое произведено включение). Поэтому мы добавим к списку параметров процедуры булевскую переменную А, означаюшую «высога поддерева увеличилась». Очевидно, по а должна быть гираметром-переменной, поскольку используется для передачи результата, Теперь предположим, что алгоритм возвращается к узлу с левой ветви (см. рис.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
