Ñòðóêòóðû è àëãîðèòìû îáðàáîòêè äàííûõ

       

Àëãîðèòì


 

Ðàññìîòðèì àëãîðèòì âñòàâêè óçëà â áèíàðíîå äåðåâî.

Âñòàâèì óçåë ñ íîìåðîì 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



Ñîäåðæàíèå ðàçäåëà