Trädpassering
Inom datavetenskap är trädgenomgång (även känd som trädsökning och gå i trädet ) en form av genomgång av grafer och hänvisar till processen att besöka (t.ex. hämta, uppdatera eller ta bort) varje nod i en träddatastruktur , exakt en gång. Sådana genomgångar klassificeras efter den ordning i vilken noderna besöks. Följande algoritmer beskrivs för ett binärt träd , men de kan också generaliseras till andra träd.
Typer
Till skillnad från länkade listor , endimensionella arrayer och andra linjära datastrukturer , som kanoniskt korsas i linjär ordning, kan träd korsas på flera sätt. De kan korsas i djup-först eller bredd-första ordning. Det finns tre vanliga sätt att gå igenom dem i djup-första ordning: i beställning, förbeställning och efterbeställning. Utöver dessa grundläggande genomgångar är olika mer komplexa eller hybridscheman möjliga, till exempel djupbegränsade sökningar som iterativ fördjupning djup-först-sökning . Det senare, liksom bredd-först-sökning, kan också användas för att korsa oändliga träd, se nedan .
Datastrukturer för trädpassering
Att korsa ett träd innebär att iterera över alla noder på något sätt. Eftersom det från en given nod finns mer än en möjlig nästa nod (det är inte en linjär datastruktur), då, om man antar sekventiell beräkning (inte parallell), måste vissa noder skjutas upp – lagras på något sätt för senare besök. Detta görs ofta via en stack (LIFO) eller kö (FIFO). Eftersom ett träd är en självreferensiell (rekursivt definierad) datastruktur, kan traversering definieras genom rekursion eller, mer subtilt, corecursion , på ett naturligt och tydligt sätt; i dessa fall lagras de uppskjutna noderna implicit i anropsstacken .
Djup-först-sökning implementeras enkelt via en stack, inklusive rekursivt (via anropsstacken), medan bredd-först-sökning enkelt implementeras via en kö, inklusive corekursivt.
Djup-första sökning
I depth-first search (DFS) fördjupas sökträdet så mycket som möjligt innan man går till nästa syskon.
För att korsa binära träd med djup-först-sökning, utför följande operationer vid varje nod:
- Om den aktuella noden är tom, gå tillbaka.
- Utför följande tre operationer i en viss ordning:
- N: Besök den aktuella noden.
- L: Gå rekursivt genom den nuvarande nodens vänstra underträd.
- R: Gå rekursivt genom den aktuella nodens högra underträd.
Spåret av en traversering kallas en sekventialisering av trädet. Traversalspåret är en lista över varje besökt nod. Ingen sekventialisering enligt pre-, in- eller postorder beskriver det underliggande trädet unikt. Med tanke på ett träd med distinkta element räcker antingen förbeställning eller efterbeställning ihop med in-order för att beskriva trädet unikt. Förbeställning med efterbeställning lämnar dock en viss otydlighet i trädstrukturen.
Det finns tre metoder vid vilken position av genomgången i förhållande till noden (i figuren: röd, grön eller blå) besöket av noden ska ske. Valet av exakt en färg avgör exakt ett besök av en nod enligt beskrivningen nedan. Besök i alla tre färgerna resulterar i ett trefaldigt besök av samma nod, vilket ger sekvenseringen av "all-order":
- F - B - A - A - A - B - D - C - C - C - D - E - E - E - D - B - F - G - G - I - H - H - H - I - I - G - F
Förbeställ, NLR
- Besök den aktuella noden (i figuren: position röd).
- Gå rekursivt genom den aktuella nodens vänstra underträd.
- Gå rekursivt genom den aktuella nodens högra underträd.
Förbeställningsgenomgången är topologiskt sorterad , eftersom en överordnad nod bearbetas innan någon av dess underordnade noder är klar.
Postorder, LRN
- Gå rekursivt genom den aktuella nodens vänstra underträd.
- Gå rekursivt genom den aktuella nodens högra underträd.
- Besök den aktuella noden (i figuren: position blå).
Post-order-traversal kan vara användbart för att få postfix-uttryck av ett binärt uttrycksträd .
I ordning, LNR
- Gå rekursivt genom den aktuella nodens vänstra underträd.
- Besök den aktuella noden (i figuren: position grön).
- Gå rekursivt genom den aktuella nodens högra underträd.
I ett binärt sökträd ordnat så att nyckeln i varje nod är större än alla nycklar i dess vänstra underträd och mindre än alla nycklar i dess högra underträd, hämtar genomgång i ordning nycklarna i stigande sorterad ordning .
Omvänd förbeställning, NRL
- Besök den aktuella noden.
- Gå rekursivt genom den aktuella nodens högra underträd.
- Gå rekursivt genom den aktuella nodens vänstra underträd.
Omvänd postorder, RLN
- Gå rekursivt genom den aktuella nodens högra underträd.
- Gå rekursivt genom den aktuella nodens vänstra underträd.
- Besök den aktuella noden.
Omvänd i ordning, RNL
- Gå rekursivt genom den aktuella nodens högra underträd.
- Besök den aktuella noden.
- Gå rekursivt genom den aktuella nodens vänstra underträd.
I ett binärt sökträd ordnat så att nyckeln i varje nod är större än alla nycklar i dess vänstra underträd och mindre än alla nycklar i dess högra underträd, hämtar omvänd genomgång i ordning nycklarna i fallande sorterad ordning .
Godtyckliga träd
För att korsa godtyckliga träd (inte nödvändigtvis binära träd) med djup-först-sökning, utför följande operationer vid varje nod:
- Om den aktuella noden är tom, gå tillbaka.
- Besök den aktuella noden för genomgång av förbeställning.
- För varje i från 1 till den nuvarande nodens antal underträd − 1, eller från det senare till det förra för omvänd traversering, gör:
- Passera rekursivt den nuvarande nodens i -te underträd.
- Besök den aktuella noden för övergång i ordning.
- Gå rekursivt genom den aktuella nodens sista underträd.
- Besök den aktuella noden för efterbeställning.
Beroende på problemet kan förbeställning, efterbeställning och särskilt ett av antalet underträd − 1 operation i ordning vara valfritt. Dessutom kan i praktiken mer än en av förbeställnings-, efterbeställnings- och beställningsoperationer krävas. Till exempel, när du infogar i ett ternärt träd, utförs en förbeställningsoperation genom att jämföra objekt. En efterbeställningsoperation kan behövas efteråt för att återbalansera trädet.
Utöka första sökningen
I bredd-först-sökning (BFS) eller sökning på nivåordning breddas sökträdet så mycket som möjligt innan du går till nästa djup.
Andra typer
Det finns också trädgenomgångsalgoritmer som klassificeras som varken djup-först-sökning eller bredd-först-sökning. En sådan algoritm är Monte Carlo-trädsökning , som koncentrerar sig på att analysera de mest lovande dragen och basera utökningen av sökträdet på slumpmässigt urval av sökutrymmet.
Ansökningar
Genomgång av förbeställning kan användas för att göra ett prefixuttryck ( polsk notation ) från uttrycksträd : gå igenom uttrycksträdet i förväg. Till exempel, korsning av det avbildade aritmetiska uttrycket i förbeställning ger "+ * A − B C + D E ". I prefixnotation finns det inget behov av några parenteser så länge varje operator har ett fast antal operander. Genomgång av förbeställning används också för att skapa en kopia av trädet.
Post-order-traversering kan generera en postfix-representation ( omvänd polsk notation ) av ett binärt träd. Att korsa det avbildade aritmetiska uttrycket i efterordning ger " A B C − * D E + +"; den senare kan enkelt omvandlas till maskinkod för att utvärdera uttrycket av en stackmaskin . Postorder-traversering används också för att ta bort trädet. Varje nod frigörs efter att dess barn har frigjorts.
Traversal i ordning används mycket ofta på binära sökträd eftersom den returnerar värden från den underliggande uppsättningen i ordning, enligt komparatorn som satte upp det binära sökträdet.
Genomföranden
Depth-first search implementering
Förbeställ implementering
procedur förbeställning(nod) om nod = noll återbesök (nod) förbeställning(nod.vänster) förbeställning(nod.höger)
|
procedure iterativePreorder(node) if node = null return stack ← tom stack stack.push(node) while not stack.isEmpty() node ← stack.pop() visit(node) // höger underordnat trycks först så att vänster bearbetas först om node.höger ≠ null stack.push(nod.höger) om nod.vänster ≠ null stack.push(nod.vänster)
|
Implementering efter beställning
procedure postorder(node) if node = null return postorder(node.left) postorder(node.right) visit(node)
|
procedure iterativePostorder(nod) stack ← tom stack lastNodeVisited ← null medan inte stack.isEmpty() eller nod ≠ null om nod ≠ null stack.push(nod) nod ← node.left else peekNode ← //.peek() barn finns och passerar nod // från vänster barn, flytta sedan åt höger om peekNode.right ≠ null och lastNodeVisited ≠ peekNode.right node ← peekNode.right annars besök(peekNode) lastNodeVisited ← stack.pop()
|
Implementering i ordning
procedure inorder(node) if node = null return inorder(node.left) visit(node) inorder(node.right)
|
procedure iterativeInorder(nod) stack ← tom stack medan inte stack.isEmpty() eller nod ≠ null om nod ≠ null stack.push(nod) nod ← node.left else nod ← stack.pop() besök(nod) nod ← nod .höger
|
En annan variant av Pre-order
Om trädet representeras av en array (första indexet är 0), är det möjligt att beräkna indexet för nästa element: [ förtydligande behövs ]
procedur bubbleUp(array, i, leaf) k ← 1 i ← (i - 1)/2 medan (blad + 1) % (k * 2) ≠ k i ← (i - 1)/2 k ← 2 * k return i procedur förbeställning(array) i ← 0 medan i ≠ array.size visit(array[i]) om i = storlek - 1 i ← storlek annars om i < storlek/2 i ← i * 2 + 1 annat blad ← i - storlek /2 parent ← bubble_up(array, i, leaf) i ← parent * 2 + 2
Går vidare till nästa eller föregående nod
Noden som ska startas med kan ha hittats i det binära sökträdet bst med hjälp av en standardsökfunktion, som här visas i en implementering utan föräldrapekare, dvs den använder en stack för att hålla förfäderpekarna.
procedursökning (bst, nyckel) // returnerar en (nod, stack) nod ← bst.root stack ← tom stack medan nod ≠ null stack.push(nod) om nyckel = nod.nyckel retur (nod, stack) om nyckel < node.key node ← node.left else node ← node.right retur ( null , tom stack )
Funktionen inorderNext returnerar in-order- predecessorn en i-ordning-granne till nod , antingen in-order- successorn stacken (för dir=1 ) eller (för dir=0 ), och den uppdaterade , så att binärt sökträd kan sekventiellt genomgås i ordningsföljd och genomsökas i den givna riktningen längre fram.
procedur inorderNext(nod, dir, stack) nynod ← nod.barn[dir] om nynod ≠ null gör nod ← nynod stack.push(nod) nynod ← nod.barn[1-dir] tills nynod = nollretur (nod, stack ) // noden har inte ett dir-child: gör om stack.isEmpty() return ( null , tom stack ) oldnode ← nod node ← stack.pop() // förälder till oldnode tills oldnode ≠ node.child[dir] // nu oldnode = nod.child[1-dir], // dvs nod = förfader (och föregångare/efterträdare) till den ursprungliga nodens retur (nod, stack)
Observera att funktionen inte använder nycklar, vilket innebär att den sekventiella strukturen registreras helt av det binära sökträdets kanter. För traverser utan riktningsändring är den ( avskrivna ) medelkomplexiteten eftersom en full traversering tar steg för en BST av storlek 1 steg för kant upp och 1 för kant ner. Den värsta komplexiteten är med som höjden på trädet.
Alla ovanstående implementeringar kräver stackutrymme proportionellt mot trädets höjd som är en anropsstack för den rekursiva och en överordnad (förfader) stack för de iterativa. I ett dåligt balanserat träd kan detta vara avsevärt. Med de iterativa implementeringarna kan vi ta bort stackkravet genom att behålla överordnade pekare i varje nod, eller genom att tråda trädet (nästa avsnitt).
Morris in-order traversering med gängning
Ett binärt träd trådas genom att varje vänster underordnad pekare (som annars skulle vara noll) pekar mot nodens föregångare i sin ordning (om den finns) och varje höger underordnad pekare (som annars skulle vara null) pekar på in- nodens efterföljare (om den finns).
Fördelar:
- Undviker rekursion, som använder en samtalsstack och förbrukar minne och tid.
- Noden håller ett register över sin förälder.
Nackdelar:
- Trädet är mer komplext.
- Vi kan bara göra en övergång åt gången.
- Det är mer benäget att göra fel när båda barnen inte är närvarande och båda nodvärdena pekar på deras förfäder.
Morris-traversal är en implementering av in-order-traversal som använder trådning:
- Skapa länkar till efterföljaren i ordning.
- Skriv ut data med hjälp av dessa länkar.
- Återställ ändringarna för att återställa det ursprungliga trädet.
Utöka första sökningen
Också, listad nedan är pseudokod för en enkel köbaserad genomgång av nivåordning, och kommer att kräva utrymme proportionellt mot det maximala antalet noder på ett givet djup. Detta kan vara så mycket som hälften av det totala antalet noder. Ett mer utrymmeseffektivt tillvägagångssätt för denna typ av traversering kan implementeras med hjälp av en iterativ fördjupande djup-först-sökning .
procedure levelorder(node) queue ← tom kö queue.enqueue(node) while not queue.isEmpty() node ← queue.dequeue() visit(node) if node.left ≠ null queue.enqueue(node.left) if node. höger ≠ null queue.enqueue(node.right)
Om trädet representeras av en array (första indexet är 0), räcker det att iterera genom alla element:
0 procedur levelorder(array) för i från till array.size visit(array[i])
Oändliga träd
Medan traversering vanligtvis görs för träd med ett ändligt antal noder (och därmed ändligt djup och ändlig förgreningsfaktor ) kan det också göras för oändliga träd. Detta är av särskilt intresse för funktionell programmering (särskilt med lat utvärdering ), eftersom oändliga datastrukturer ofta lätt kan definieras och arbetas med, även om de inte (strikt) utvärderas, eftersom detta skulle ta oändlig tid. Vissa finita träd är för stora för att representera explicit, till exempel spelträdet för schack eller go , och därför är det användbart att analysera dem som om de vore oändliga.
Ett grundläggande krav för att passera är att besöka varje nod så småningom. För oändliga träd misslyckas ofta enkla algoritmer detta. Till exempel, givet ett binärt träd med oändligt djup, kommer en djup-först-sökning att gå ner på ena sidan (enligt den vänstra sidan) av trädet, aldrig besöka resten, och verkligen en in-order- eller post-order-genomgång kommer aldrig besöka några noder, eftersom det inte har nått ett löv (och faktiskt aldrig kommer). Däremot kommer en genomgång av bredd-först (nivåordning) att passera ett binärt träd med oändligt djup utan problem, och kommer verkligen att korsa vilket träd som helst med en begränsad förgreningsfaktor.
Å andra sidan, givet ett träd av djup 2, där roten har oändligt många barn, och vart och ett av dessa barn har två barn, kommer en djup-första sökning att besöka alla noder, eftersom det när det tröttar ut barnbarnen (barn till barn till en nod), kommer den att gå vidare till nästa (förutsatt att den inte är postorder, i vilket fall den aldrig når roten). Däremot kommer en bredd-först-sökning aldrig att nå barnbarnen, eftersom den försöker utmatta barnen först.
En mer sofistikerad analys av körtiden kan ges via oändliga ordningstal ; till exempel, sökningen på bredden-först av djup 2-trädet ovan kommer att ta ω ·2 steg: ω för den första nivån, och sedan en annan ω för den andra nivån.
Enkla sökningar med djup-först eller bredd-först går alltså inte igenom alla oändliga träd och är inte effektiva på mycket stora träd. Hybridmetoder kan dock korsa vilket som helst (uträknat) oändligt träd, huvudsakligen via ett diagonalt argument ("diagonal" - en kombination av vertikal och horisontell - motsvarar en kombination av djup och bredd).
Konkret, givet det oändligt förgrenade trädet av oändligt djup, märk roten (), rotens barn (1), (2), …, barnbarnen (1, 1), (1, 2), …, (2) , 1), (2, 2), … och så vidare. Noderna är alltså i en -till-en- överensstämmelse med ändliga (eventuellt tomma) sekvenser av positiva tal, som är räknbara och kan placeras i ordning först efter summan av poster, och sedan efter lexikografisk ordning inom en given summa (endast ändligt många sekvenser summerar till ett givet värde, så alla poster nås – formellt finns det ett ändligt antal sammansättningar av ett givet naturligt tal, närmare bestämt 2 n −1 sammansättningar av n ≥ 1 ), vilket ger en genomgång. Explicit:
- ()
- (1)
- (1, 1) (2)
- (1, 1, 1) (1, 2) (2, 1) (3)
- (1, 1, 1, 1) (1, 1, 2) (1, 2, 1) (1, 3) (2, 1, 1) (2, 2) (3, 1) (4)
etc.
Detta kan tolkas som att man kartlägger det binära trädet med oändligt djup på detta träd och sedan tillämpar sökning med bredd-först: ersätt de "nedåt" kanterna som förbinder en föräldernod med dess andra och senare barn med "höger" kanter från det första barnet till det andra barn, från det andra barnet till det tredje barnet, etc. Sålunda kan man vid varje steg antingen gå ner (lägg till en (, 1) i slutet) eller gå höger (lägg till en till den sista siffran) (förutom roten, som är extra och kan bara gå ner), vilket visar överensstämmelsen mellan det oändliga binära trädet och ovanstående numrering; summan av posterna (minus en) motsvarar avståndet från roten, vilket överensstämmer med de 2 n −1 noderna på djupet n − 1 i det oändliga binära trädet (2 motsvarar binärt).
Källor
- Dale, Nell. Lilly, Susan D. "Pascal Plus Data Structures". DC Heath and Company. Lexington, MA. 1995. Fjärde upplagan.
- Drozdek, Adam. "Datastrukturer och algoritmer i C++". Brook/Cole. Pacific Grove, CA. 2001. Andra upplagan.
- "Tree Transversal" (math.northwestern.edu)