Trädsökning

Till skillnad från länkade listor, endimensionella matriser och andra linjära datastrukturer, som kanoniskt sett genomkorsas i linjär ordning, kan träd genomkorsas på flera olika sätt. De kan genomgås i djup först- eller bredd först-ordning. Det finns tre vanliga sätt att genomkorsa dem i djup-första ordning: i ordning, i förordning och i efterordning. Utöver dessa grundläggande genomgångsmetoder är det möjligt att använda olika mer komplexa eller hybrida metoder, t.ex. djupbegränsade sökningar som iterativ fördjupning av djupförsta sökning. Det senare, liksom breadth-first search, kan också användas för att traversera oändliga träd, se nedan.

Datastrukturer för trädtraverseringRedigera

Traversering av ett träd innebär att man itererar ö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), måste vissa noder, om man utgår från sekventiell beräkning (inte parallell), skjutas upp och lagras på något sätt för senare besök. Detta görs ofta med hjälp av en stapel (LIFO) eller en kö (FIFO). Eftersom ett träd är en självrefererande (rekursivt definierad) datastruktur kan traversering definieras genom rekursion eller, mer subtilt, corecursion, på ett mycket naturligt och tydligt sätt; i dessa fall lagras de uppskjutna noderna implicit i anropsstapeln.

Djupförsta sökning är lätt att genomföra via en stapel, även rekursivt (via anropsstapeln), medan breddförsta sökning är lätt att genomföra via en kö, även corecursivt.:45-61

Djupförsta sökning av binärt trädRedigera

Djupförsta traversering (prickad väg) av ett binärt träd:

• Förordningsordning (tillgång till nod vid position röd ●):

  F, B, A, D, C, E, G, I, H;

• I ordning (tillgång till noder vid positionen grön ●):

  A, B, C, D, E, F, G, H, I;

• Efterordning (tillgång till noder vid positionen blå ●):

  A, C, E, D, B, H, I, G, F.

Dessa sökningar kallas DFS (depth-first search), eftersom sökträdet fördjupas så mycket som möjligt på varje barn innan man går till nästa syskon. För ett binärt träd definieras de som åtkomstoperationer vid varje nod, med början i den aktuella noden, vars algoritm är följande:

Det generella rekursiva mönstret för att genomkorsa ett binärt träd är följande:

1. Gå ner en nivå till det rekursiva argumentet N. Om N existerar (är icke-tomt), utför följande tre operationer i en viss ordning: L: Genomkorsa rekursivt N:s vänstra delträd. R: Återkommande genomgång av N:s högra delträd. N: Tillgång till (besök) den aktuella noden N själv.
2. Returnera genom att gå upp en nivå och komma fram till N:s överordnade nod.

Det finns tre metoder (mönster) vid vilken position i parcoursen (traversal) i förhållande till noden (i figuren: röd, grön eller blå) som besöket (åtkomsten) av noden skall äga rum. Valet av exakt en färg bestämmer exakt ett besök av en nod enligt beskrivningen nedan. Tillgång till alla tre färgerna resulterar i ett trefaldigt besök av samma nod vilket ger ”all-order” sekventialisering:

F-B-A-A-A-A-B-D-C-C-C-C-D-D-E-E-E-E-D-B-F-F-G-G-G- I-H-H-H-H- I- I-G-F

Pre-order, NLREdit

1. Access the data part of the current node (i figuren: position red).
2. Genomgång av det vänstra delträdet genom att rekursivt anropa pre-order-funktionen.
3. Genomgång av det högra delträdet genom att rekursivt anropa pre-order-funktionen.

Den förordnade traverseringen är topologiskt sorterad, eftersom en överordnad nod behandlas innan någon av dess underordnade noder behandlas.

In-order, LNREdit

1. Traversera det vänstra underträdet genom att rekursivt anropa funktionen in-order.
2. Access the data part of the current node (in the figure: position green).
3. Traverse the right subtree by recursively calling the in-order function.

I ett binärt sökträd som är ordnat så att nyckeln i varje nod är större än alla nycklar i dess vänstra delträd och mindre än alla nycklar i dess högra delträd hämtar in-order traversal nycklarna i stigande sorterad ordning.

Omvänd inbördes ordning, RNLEdit

1. Traversera det högra delträdet genom att rekursivt anropa funktionen omvänd inbördes ordning.
2. Access till datadelen av den aktuella noden.
3. Traversera det vänstra delträdet genom att rekursivt anropa funktionen omvänd inbördes ordning.

I ett binärt sökträd hämtar omvänd inordertraversering nycklarna i fallande sorterad ordning.

Post-order, LRNEdit

1. Traversera det vänstra underträdet genom att rekursivt anropa postorderfunktionen.
2. Genomgång av det högra delträdet genom att rekursivt anropa efterordningsfunktionen.
3. Access till datadelen av den aktuella noden (i figuren: position blå).

Spåren av en genomgång kallas för en sekventialisering av trädet. Traversalspåret är en lista över varje besökt nod. Ingen sekventialisering enligt pre-, in- eller postordning beskriver det underliggande trädet på ett entydigt sätt. Givet ett träd med distinkta element räcker det med antingen pre-order eller post-order i kombination med in-order för att beskriva trädet på ett entydigt sätt. Pre-order med post-order lämnar dock en viss tvetydighet i trädstrukturen.

Generic treeEdit

För att genomkorsa ett träd med djupgående första sökning utför du följande operationer vid varje nod:

1. Om noden inte finns återgår du.
2. Access (= besök) node (pre-order position).
3. För varje i från 1 till number_of_children – 1 gör:
   1. Rekursivt genomgång av i:e barnet.
   2. Access node (in-order position).
4. Recursivt traverse sista barnet.
5. Access node (post-order position).

Avhängigt av det aktuella problemet kan operationerna pre-order, post-order och särskilt en av operationerna (number_of_children – 1) in-order vara ogiltiga, eller så vill man bara ha tillgång till ett specifikt barn, så dessa operationer är valfria. I praktiken kan det också krävas mer än en av operationerna för förordning, inordning och efterordning. När man t.ex. infogar i ett ternärt träd, utförs en operation i förordning genom att jämföra objekt. En efterordningsoperation kan behövas efteråt för att återbalansera trädet.

Breadth-first search, or level orderEdit

Level-order: F, B, G, A, D, I, C, E, H.

Träd kan också genomkorsas i nivåordning, där vi besöker varje nod på en nivå innan vi går till en lägre nivå. Denna sökning kallas breadth-first search (BFS), eftersom sökträdet breddas så mycket som möjligt på varje djup innan vi går till nästa djup.

Andra typerRedigera

Det finns också trädtraverseringsalgoritmer som klassificeras som varken depth-first search eller breadth-first search. En sådan algoritm är Monte Carlo Tree Search, som koncentrerar sig på att analysera de mest lovande dragen och baserar expansionen av sökträdet på ett slumpmässigt urval av sökutrymmet.