.bal = О, вес склонился влево.

q Hl P\-bal - -1, необходима балансировка.

п третьем случае показатель сбалансированности корня ле--го поддерева (скажем, р1 \.bal) определяет, который из ,дучаев (1 или 2 на рис. 4.32) имеет место. Если левое под- ерево этого узла тоже выше правого, то мы имеем дело со дучаем 1, иначе - со случаем 2. (Убедитесь, что в этом слу-1,2е левое поддерево корня не может иметь показатель сбалансированности, равный 0.) Необходимые операции балан-jiipoBKH полностью заключаются в обмене значениями ссылок. Фактически ссылки обмениваются значениями по кругу, iro приводит к однократному или двукратному повороту двух или трех узлов. Кроме вращения ссылок следует также изменить соответствующие показатели сбалансированности узлов. Подробно это показано в процедуре поиска, включения и балансировки (4.63).

Принцип работы алгоритма показан на рис. 4.34. Рассмотрим бинарное дерево (а), которое состоит только из двух узлов. Включение ключа 7 вначале дает несбалансированное дерево (т. е. линейный список). Его балансировка требует однократного правого {RR) поворота, давая в результате идеально сбалансированное дерево (Ь). Последующее вклю-етие узлов 2 и 1 дает несбалансированное поддерево с корнем 4. Это поддерево .балансируется однократным левым \Щ поворотом (d). Далее включение ключа 3 сразу нарушает критерий сбалансированности в корневом узле 5. Сба-чансированность теперь восстанавливается с помощью более гаожного двукратного поворота налево и направо (LR); результатом является дерево (е). Теперь при следующем включении потерять сбалансированность может лишь узел 5. Действительно, включение узла 6 должно привести к четвертому иду балансировки, описанному в (4.63): двукратному повороту направо и налево {RL). Окончательное дерево показано 3 рис. 4.34 (f). С эффективностью алгоритма включения сбалансированное дерево связаны следующие два особо iifiepecHbix вопроса:

Если все п\ перестановок п ключей появляются с одинаковой вероятностью, то какова ожидаемая высота форми-, Руемого сбалансированного дерева?

Какова вероятность, что включение приведет к балансировке?

jjjiacb. Мы ДОЛЖНЫ различать три возможные ситуации J* дрисимости от высоты поддеревьев перед включением:

,fii<hK, p.bal =предыдущая несбалансированность уравновешивается.

procedate search(x: integer, var p: ref; var h: boolean);

vat p\,p2; ref; [h = false] begin

if p = nil then

begin [слова нет в дереве; включить его] new(p); h ;= true; with /?t do

begin fcej ;= count := 1;

/e/i ;= ml; right := nil; 6a/ := 0

end end else

if X < pl.key then begin search(x, p].left. A);

if h then [выросла левая ветвь]

case p\.bal of

ГТ begin p].bal := 0; h := /o/je

end ; .

0: ;.Г-*й/:= -1; I

-1: begin [балансировка] p\ p\.left; ,

if ;?1.6й/ = -1 then begin [однократный LL-noeopom] p\.left := p\\.right; p\\.right := p; p\.bal:- 0; p :~ pi end else

begin [двукратный LR-noeopom] p2 := рЦ.right; plt.right := p2bleft; p2].left := 1; p\.left := p2\.right; p2\.right ;?; if ;52.&й/ = -1 then pi.bal +1 еЫр\.1чг10; if ;72.6а/ = +1 then pi\.bal := -1 else pl\Ml ; ( ;

end ;

end end else

if x > p].key then

begin searchix, p].right, h);

if h then [выросла правая ветвь]

ca?e of -1: begm pMl := 0; Л :== false end ;

0: p].bal\=== +1;

1: begin [балансировка] pi :-p].right;

begin p].count := p].count + 1; h \= false end

i. [search]

(4.63)

Математический анализ этого сложного алгоритма пока не гро1зведен. Эмпирические проверки оправдывают предположение, что ожидаемая высота сбалансированного дерева, ко-юрье строится в (4.63), равна h = log(n)с, где с - малая Штанта (с 0,25). Это значит, что на практике АВЛ-сба-гашированные деревья ведут себя так же, как идеально сба-мнсированные деревья, хотя с ними намного легче работать. Эмпирически можно также предположить, что в среднем балансировка необходима приблизительно один раз на каждые №а включения. При этом однократный и двукратный повороты одинаково вероятны. Пример на рис. 4.34 явно был тщательно подобран, чтобы показать как можно больше поворотов при минимальном числе включений.

Из-за сложности операций балансировки считается, что балансированные деревья следует использовать лишь в том %чае, когда поиск информации происходит значительно Ще, чем включение. Это, в частности, верно потому, что Чы таких деревьев поиска обычно для экономии памяти Р^лизуются как плотно упакованные записи. Скорость З^нения показателей сбалансированности, занимающих *1ько по два разряда каждый, и обращения к ним часто яв-jCH решающим фактором, определяющим эффективность

if рЦ.Ъа! = +1 then

begin [однократный RR-поворот]

Pbright := plbleft; p\\.left := p,

p\.bal := 0; p := pi end else

begin [двукратный RL-noeopom] p2 := pi].left\

J pl\.Wt := p2\.right; p2].right := pV,

Pbright p2[;left; p2\.]eft :=

if p2\.bal = +1 then pbal : -1 else = Oj

; if /)2.Ы = -1 then pl].bal +1 else рЦ.Ьа1 J- С

p :=p2

Iend ; Pt.6fl/:=i 0; h:= false end end