În cazul reprezentării unui arbore binar sub formă de noduri care conține un câmp de informații și două câmpuri de comunicare, numărul de câmpuri de comunicare având valorile zero. este întotdeauna mai mare decât numărul de linkuri care indică nodurile existente. Prin urmare, de multe ori această metodă de stocare a arborilor se dovedește a fi ineficientă în ceea ce privește utilizarea memoriei, mai ales dacă dimensiunea câmpului de informație este comparabilă cu dimensiunea indicelui.
Fig. 6.1 - Cusătură simetrică pe arborele binar drept
Deoarece trebuie să distingi cumva conexiunea obișnuită de firul care clipește, fiecare nod este adăugat câte două câmpuri de etichete unice (logice): ltag și rtag. Dacă valoarea etichetei este adevărată. câmpul de comunicare corespunzător este o legătură normală, în cazul unui mesaj fals, prin firul care clipește.
În acest sens, nodul unui copac binar convențional este reprezentat de o structură
Nodul binar de copaci are o structură diferită
Câmpurile logice din arborele cusut pot lua următoarele valori.
1. ltag = adevărat. prin urmare, stânga este o conexiune normală.
2. ltag = false. prin urmare, puncte de stânga la nodul predecesor.
3. rtag = adevărat. prin urmare, dreapta este o conexiune normală.
4. rtag = false. prin urmare, punctele corecte la nodul succesor.
Să considerăm inserarea unui vârf nou în stânga unui dat într-un arbore binar cusut simetric (Figura 6.2). În Fig. 6.3 arată arborele rezultat.
Fig. 6.2 - Arbore inițial cusut simetric
Fig. 5 - Arbore cusut după introducerea unui element nou în el
Aici a fost cerut să se introducă vertexul I sub formă de substrat de stânga al vârfului A. Dacă A nu are un substrat de stânga. Altfel, un nou vârf este introdus între A și fiul său stâng.
Pentru comoditatea creării și traversării arborelui, se folosește un cap cap suplimentar. care servește ca o traversare simetrică de predecesorul primului său vârf și de receptorul tuturor vârfurilor sale terminale.
Împreună cu avantajele arborilor cusute: bypass rapid, nu este nevoie de un stiva, puteți determina predecesorul și succesorul de top, există neajunsuri. Includerea unui nou vârf în copac durează mai mult timp, deoarece este necesar să se sprijine două tipuri de conexiuni: structura și firul. Prin urmare, este recomandabil să se utilizeze arborii cusute în acele probleme în care schimbările copacilor apar rar și adesea se efectuează crawleri.
Articole similare
Trimiteți-le prietenilor: