Virt N. Algoritmy struktury dannyh = programmy (ru)(T)(410s) (522393), страница 43
Текст из файла (страница 43)
4.32) с указанием, что ее высота уве- 4.4. Древо«идам>е сгруагуры личплась. Мы должны различать трн возможные ситуации в зависимости от высоты поддеревьев перед включением: 1. Лг ~ Ью р(.Ьа1= +1, предыдущая несбал«нсированность в р уравновешивается. 2. Ьг = Ью р(.Ьа1 = О, вес склонился влево. 3.
)ц '-» йю р(.Ьа1= — 1, необходима балансировка. В третьем случае показатель сбалансированности корня левого поддерева (скажем, р1(.Ьа1) определяет, который из случаев (1 пли 2 на рис. 4.32) имеет место. Если левое поддерево этого узла тоже выше правого, то мы имеем дело со случаем 1, иначе — со случаем 2. (Убедитесь, что в этом случае левое поддерево корня не может иметь показатель сбалансированности, равный 0.) Необходимые операции балансировки погнюстью заключаются в обмене значениями ссылок.
Фактически ссылки обмениваются значениями по кругу, что приводит к однократному или двукратному «повороту» двух или трех узлов. Кроме «вращения» ссылок следует также измснпгь соотвегствующис показатели сбалансированности узлов. Подробно это показано в процедуре поиска, включения и балансировки (4.63). Принцип работы алгоритма показан на рис. 4.34. Рассмотрим бинарное дерево (а), которое состоит только нз двух узлов. Вклк>ченпе ключа 7 вначале дает несбалансированное дерево (т.
е. л>шейный список). Его балансировка требует однократного правого ()И) поворота, давая в результате идеально сбалансированное дерево (6). Последующее включение узлов 2 и 1 дает несбалансированное поддерево с корнем 4. Это поддерево балансируется однократным левым (ЕЕ) поворотом (г(). Далее включение ключа 3 сразу нарушает критерий соалансированности в корневом узле 6. Сбалансированность теперь восстанавливается с помощью более сложного двукратного поворота налево и направо (ЕЯ); результатом является дерево (е), Теперь при с,тедующем включении потерять сбалансированность может лишь узел 5.
Действительно, включение узла 6 должно привести к четвертому шщу балансировки, описанному в (4.63): двукратному' пово. роту направо н налево (И.). Окончательное дерево показано на рис, 4.34 (1). С эффективностью алгоритма включения в сбалансированное дерево связаны следующие два особо интересных вопроса: 1. Если все»! перестановок а ключей появляются с одинаковой вероятностью, то какова ожидаемая высота формируемого сбалансированного дерева? 2.
Какова вероятность, что включение приведет к балансировке? рсоссдаге веаесЬ(х: !иеееет; час р: сеЕ; час Ь: Ьвв)еал); еас р1,р2: геЕ'; 'Ь =- !а!ее) Ьерп И р =- пП 1Ьев ЬеЬ(в (слова нет в дереве; включить его) иеи(р); Ь;= ение; вЕй р', до ЬсаЕп Есеу:=- х; соил!:=.- 1; Ее!1:= — п11; пкйе:= в11; Ьа1:== О свд епд е1ве И х < р),йеу йев Ьерп всагсЬ(х, р';.ЕеГ(, ЛЕ; И Ь йсп (выросла левая ветвь) саве РЕ.Ьа! о1 1: Ьеа(п рс.ЬаЕ:= 0; Ь:= Ее!ее епд; О; Р",.ЬаЕ,'= — 1; -1: Ьерп (балансировка) р1;= Р!.!ей!; И р1),ЬаЕ -= — 1 йеп Ъерп (однократный 1Л;поворот) р!.ЕВ: =- р1!.пдЬЕ; Р1, УЕЯЬЕ:::= Р; р!.Ьа(:= О; р; — -- р1 евд е(ае Ьеп)п (двукратный уя-поворот) р2:= р1),еЕбЬЕЕ Р1!.пКЬЕ:= р2Е,Ее~41 р2 Е.Ее!1;= р1; р!.ЕеЕЕ:= Ф).щЬЕ; р2).пЬЬЕ: р; И р2Т.Ьа! =* — 1 йеп РЕ,ЬаЕ:= +1 е1ес р!.ЬаЕ: — — О; И Р2! ЬаЕ = +1 йеп РЕ),ЬаЕ .
-1 е(ве р( Е,ЬаЕ: О; Р:= Р2 евд; р).ЬаЕ:=- О; Ь:= уаЕке евд епд евд е(ае И х > р).Есеу йеп ьеа!п кеагсь(х, р !.геееь!, ь); И Ь 1Ьеп (выросла правая ветвь) саве Р,.ЬаЕ о1 -1: Ьеп(п р).ЬаЕ:= О; Ь:=- уаЬе епд; О: р).ЬаЕ:= +1; Ьеп(п (балансировка) р1;= р(,АРЬЕ! 4,4. Древовидные структуры И' р11.Ьа! = +1 гйеп Ьеййп (однократный ЯЯ-поворот) р~.ггуйг:= р1~~ЛеГ!; р1Т.!еХй:== р; р1.Ьа1:=- 0; р:= — р1 епй е)эе Ьеа)п (двукратный 3И:поворот) р2: =- р1 ).!еЛ) р1",:.!ей!:= р2!.пкЬ!; р2г.г!у!И:= р1; р~.пзбг ."= р21Л«уг; р2»ЛеХс:= р; 11 р2~.Ьа! = +1 Отеп р«.Ьа1:= — 1 е1эе р),Ьа1: —. 01 й р2;,,Ьа! = — 1 1Ьеп р17.Ьа1: +1 е)эе рЦ,Ьа! 1 0; р:= рг епй;.
р(.Ьа1:= 0; Ь:= Ла!ев епй епй епй е1ае Ьеа)п р(',соапг:= ре,соил! + 1; Ь;=,га!ве епй епй (ееагсЦ (4.63) й)атематическнй анализ этого сложного алгоритма пока не произведен, Эмпирические проверки оправдывают предположение, что ожидаемая высота сбалансированного дерева, которое строится в (4.63), равна Ь = !ой'(и)+ с, где с — малая константа (с ем 0,25). Это значит, что на практике АВЛ-сбалансированные деревья ведут себя так же, как идеально сбалансированные деревья, хотя с ними намного легче работать.
Эмпирически можно также предположить, что в среднем балансировка необходима приблизительно один раз на каждые два включения. При этом однократный и двукратный повороты одинаково вероятны, Пример на рис. 4.34 явно был тщательно подобран, чтобы показать как можно больше поворотов при минимальном числе включений. Из-за сложности операций балансировки считается, что сбалансированные деревья следует использовагь лишь в том случае, когда поиск информации происходит значительно чаше, чем включение.
Это, в частности, верно потому, что узлы таких деревьев поиска обычно для экономии памяти реализуются как плотно упакованные записи. «Скорость» изменения показателей сбалансированности, занимающих только по два разряда каждый, и обращения к ним часто является решающим фактором, определяющим эффективность 4. Динами«еское информияионные структуры 256 операции перебалансировкп, Эмпирические оценки говоряг, что сбалансированные деревья теряют большу~о часть своей привлекательности, если нужна плотная упаковка записи. (Ы (с) (е) (Е) Рвс. 4.34.
Включение в сбадавсвроввввое дерево. В самом деле, трудно превзойти простой и очевидный алгоритм включения в дерево! 4А.В, Удаление нз сбалансированного дерева Учитывая наш опыт с удалением из дерева, мы можем предположить, что в случае сбалансированных деревьев удаление будет еще более сложным, чем включение. Это верно, хотя операция балансировки остается в основном такой же, чта и прн включении. В частности, балансировка состоит из однократного или двукратного поворота узлов. Удаление из сбалансированного дерева основано на алгоритме (4.52). Простыми случаями являются удаление терминальных узлов н узлов с одним потомком.
Если же узел, который нужно удалить, имеет два поддерева, мы вновь будем заменять его самым правым узлом левого поддерева. Как и и случае включения (4.63), добавляется булевский параметр-переменная Ь, означающий, что «высота поддерева уменьшилась». Вопрос о перебалансировке рассматривается только при й = (гие. Значение (тпе присваивается )) прп нахождении и удалении узла или если сама балансировка уменьшает высоту поддерева, В про~рампе (4.64) мы вводим две ВМ, древовидные сгрркгнры 257 )спммезричные) операции балансировки в виде процедур„ так как в алгоритме удаления к ннм обращаются несколько раз.
Отметим, что да)апсе 7 используется, когда уменьшается высота лсвого, а Ьагапсв2 — правого поддерева. [а) рй (а) йп Рнс. 4.3В. Удаления на сбалаиснрснанноги дерева, Работа нашей процедуры иллюстрируется на рис, 4,3б. Если задано сбалансированное дерево га), то последовательное удаление узлов с клю)амн 4, 8, 6, б, 2, ! и 7 дает деревья гЫ,..., ())). Удаление ключа 4 само по себе просто, так как он грелстандяЕт СОбОй зсрМШШЛЬНЫй унсд, ОдиаКО Прн ЭТОМ ПОяа ляется несбалансированность н )зле 3, Его балансировка тре- 258 4, Диназиииесние инфориоционные структуры бует однократного поворота налево. Балансировка вновь становится неооходпмой после удаления узла б. На этот раз правое поддерево корня балансируется однократным поворотом направо.
Удаление узла 2, хотя само по себе просто, так как он имеет только одного потомка, вызывает сложный дав кратный поворот направо и налево. И четвертый случаи: двукратный поворот налево и направо вь|зывается удалением узла 7, который прежде заменяется самым правым элементом левого поддерева, т. е. узлом с ключом 3. ргоссйвге с!с!его(х: и!егер; тат р: гсг"; тат-!и Ьоо!вап); тат д: ге!'; Я .—.- /а!гс) ргосейнге Ьа!алое!(тат р: гсс"; таг Л: Ьоо!сан); тат р1,р2: гК Ы„Ь2: -1 ..
+1; Ъеа1а (й- Геис, левал ветвь стала короче! сазе р',.Ьа! о1 -1: р,.Ьа1:=- О; 0: Ъеа!и р!.Ьп1:=- -Ь11 Ь; Я~!зе епй; 1; Ъеа1п !балансировка! р1:= р";,.г!ййг! Ь1:= р11,Ьв!! рйЫ > 0 гйеп Ъер1п 1однолратный Рсес-поворот) р...щ!Н:= р1~.!еуу1р1 1,!е1Г:= р; 1ЕЫ =01йеп Ъеа1п р1,Ьа1:= +1; р1;.Ьа1 '.= -1; й;=,!а!гв епй е1зе Ъей1п р,.Ьв1:= 0; р1;.Ьа!:= О епй; р:== р1 епй е1зе Ъей1п ! двулрвтньай Я1;поворот'! р2:= р1!.!е|1; Ь2:= р2;.Ьа1; р1 „!е!г:= рй,,пгЫ; рй!.пе!и: =- р1; р',.пе!и:= рй".!е!Г; р2",.!ф: р; 11 Ьй =- +1 тЪеп р'пЬа1:= -1 е)зе р;,Ьв! 1= О; 11 Ь2 = -1 гйеп р1;.Ьв1: — , '1 е1зе рЦ'.Ьа1:= 0; р;= р2; р2;,Ьа1:= О епй епй еай епй 1Ьв!апре 1) ! укоеейпке Ьа1апсе27как р: те7) как Ь: Ьоо1еап); как р1,р2: те«; Ы,Ь2: -1.. +1; Ъеа!п (Ь.-кь'ьье, правая ветвь с«пала короче) сапе р "1.Ьа1 оГ 1: рТ,Ьа1:= О," О: Ъеа1п рЬ,Ьа1: —.— — 1; 1ь:=,1айе епй,' -1: Ъерп 1балансировка) р1 ".= р";.1«7«; Ы:=- р1'.Ьа7; ЫЫ~ ОкЪеп Ъеаьп Аоднокрапьнььй 22;повороьп) р7.7«71 ь= р1 "ь.тьк1ьт; р1,,«1кЬь:= р; ИЫ = ОкЪ Ъерп рь'.Ьа7:= -1; р1ь.Ьа1:= +1; Ь:= 1аЬе епй е1ае Ъеа1п р",,Ьа1 .'= О; р1 ь.Ьа1:= О епй " р:= р1 епй е1ае Ъеа1п 7двукратньььй 1Я-поворот) р2:== р1ь.ььк7ь«1 И:=.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
