Tree traversal (cunoscut și ca tree search ) este un fel de traversare a graficului care determină procesul de vizitare (verificare și/sau actualizare) a fiecărui nod al structurii arborelui de date exact o dată. Asemenea traversări sunt clasificate după ordinea în care sunt vizitate nodurile. Algoritmii din articol se referă la arbori binari , dar pot fi generalizați la alți arbori.
Spre deosebire de listele legate , matricele unidimensionale și alte structuri de date liniare , care sunt parcurse canonic în ordine liniară, arborii pot fi parcurși într-o varietate de moduri. Copacii pot fi ocoliți „în adâncime” sau „în lățime”. Există trei moduri principale de a ocoli „în profunzime”
Parcurgerea arborelui trece iterativ prin toate nodurile conform unui algoritm. Deoarece există mai mult de un nod următor dintr-un nod dat (aceasta nu este o structură de date liniară), atunci, presupunând calcule secvențiale (mai degrabă decât paralele), unele noduri trebuie amânate, adică stocate într-un fel pentru vizita ulterioară. Acest lucru se face adesea cu o stivă (LIFO = ultimul intrat, primul ieşit) sau o coadă (FIFO = primul intrat, primul ieşit). Deoarece un arbore este o structură de date autoreferențială (autoreferențială, definită recursiv), traversarea poate fi definită prin recursivitate sau, mai subtil, prin corecursie într-un mod natural și clar. În aceste cazuri, nodurile în așteptare sunt stocate fie în mod explicit în stiva obișnuită , implicit în stiva de apeluri , fie în mod explicit în coadă .
Căutarea în profunzime este implementată cu ușurință printr-o stivă, inclusiv implementarea prin recursivitate (stiva de apeluri), în timp ce căutarea pe lățimea întâi este implementată cu ușurință printr-o coadă, inclusiv implementarea prin corecursie.
Aceste căutări se numesc căutări în profunzime , deoarece arborele de căutare este parcurs pe cât posibil în jos pe fiecare descendent înainte de a trece la următorul frate. Pentru un arbore binar, acestea sunt definite ca operații pentru a procesa un vârf recursiv la fiecare nod, începând de la rădăcină. Algoritmul de bypass este următorul [2] [3]
Abordare recursivă de bază pentru parcurgerea unui arbore binar (nevid): Pornind de la nodul N, faceți următoarele:
(L) Traversați recursiv subarborele din stânga. Acest pas se termină când lovește din nou nodul N.
(R) Traversați recursiv subarborele din dreapta. Acest pas se termină când lovește din nou nodul N.
(N) Procesează nodul N însuși.
Acești pași se pot face în orice ordine . Dacă (L) apare înainte de (R), procesul se numește traversare de la stânga la dreapta, în caz contrar, o traversare de la dreapta la stânga. Următoarele metode arată traversări de la stânga la dreapta:
Bypass direct (NLR)
Într -un arbore de căutare binar, traversarea centrată preia datele în ordine sortată. [4] .
Secvența de traversare se numește secvențiere arborescentă. Secvența de traversare este o listă a tuturor nodurilor vizitate. Niciuna dintre secvenționările înainte, înapoi sau centrate nu descrie în mod unic un arbore. Având în vedere un arbore cu elemente distincte, traversarea înainte sau înapoi împreună cu o traversare centrată sunt suficiente pentru a descrie arborele în mod unic. Cu toate acestea, traversarea înainte împreună cu traversarea inversă lasă o oarecare ambiguitate în structura arborescentă [5] .
Arborele de vedere generalăPentru a parcurge orice arbore prin căutarea în profunzime, următoarele operații sunt efectuate recursiv pentru fiecare nod:
În funcție de sarcina curentă, operațiunile de traversare înainte, înapoi sau centrată pot fi goale sau este posibil să doriți să vizitați doar un anumit copil, deci aceste operațiuni sunt opționale. În practică, poate fi necesară mai mult de o operație de traversare înainte, înapoi sau centrată. De exemplu, la introducerea într-un arbore ternar, operația de traversare înainte se realizează prin compararea elementelor. După aceasta, poate fi necesară o operație de întoarcere pentru a echilibra arborele.
Copacii pot fi, de asemenea, traversați în ordinea nivelului , unde vizităm fiecare nod într-un nivel înainte de a trece la nivelul următor. O astfel de căutare se numește breadth - first search (BFS).
Există, de asemenea, algoritmi de traversare care nu sunt clasificați nici ca căutare în profunzime, nici ca căutare pe lățime. Un astfel de algoritm este metoda Monte Carlo , care se concentrează pe analiza celor mai promițătoare mișcări bazate pe extinderea arborelui de căutare în timp ce alegerea aleatorie a spațiului de căutare.
Traversarea înainte la duplicarea nodurilor și marginilor poate face o duplicare completă a unui arbore binar . Aceasta poate fi folosită pentru a crea o expresie de prefix ( notație poloneză ) din arborii de expresii , pentru care repetăm expresia în ordine directă.
Parcursul centrat este cel mai frecvent utilizat în arborii de căutare binari, deoarece returnează valori din setul de bază în ordinea determinată de funcția de comparație care definește arborele de căutare binar.
Traversarea inversă la ștergerea sau eliberarea nodurilor poate șterge sau elibera întregul arbore binar. Traversarea generează, de asemenea, o reprezentare postfixă a arborelui binar.
| precomandă (nod) dacă (nod = null ) returnează vizita (nod) precomanda(node.left) precomanda (nodul dreapta) | iterativPreorder (nod) dacă (nod = null ) returnează s ← stivă goală s.push(nod) în timp ce ( nu s.isEmpty()) nod ← s.pop() vizita (nod) //copilul din dreapta este împins primul, deci copilul din stânga este procesat primul dacă (nod.right ≠ null ) s.push(nod.dreapta) dacă (nod.stânga ≠ nul ) s.push(nod.stânga) |
| în ordine (nod) dacă (nod = null ) returnează inorder(node.stânga) vizita (nod) în ordine (nodul dreapta) | iterativeInorder (nod) s ← stivă goală în timp ce ( nu s.isEmpty() sau nodul ≠ nul ) dacă (nodul ≠ nul ) s.push(nod) nod ← nod.stânga altfel nod ← s.pop() vizita (nod) nod ← nod.dreapta |
| postorder (nod) dacă (nod = null ) returnează postorder(node.stânga) post-ordine (nodul dreapta) vizita (nod) | iterativPostorder (nod) s ← stivă goală lastNodeVisited ← null while ( nu s.isEmpty() sau nod ≠ null ) if (nodul ≠ null ) s.push(nod) nod ← nod.stânga altfel peekNode ← peek() // dacă copilul drept există și traversarea a venit de la copilul stâng, deplasați-vă la dreapta dacă (peekNode.right ≠ null și lastNodeVisited ≠ peekNode.right) nod ← peekNode.right altfel vizitați(peekNode) lastNodeVisited ← s.pop() |
Toate implementările de mai sus necesită o stivă proporțională cu înălțimea arborelui, care este stiva de apeluri pentru implementarea recursivă și stiva părinte pentru cea iterativă. Într-un copac prost echilibrat, această stivă poate fi semnificativă. Într-o implementare iterativă, putem scăpa de stiva prin stocarea fiecărui nod în părintele său sau prin utilizarea cusăturii arborelui (secțiunea următoare).
Bypass Morris centrat pe firmwareArborele binar este îmbinat dându-i fiecărui pointer copil stâng (care altfel este întotdeauna gol = nul) un pointer către predecesorul nodului în ordine centrată (dacă există unul) și fiecărui pointer copil din dreapta (care altfel este întotdeauna gol) un pointer către următorul nod în ordinea centrată.ordinea centrată (dacă există).
Avantaje:
Defecte:
Morris walk este o implementare a mersului centrat folosind firmware [6] :
Mai jos este pseudocodul pentru o simplă parcurgere strat cu strat bazată pe coadă . Algoritmul necesită un spațiu proporțional cu numărul maxim de noduri din niveluri. Această valoare poate atinge jumătate din toate nodurile. O abordare mai eficientă a memoriei pentru acest tip de traversare poate fi implementată folosind căutarea depth-first cu aprofundare iterativă .
levelorder (rădăcină) q ← coadă goală q.enqueue(rădăcină) în timp ce ( nu q.isEmpty()) nodul ← q.dequeue() vizita (nod) dacă (nod.stânga ≠ nul ) q.enqueue(nod.left) dacă (nod.right ≠ null ) q.enqueue(nod.right)Parcursul se face de obicei pentru copaci cu un număr finit de noduri (deci adâncime finită și factor de ramificare finit ), dar se poate face și pentru copaci infiniti. O astfel de parcurgere este de interes în special în programarea funcțională (pentru evaluare leneșă ), deoarece structurile infinite de date pot fi adesea definite și manipulate cu ușurință, deși nu pot fi (riguros) calculate, deoarece ar dura un timp infinit. Unii copaci finiți sunt prea mari pentru a fi reprezentați în mod explicit, cum ar fi arborele de joc șah sau go , așa că este logic să îi tratăm ca infiniti.
Principala cerință a traversării este să vizitați toate nodurile. Pentru copaci infiniti, algoritmii simpli nu pot face acest lucru. De exemplu, dacă există un arbore binar de adâncime infinită, căutarea depth-first se va deplasa de-a lungul unei laturi (de obicei partea stângă) a arborelui, fără a vizita niciodată restul vârfurilor și, în plus, o traversare centrată sau înapoi nu se va deplasa niciodată. vizitați orice nod, deoarece nu ajunge niciodată la frunză. În schimb, parcurgerea pe lățimea întâi (nivel cu nivel) traversează fără probleme un arbore binar de adâncime infinită și, în plus, traversează orice arbore cu un factor de ramificare limitat.
Pe de altă parte, având în vedere un arbore de adâncime 2 în care rădăcina are un număr infinit de copii și fiecare nod copil are doi copii, căutarea depth-first va vizita toate nodurile, deoarece, ocolind nepoții (copiii celui de-al doilea nivel), trece la următorul nod (presupunând că aceasta nu este o traversare înapoi care nu ajunge niciodată la rădăcină). În schimb, căutarea pe lățimea întâi nu va ajunge niciodată la nepoți, deoarece trebuie să se repete mai întâi asupra tuturor copiilor (nivelul I).
O analiză mai sofisticată a timpului de rulare poate fi făcută folosind numere ordinale infinite . De exemplu, o căutare pe lățimea întâi într-un arbore cu adâncimea 2 (ca mai sus) va dura ω ·2 pași - ω pentru primul nivel și un alt ω pentru al doilea nivel.
Astfel, căutările simple în primul rând în adâncime și în lățime nu traversează niciun copac infinit și sunt ineficiente pe arbori foarte mari. Cu toate acestea, metodele hibride pot traversa orice arbore infinit (numărabil), în principal prin argumentul diagonal („diagonală”, o combinație de verticală și orizontală, corespunde unei combinații de căutare depth-first și breadth-first search).
Mai exact, având în vedere un arbore cu ramificare infinită de adâncime infinită, etichetăm rădăcina (), copiii rădăcinii (1), (2), ..., nepoții (1, 1), (1, 2), ... , (2, 1), (2, 2), … și așa mai departe. Nodurile sunt apoi în corespondență unu-la-unu cu secvențe finite (posibil goale) de numere pozitive, a căror mulțime este numărabilă și poate fi ordonată mai întâi după suma elementelor și apoi după ordine lexicografică în cadrul unor secvențe cu o sumă dată . (doar un număr finit de secvențe dă o sumă dată , astfel încât toate nodurile sunt atinse; formal vorbind, există un număr finit de compoziții ale unui număr natural dat, și anume 2 n − 1 compoziții). Această ordine definește traversarea arborelui. Specific:
0: () unsprezece) 2: (1, 1) (2) 3: (1, 1, 1) (1, 2) (2, 1) (3) 4: (1, 1, 1, 1) (1, 1, 2) (1, 2, 1) (1, 3) (2, 1, 1) (2, 2) (3, 1) (4)etc..
Acest lucru poate fi interpretat ca maparea unui arbore binar infinit de adânc la acest tip de arbore și aplicarea unei căutări pe lățimea întâi - înlocuiți marginile „jos” care conectează nodul părinte cu al doilea și cu alții copii, cu marginile „dreapta” de la primul copil la al doilea, de la al doilea la al treilea și așa mai departe. Apoi la fiecare pas fie ne deplasăm în jos (adăugăm (, 1) până la sfârșit), fie mergem la dreapta (adăugăm unul la ultimul număr) (cu excepția rădăcinii, din care nu poți decât să cobori), care arată relația dintre arborele binar infinit și numerotarea de mai sus. Suma intrărilor (fără una) corespunde distanței de la rădăcină, care este în concordanță cu 2 n − 1 noduri și adâncimea n − 1 într-un arbore binar infinit (2 corespunde arborelui binar).
| Algoritmi de căutare grafică | ||
|---|---|---|
| Metode neinformate | ||
| Metode informate | ||
| Comenzi rapide | ||
| Arborele de întindere minim | ||
| Alte | ||
| Arborele (structura de date) | |
|---|---|
| Arbori binari | |
| Arbori binari cu auto-echilibrare |
|
| B-copaci |
|
| arbori de prefix |
|
| Partiționarea binară a spațiului | |
| Arbori non-binari |
|
| Despărțirea spațiului |
|
| Alți copaci |
|
| Algoritmi | |