Àëãîðèòì
Ðàññìîòðèì àëãîðèòì âñòàâêè óçëà â áèíàðíîå äåðåâî.
Âñòàâèì óçåë ñ íîìåðîì 150, òîãäà îí ñòàíåò ïðàâûì ñûíîì óçëà ñ íîìåðîì 120, ò.ê. îí ÿâëÿåòñÿ áîëüøèì ïî çíà÷åíèþ óçëà ñ íîìåðîì 120, íî ìåíüøå çíà÷åíèÿ óçëà ãîëîâû äåðåâà.
P - ðàáî÷èé óêàçàòåëü
Q - óêàçàòåëü îòñòàþùèé îò Ð íà îäèí øàã
V - óêàçàòåëü íà ýëåìåíò, êîòîðûé áóäåò âñòàâëåí â áèíàðíîå äåðåâî .
Èëëþñòðàöèÿ ïðîöåññà âñòàâêè óçëà 150, â ñîîòâåòñòâèè ñ âûøåïðèâåäåííûì àëãîðèòìîì (êðàñíûì öâåòîì âûäåëåíû íîâûå ñâÿçè â äåðåâå).
Êîíå÷íûé âàðèàíò äåðåâà ïîñëå âñòàâêè :
Ïðîãðàììà
Ïñåâäîêîä Ïàñêàëü
Q=nil Q=nil
P=Tree P=Tree
While (P<>nil) do While (P<>nil) do
Q=P Begin
If key=k(P) then Q=P;
search=P If key=P^.k then
return Begin
EndIf search:=P;
If key<k(P) then exit;
P=left(P) End;
else If key<P^.k then
P=right(P) P:=P^.left;
EndIf else
EndWhile P:=P^.right;
V=maketree(key,rec) End;
If key<k(Q) then V=maketree(key,rec)
else If key<Q^.k then
Right(Q)=V Q^.left:=V
EndIf else
search=V Q^.right:=V;
Return search:=V
