Текст процедуры insert_&_balanse.

ТЕКСТ ПРОЦЕДУРЫ Insert_&_Balanse.

Процедура выполняет действия по вставка элемента в бинарное дерево с последующей балансировкой в соответствии с приведенным выше алгоритмом.

{=====Программный пример 6.18=========} Procedure Insert_&_Balanse (x:integer; var p,root:ref; var h:boolean); { x=KEY, p=p, root=ROOT, h=h } var p1,p2:ref; {h=false} Begin if p=nil then Create(x,p,h) {слова нет в дереве,включить его} else if x=p^.key then begin gotoXY(35,3); write('Ключ найден!'); readln; exit; end; if x < p^.key then begin Insert_&_Balanse(x,p^.left,root,h); if h then {выросла левая ветвь} case p^.bal of 1: begin p^.bal:=0; h:=false; end; 0: p^.bal:=-1; -1: begin {балансировка} if p=root then root:=p^.left; p1:=p^.left; {смена указателя на вершину} if p1^.bal=-1 then begin {однократный LL-поворот} p^.left:=p1^.right; p1^.right:=p; p^.bal:=0; p:=p1; end else begin {2-кратный LR-поворот} if p1=root then root:=p1^.right; p2:=p1^.right; p1^.right:=p2^.left; p2^.left:=p1; p^.left:=p2^.right; p2^.right:=p; if p2^.bal=-1 then p^.bal:=+1 else p^.bal:=0; if p2^.bal=+1 then p1^.bal:=-1 else p1^.bal:=0; p:=p2; end; p^.bal:=0; h:=false; end; end;{case} end { h then} else if x > p^.key then begin Insert_&_Balanse(x,p^.right,root,h); if h then {выросла правая ветвь} case p^.bal of -1: begin p^.bal:=0; h:=false; end; 0: p^.bal:=+1; 1: begin {балансировка} if p=root then root:=p^.right; p1:=p^.right; {смена указателя на вершину} if p1^.BAL=+1 then begin {однократный RR-поворот} p^.right:=p1^.left; p1^.left:=p; p^.BAL:=0; p:=p1; end else begin {2-кратный RL-поворот} if p1=root then root:=p1^.left; p2:=p1^.left; p1^.left:=p2^.right; p2^.right:=p1; p^.right:=p2^.left; p2^.left:=p; if p2^.BAL=+1 then p^.BAL:=-1 else p^.BAL:=0; if p2^.BAL=-1 then p1^.BAL:=+1 else p1^.BAL:=0; p:=p2; end; p^.BAL:=0; h:=false; end; { begin 3 } end;{ case } end; {then } End {Search};