ebalmce2(\at p: ref; var h: boolean); wphp2- ref; bl,b2: -1.. +1; gin {ft-true, правая ветвь стала короче} case pbbalot . i: p\.bal 0; q: begin i?t.fc -1; й false end ;

l: begin {балансировка} pi := j?,fe ; й1 := /)1.йй/;

----if Я < О then

begin Ходнократный LL-поворот] p\.left := plbright; pl\.right := j?; if Я ==0 then

begin pX.bdl ;= -I; pl\.bal := +1; h false end else

begin p]-.bal :=? 0; j>lt.&fl/ 0 end ; P pi end else

begin {двукратный LR-noeopom] p2 :== pl].right; Ь2 := /)2.йй?; pl\.nght гт./е/г?; il-l-./e/? := i7t.fc/!f :== p2[.right; p2\.rigJit := if J2 -1 then it-fi +1 elsept- 0; if Ъ2 = +1 then j>lt.6fl/ := -1 еЫр1\.ЪаИ-= 0; P i?2.M := 0

end {balance2} ;

procedure JeZ(Yar r; ref; var h: boolean); begin [h ~ /flZs-e}

if r].right Ф nil then

begin del(r\.right,h); if /г then balcmce2(r,h) end else

begin gt-J r].key; q\.CQUnt := i*.C0M fj r r\.left; h := true

end end ;

begin {delete}

Iif = nil then begin writeln (-KEY iS NOT Ш TBEEJi. A / /0 end else

(4.64)

if л: < pJcey then

begiadeleteiXypl.leftJiy, if h thmbahnce\{p,h)

end else if X > pi-key then

begin delete{x,p\.right,hy, if h tlien balance2{p,h)

end else

Ъефл [удалениеp) Q:-p\ if gbright = nil then

begin p :- q.left; h := true

end else if q]Jeft = nil then

begin p := q\.right, h := true -

end else begfn deT(qfJeft,7iJ;

if Й then5fl/a cel(p,) end ;

[disposeiq)}

end {delete}

Очевидно, что удаление элемента в сбалансированном дереве может также быть выполнено за (в худшем случае) О (log/г) шагов. Тем не менее не следует упускать из виду существенную разницу в выполнении процедур включения и удаления. В то время как включение одного ключа может вызвать самое большее один поворот (двух или трех узлов), удаление может потребовать поворота в каждом узле вдоль пути поиска. Рассмотрим, например, удаление самого правого узла в дереве Фибоначчи. Удаление любого узла в дереве Фибоначчи вызывает уменьшение его высоты, а удаление самого правого узла требует максимального числа поворотов. Таким образом, мы получили самое неудачное сочетание: наихудший выбор узла в наиболее плохом варианте сбалансированного дерева! Но насколько вообще вероятны повороты? Удивительный результат эмпирических проверок показал, что в то время как один поворот вызывается приблизительно каждыми двумя включениями, тем не менее при удалений мы имеем дело с одним поворотом на целых пять удалений. Поэтому удаление из сбалансированного дерева примерно так же просто - или так же трудно, - как и включение.

4.4.9. Оптимальные деревья поиска

До сих пор в наших рассуждениях об организации Pfi ревьев поиска мы исходили из предположения, что частота обращения ко всем узлам одинакова, т. е. что все ключИ

равной вероятностью становятся аргументами поиска. По- дймому, это - наилучшее допущение, если нет сведений распределении частоты обращений. Но существуют случаи /скор исключение, чем правило), когда имеется информа-* J, о вероятности обращений к отдельным ключам. Для ij(0X случаев обычно характерно, что ключи остаются по-.оянными, т. е. дерево поиска не подвергается ни включе-д„ям, ни удалениям, а сохраняет постоянную структуру. Тн-примером служит сканер транслятора, который для jjajKfloro слова (идентификатора) определяет, является ли оно

(Ь) (с) <dl (е)

Рис. 4.36. Деревья поиска с тремя узлами.

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

Предположим, что pi - вероятность обращения к узлу i в дереве поиска:

Pr{x = ki} = pi, Ypi

(4.65)

Теперь мы хотим организовать дерево поиска так, чтобы общее число iiiatou п5иска, подсчитанное для достаточно большого количества опытов, было мийимальным. Для этого припишем каждому узлу в определении длины пути (4.34) некоторый вес. Узлы, к которым часто обращаются, считаются Тяжелыми, а посещаемые редко - легкими. Тогда взвешенная лина пути есть с^мма всех путей от корня к каждому узлу, Умноженных на вероятность обращения к этому узлу:

(4.66)

уровень узла I (или его расстояние от корня +1). Наша лъ~ минимизировать взвеиленную длину пути для данного

гПределения вероятностей.