операции перебалансировки. Эмпирические оценки

что сбалансированные деревья теряют большую часть cr привлекательности, если нужна плотная упаковка ащ

id) (е) (f)

Рис. 4.34. Включение в сбалансированное дерево.

В самом деле, трудно превзойти простой и очевидный алгоритм включения в дерево!

4.4.8. Удаление из сбалансированного дерева

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

Удаление из сбалансированного дерева основано на алгоритме (4.52). Простыми случаями являются удаление терминальных узлов и узлов с одним потомком. Если же узел, который нужно удалить, имеет два поддерева, мы вновь будем заменять его самым правым узлом левого поддерева. Ка и в случае включения (4.63), добавляется булевский параметр-переменная h, означающий, что высота поддере^ уменьшилась . Вопрос о перебалансировке рассматривается только при h = true. Значение true присваивается h~ при нй хождении и удалении узла или если сама балансировка уменьшает высоту поддерева. В программе (4.64) мы вводим

йММетричные) операции балансировки в виде процедур, к как в алгоритме удаления к ним обращаются несколько яз Отметим, что balance 1 используется, когда уменьщается PjcoTa левого, а balance 2 - правого поддерева.

Рис. 4.35. Удаления из сбалансированного дерева.

Работа нашей процедуры иллюстрируется на рис. 4.35. Если задано сбалансированное дерево (а), то последовательное удаление узлов с ключами 4, 8, 6, 5, 2, 1 и 7 дает деревья (Ь),..., (h).

Удаление ключа 4 само по себе просто, так как он пред- тавляет собой терминальный узел. Однако при этом появ-Йется несбалансированность в узле 3. Его балансировка тре-

procedure delete(x: mieger; таг р: ref; var h. booJecm); vat g: ref; {h = false}

procedure (var p: ref var h: boekai);

var p\,p2: ref; b\,b2: -1 . +1; begin [h-true, левая ветвь стала короче)

case pl.baloi -1: pX.bal := 0; 0: begm p\.bal := +1; Л := false end ;

I: begin [балансировка] p\ := p].right; Ы := pl\M; if Й1 > 0 then

begin [однократныйRR-noeopom] P\.right := p\].left; p\].left : p; if 61 = 0 then

begin pf.bal := +1; pl\.bal := -1; h := false end else

begin pl.bal 0; рЦ.Ъа! 0 end ; p:=-pl end else

begin [двукратный RL-noeopom]

p2 pltleft; b2 := p2\.bal;

plbleft : p2].right; p2\.right : pi;

p\.rlght := p2]Jeft; p2].left p;

if И = +1 then pMl := -1 else p]M 0;

if Ъ2 -1 then рЦ.Ьа1 := +1 else рЦ.Ъа1 := OJ

p p2; p2\.bal ;= 0 end

end [balance 1};

бует однократного поворота налево. Балансировка вновь новится необходимой после удаления узла 6. На этот правое поддерево корня балансируется однократным пово том направо. Удаление узла 2, хотя само по себе просто как он имеет только одного потомка, вызывает сложный'J кратный поворот направо и налево. И четвертый случай: л?! кратный поворот налево и направо вызывается удалени^ узла 7, который прежде заменяется самым правым элемент^ левого поддерева, т. е. узлом с ключом 3.