Procházení stromu (také známé jako vyhledávání ve stromech ) je druh procházení grafu , který způsobí, že každý uzel struktury datového stromu navštíví (zkontroluje a/nebo aktualizuje) právě jednou. Takové průchody jsou klasifikovány podle pořadí, ve kterém jsou uzly navštěvovány. Algoritmy v článku odkazují na binární stromy , ale lze je zobecnit na jiné stromy.
Na rozdíl od propojených seznamů , jednorozměrných polí a dalších lineárních datových struktur , které se kanonicky procházejí v lineárním pořadí, lze stromy procházet různými způsoby. Stromy lze obejít „do hloubky“ nebo „na šířku“. Existují tři hlavní způsoby, jak obejít „do hloubky“
Procházení stromu iterativně prochází všemi uzly podle nějakého algoritmu. Protože existuje více než jeden další uzel z daného uzlu (nejedná se o lineární datovou strukturu), pak za předpokladu sekvenčních (spíše než paralelních) výpočtů musí být některé uzly odloženy, tj. nějakým způsobem uloženy pro pozdější návštěvu. To se často provádí pomocí zásobníku (LIFO = poslední dovnitř, první ven) nebo fronty (FIFO = první dovnitř, první ven). Vzhledem k tomu, že strom je sebereferenční (sebe-referenční, definovaná rekurzivně) datová struktura, lze procházení definovat pomocí rekurze nebo, jemněji, pomocí korekurze přirozeným a jasným způsobem. V těchto případech jsou čekající uzly uloženy buď explicitně v běžném zásobníku , implicitně v zásobníku volání nebo explicitně ve frontě .
Hloubkové vyhledávání lze snadno implementovat prostřednictvím zásobníku, včetně implementace pomocí rekurze (zásobník volání), zatímco vyhledávání do šířky lze snadno implementovat prostřednictvím fronty, včetně implementace prostřednictvím corecursion.
Tato hledání se nazývají hloubkové prohledávání , protože strom hledání je u každého potomka procházen co nejdále dolů, než se přejde k dalšímu sourozenci. Pro binární strom jsou definovány jako operace pro rekurzivní zpracování vrcholu v každém uzlu, počínaje kořenem. Algoritmus bypassu je následující [2] [3]
Základní rekurzivní přístup pro procházení (neprázdného) binárního stromu: Začněte v uzlu N, proveďte následující:
(L) Projděte levý podstrom rekurzivně. Tento krok končí, když znovu narazí na uzel N.
(R) Projděte pravý podstrom rekurzivně. Tento krok končí, když znovu narazí na uzel N.
(N) Samotný procesní uzel N.
Tyto kroky lze provést v libovolném pořadí . Pokud (L) nastane před (R), proces se nazývá přechod zleva doprava, v opačném případě přechod zprava doleva. Následující metody ukazují průchody zleva doprava:
Přímý bypass (NLR)
V binárním vyhledávacím stromu získává centrované procházení data v seřazeném pořadí. [4] .
Sekvence procházení se nazývá stromová sekvence. Sekvence průchodu je seznam všech navštívených uzlů. Žádná z dopředných, zpětných nebo centrovaných sekvencí jednoznačně nepopisuje strom. Vzhledem k tomu, že strom obsahuje odlišné prvky, stačí k jedinečnému popisu stromu procházení vpřed nebo vzad spolu se středovým procházením. Přechod vpřed spolu s přejezdem zpět však zanechává ve stromové struktuře určitou nejednoznačnost [5] .
Celkový pohled na stromChcete-li procházet libovolným stromem hledáním do hloubky, provádějí se pro každý uzel rekurzivně následující operace:
V závislosti na aktuální úloze mohou být operace procházení vpřed, vzad nebo centrování prázdné nebo můžete chtít navštívit pouze konkrétní dítě, takže tyto operace jsou volitelné. V praxi může být vyžadována více než jedna operace posuvu vpřed, vzad nebo vystředění. Například při vkládání do ternárního stromu se operace dopředného průchodu provádí porovnáním prvků. Poté může být vyžadována zpětná operace, aby se strom vyrovnal.
Stromy lze také procházet v pořadí úrovní , kdy navštívíme každý uzel v úrovni, než přejdeme na další úroveň. Takové vyhledávání se nazývá prohledávání do šířky (BFS).
Existují také algoritmy procházení, které nejsou klasifikovány jako prohledávání do hloubky nebo prohledávání do šířky. Jedním z takových algoritmů je metoda Monte Carlo , která se zaměřuje na analýzu nejslibnějších tahů na základě expanze vyhledávacího stromu při náhodném výběru vyhledávacího prostoru.
Dopředné procházení při duplikování uzlů a hran může vytvořit úplnou duplikaci binárního stromu . Toho lze využít k vytvoření předponového výrazu ( polský zápis ) z výrazových stromů , u kterého výraz v přímém pořadí iterujeme.
Středové procházení se nejčastěji používá v binárních vyhledávacích stromech , protože vrací hodnoty ze základní sady v pořadí určeném porovnávací funkcí, která definuje binární vyhledávací strom.
Zpětné procházení při mazání nebo uvolňování uzlů může smazat nebo uvolnit celý binární strom. Procházení také generuje postfixovou reprezentaci binárního stromu.
| preorder (node) if (node = null ) return návštěva (uzel) předobjednávka (node.left) předobjednávka (uzel vpravo) | iterativePreorder (node) if (node = null ) return s ← prázdný zásobník s.push(uzel) while ( ne s.isEmpty()) uzel ← s.pop() návštěva (uzel) //pravé dítě je tlačeno jako první, takže levé dítě je zpracováno jako první if (node.right ≠ null ) s.push(uzel.vpravo) if (node.left ≠ null ) s.push(uzel.levý) |
| inorder (node) if (node = null ) return inorder(uzel.left) návštěva (uzel) inorder (uzel vpravo) | iterativeInorder (uzel) s ← prázdný zásobník while ( ne s.isEmpty() nebo uzel ≠ null ) if (node ≠ null ) s.push(uzel) uzel ← uzel.vlevo jiný uzel ← s.pop() návštěva (uzel) uzel ← uzel.pravý |
| postorder (node) if (node = null ) return postorder(node.left) postorder (uzel vpravo) návštěva (uzel) | iterativePostorder (uzel) s ← prázdný zásobník lastNodeVisited ← null while ( ne s.isEmpty() nebo uzel ≠ null ) if (node ≠ null ) s.push(uzel) uzel ← uzel.vlevo jiný peekNode ← s.peek() // pokud existuje pravé dítě a přechod pochází od levého potomka, přesuňte se doprava if (peekNode.right ≠ null a lastNodeVisited ≠ peekNode.right) uzel ← peekNode.right jiný návštěva (peekNode) lastNodeVisited ← s.pop() |
Všechny výše uvedené implementace vyžadují zásobník úměrný výšce stromu, což je zásobník volání pro rekurzivní implementaci a nadřazený zásobník pro iterativní implementaci. U špatně vyváženého stromu může být tento zásobník významný. V iterativní implementaci se můžeme zbavit zásobníku uložením každého uzlu do jeho rodiče nebo použitím stromového sešívání (další sekce).
Firmware Centered Morris BypassBinární strom je spojen tak, že každému levému podřízenému ukazateli (který je jinak vždy prázdný = null) přiřadíte ukazatel na předchůdce uzlu ve vystředěném pořadí (pokud takový existuje) a každému pravému podřízenému ukazateli (který je jinak vždy prázdný) ukazatel na další uzel v centrovaném pořadí centrované pořadí (pokud takový existuje).
výhody:
nedostatky:
Morris walk je implementace centrované chůze pomocí firmwaru [6] :
Níže je pseudokód pro jednoduché procházení po vrstvách založené na frontě . Algoritmus vyžaduje prostor úměrný maximálnímu počtu uzlů v úrovních. Tato hodnota může dosáhnout poloviny všech uzlů. Paměťově efektivnější přístup pro tento typ procházení lze implementovat pomocí vyhledávání do hloubky s iterativním prohlubováním .
levelorder (kořen) q ← prázdná fronta q.enqueue(kořen) while ( ne q.isEmpty()) uzel ← q.dequeue() návštěva (uzel) if (node.left ≠ null ) q.enqueue(node.left) if (node.right ≠ null ) q.enqueue(node.right)Procházení se obvykle provádí pro stromy s konečným počtem uzlů (proto konečná hloubka a konečný faktor větvení ), ale lze jej provést i pro nekonečné stromy. Takové procházení je zajímavé zejména ve funkcionálním programování (pro líné vyhodnocování ), protože nekonečné datové struktury lze často snadno definovat a manipulovat s nimi, i když je nelze (přísně) vypočítat, protože by to trvalo nekonečně dlouho. Některé konečné stromy jsou příliš velké na to, aby je bylo možné explicitně znázornit, jako například herní strom šachy nebo go , takže má smysl s nimi zacházet jako s nekonečnými.
Hlavním požadavkem procházení je navštívit všechny uzly. U nekonečných stromů to jednoduché algoritmy nedokážou. Například, pokud existuje binární strom nekonečné hloubky, prohledávání do hloubky se bude pohybovat podél jedné strany (obvykle levé strany) stromu, nikdy nenavštíví zbytek vrcholů, a navíc centrovaný nebo zpětný přechod nikdy nebude navštivte jakýkoli uzel, protože nikdy nedosáhne listu. Naproti tomu procházení do šířky (úroveň po úrovni) projde binární strom nekonečné hloubky bez problémů a navíc projde jakýkoli strom s omezeným faktorem větvení.
Na druhou stranu, dáme-li strom hloubky 2, ve kterém má kořen nekonečný počet potomků a každý podřízený uzel má dvě děti, hloubkové prohledávání navštíví všechny uzly, protože obchází vnoučata (děti druhého úroveň), přesune se na další uzel (za předpokladu, že se nejedná o zpětný průchod, který nikdy nedosáhne kořene). Naproti tomu vyhledávání do šířky se nikdy nedostane k vnoučatům, protože musí nejprve iterovat všechny děti (1. úroveň).
Sofistikovanější analýzu provozní doby lze poskytnout pomocí nekonečných pořadových čísel . Například prohledávání do šířky ve stromu hloubky 2 (jak je uvedeno výše) bude trvat ω ·2 kroků - ω pro první úroveň a další ω pro druhou úroveň.
Jednoduché prohledávání do hloubky a do šířky tedy neprochází žádným nekonečným stromem a je neefektivní na velmi velkých stromech. Hybridní metody však mohou procházet jakýmkoli (spočítatelným) nekonečným stromem, a to především prostřednictvím argumentu diagonální („diagonální“, kombinace vertikálního a horizontálního, odpovídá kombinaci prohledávání do hloubky a prohledávání do šířky).
Konkrétně, vzhledem k nekonečně se rozvětvujícímu stromu nekonečné hloubky, označujeme kořen (), děti kořene (1), (2), ..., vnoučata (1, 1), (1, 2), ... , (2, 1), (2, 2), … a tak dále. Uzly jsou pak v korespondenci jedna ku jedné s konečnými (možná prázdnými) posloupnostmi kladných čísel, jejichž množina je spočetná a lze ji seřadit nejprve podle součtu prvků a poté podle lexikografického pořadí v sekvencích s daným součtem. (pouze konečný počet sekvencí dává daný součet , takže jsou dosaženy všechny uzly; formálně řečeno existuje konečný počet složení daného přirozeného čísla, konkrétně 2 n − 1 složení). Toto pořadí definuje procházení stromu. konkrétně:
0: () jedenáct) 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)atd..
To lze interpretovat jako mapování nekonečně hlubokého binárního stromu na tento druh stromu a použití prohledávání do šířky – nahraďte „dolní“ hrany spojující nadřazený uzel s druhým a dalšími potomky, „správnými“ okraji z prvního dítě na druhé, od druhého ke třetímu atd. Pak se v každém kroku buď posuneme dolů (přičteme (, 1) na konec) nebo jdeme doprava (přidáme jedničku k poslednímu číslu) (kromě kořene, ze kterého můžete pouze sestoupit), který ukazuje vztah mezi nekonečným binárním stromem a výše uvedeným číslováním. Součet vstupů (bez jednoho) odpovídá vzdálenosti od kořene, která odpovídá 2 n − 1 uzlům a hloubce n − 1 v nekonečném binárním stromu (2 odpovídá binárnímu stromu).
| Algoritmy vyhledávání grafů | ||
|---|---|---|
| Neinformované metody | ||
| Informované metody | ||
| Zkratky | ||
| Minimální kostra | ||
| jiný | ||
| Strom (datová struktura) | |
|---|---|
| Binární stromy | |
| Samovyrovnávací binární stromy |
|
| B-stromy |
|
| předponové stromy |
|
| Binární dělení prostoru | |
| Nebinární stromy |
|
| Rozbití prostoru |
|
| Jiné stromy |
|
| Algoritmy |
|