Baumdurchquerung – Wikipedia

Posted on by
before-content-x4

“Baumsuche” leitet hier weiter. Es ist nicht mit dem Suchbaum zu verwechseln.

In der Informatik Baumdurchquerung (auch bekannt als Baumsuche und auf dem Baum spazieren gehen) ist eine Form der Diagrammdurchquerung und bezieht sich auf den Prozess des Besuchs (Überprüfens und / oder Aktualisierens) jedes Knotens in einer Baumdatenstruktur genau einmal. Solche Durchquerungen werden nach der Reihenfolge klassifiziert, in der die Knoten besucht werden. Die folgenden Algorithmen werden für einen Binärbaum beschrieben, können jedoch auch auf andere Bäume verallgemeinert werden.

Im Gegensatz zu verknüpften Listen, eindimensionalen Arrays und anderen linearen Datenstrukturen, die kanonisch in linearer Reihenfolge durchlaufen werden, können Bäume auf mehrere Arten durchlaufen werden. Sie können in der Reihenfolge Tiefe zuerst oder Breite zuerst durchlaufen werden. Es gibt drei gängige Methoden, um sie in der Reihenfolge erster Tiefe zu durchlaufen: in der Reihenfolge, vor der Reihenfolge und nach der Reihenfolge.[1] Über diese grundlegenden Durchquerungen hinaus sind verschiedene komplexere oder hybride Schemata möglich, z. B. tiefenbegrenzte Suchvorgänge wie die iterative vertiefende Tiefensuche. Letzteres sowie die Breitensuche können auch zum Durchqueren unendlicher Bäume verwendet werden (siehe unten).

Datenstrukturen für die Baumdurchquerung[edit]

Beim Durchlaufen eines Baums werden auf irgendeine Weise alle Knoten durchlaufen. Da von einem bestimmten Knoten mehr als ein möglicher nächster Knoten vorhanden ist (es handelt sich nicht um eine lineare Datenstruktur), müssen unter der Annahme einer sequentiellen Berechnung (nicht parallel) einige Knoten zurückgestellt und für einen späteren Besuch auf irgendeine Weise gespeichert werden. Dies erfolgt häufig über einen Stapel (LIFO) oder eine Warteschlange (FIFO). Da ein Baum eine selbstreferenzielle (rekursiv definierte) Datenstruktur ist, kann die Durchquerung durch Rekursion oder subtiler durch Corecursion auf sehr natürliche und klare Weise definiert werden. In diesen Fällen werden die zurückgestellten Knoten implizit im Aufrufstapel gespeichert.

after-content-x4

Die Tiefensuche kann leicht über einen Stapel implementiert werden, einschließlich rekursiv (über den Aufrufstapel), während die Breitensuche leicht über eine Warteschlange implementiert wird, einschließlich Kernkurs.

Tiefendurchquerung eines Beispielbaums: Vorbestellung (rot): F, B, A, D, C, E, G, I, H; in der Reihenfolge (gelb): A, B, C, D, E, F, G, H, I; Nachbestellung (grün): A, C, E, D, B, H, I, G, F.

Tiefensuche des Binärbaums[edit]

Diese Suchen werden als bezeichnet Tiefensuche (DFS), da der Suchbaum bei jedem Kind so weit wie möglich vertieft wird, bevor zum nächsten Geschwister übergegangen wird. Für einen Binärbaum werden sie als Zugriffsoperationen an jedem Knoten definiert, beginnend mit dem aktuellen Knoten, dessen Algorithmus wie folgt lautet:[2][3]

Das allgemeine rekursive Muster zum Durchlaufen eines Binärbaums lautet wie folgt:

Gehen Sie eine Ebene nach unten zum rekursiven Argument N.. Wenn N. existiert (ist nicht leer) Führen Sie die folgenden drei Operationen in einer bestimmten Reihenfolge aus:
(L) Rekursiv durchqueren N.linker Teilbaum.
(R) Rekursiv durchqueren N.ist der richtige Teilbaum.
(N) Verarbeiten Sie den aktuellen Knoten N. selbst.
Kehren Sie zurück, indem Sie eine Ebene höher gehen und den übergeordneten Knoten von erreichen N..

In den Beispielen wird (L) meistens vor (R) durchgeführt. Aber (R) vor (L) ist auch möglich, siehe (RNL).

Vorbestellung (NLR)[edit]

  1. Greifen Sie auf den Datenteil des aktuellen Knotens zu.
  2. Durchlaufen Sie den linken Teilbaum, indem Sie die Vorbestellungsfunktion rekursiv aufrufen.
  3. Durchlaufen Sie den rechten Teilbaum, indem Sie die Vorbestellungsfunktion rekursiv aufrufen.
Die Durchquerung vor der Bestellung ist topologisch sortiert, da ein übergeordneter Knoten verarbeitet wird, bevor einer seiner untergeordneten Knoten ausgeführt wird.

In-order (LNR)[edit]

  1. Durchlaufen Sie den linken Teilbaum, indem Sie die Funktion in der Reihenfolge rekursiv aufrufen.
  2. Greifen Sie auf den Datenteil des aktuellen Knotens zu.
  3. Durchlaufen Sie den rechten Teilbaum, indem Sie die Funktion in der Reihenfolge rekursiv aufrufen.
In einem binären Suchbaum, der so angeordnet ist, dass in jedem Knoten der Schlüssel größer als alle Schlüssel in seinem linken Teilbaum und kleiner als alle Schlüssel in seinem rechten Teilbaum ist, werden die Schlüssel in der Reihenfolge des Durchlaufs abgerufen aufsteigend sortierte Reihenfolge.[4]

In umgekehrter Reihenfolge umkehren (RNL)[edit]

  1. Durchlaufen Sie den rechten Teilbaum, indem Sie die Funktion “In umgekehrter Reihenfolge” rekursiv aufrufen.
  2. Greifen Sie auf den Datenteil des aktuellen Knotens zu.
  3. Durchlaufen Sie den linken Teilbaum, indem Sie die Funktion für die umgekehrte Reihenfolge rekursiv aufrufen.
In einem binären Suchbaum werden die Schlüssel in umgekehrter Reihenfolge abgerufen absteigend sortierte Reihenfolge.

Nachbestellung (LRN)[edit]

  1. Durchlaufen Sie den linken Teilbaum, indem Sie die Nachbestellfunktion rekursiv aufrufen.
  2. Durchlaufen Sie den rechten Teilbaum, indem Sie die Nachbestellfunktion rekursiv aufrufen.
  3. Greifen Sie auf den Datenteil des aktuellen Knotens zu.

Die Spur einer Durchquerung wird als Sequentialisierung des Baumes bezeichnet. Die Traversal-Trace ist eine Liste jeder besuchten Wurzel. Keine Sequenzierung nach Vor-, In- oder Post-Order beschreibt den zugrunde liegenden Baum eindeutig. Bei einem Baum mit unterschiedlichen Elementen reicht eine Vor- oder Nachbestellung in Kombination mit einer Reihenfolge aus, um den Baum eindeutig zu beschreiben. Die Vorbestellung mit der Nachbestellung führt jedoch zu Unklarheiten in der Baumstruktur.[5]

Generischer Baum[edit]

Führen Sie die folgenden Operationen an jedem Knoten rekursiv aus, um einen Baum mit Tiefensuche zu durchlaufen.

  1. Vorbestellungsvorgang durchführen.
  2. Für jeden ich von 1 bis zur Anzahl der Kinder:
    1. Besuch ich-th, falls vorhanden.
    2. Führen Sie den ordnungsgemäßen Betrieb durch.
  3. Nachbestellungsvorgang durchführen.

Abhängig vom jeweiligen Problem sind die Vorbestellungs-, In-Order- oder Nachbestellungsvorgänge möglicherweise ungültig, oder Sie möchten möglicherweise nur ein bestimmtes untergeordnetes Element besuchen. Daher sind diese Vorgänge optional. In der Praxis kann auch mehr als eine Vorbestellungs-, In-Order- und Nachbestellungsoperation erforderlich sein. Wenn Sie beispielsweise in einen ternären Baum einfügen, wird eine Vorbestellungsoperation ausgeführt, indem Elemente verglichen werden. Möglicherweise ist anschließend eine Nachbestellungsoperation erforderlich, um den Baum neu auszugleichen.

after-content-x4

Breitensuche / Ebenenreihenfolge[edit]

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

Bäume können auch durchquert werden Level-Reihenfolge, wo wir jeden Knoten auf einer Ebene besuchen, bevor wir zu einer niedrigeren Ebene gehen. Diese Suche wird als bezeichnet Breitensuche (BFS), da der Suchbaum in jeder Tiefe so weit wie möglich erweitert wird, bevor zur nächsten Tiefe gewechselt wird.

Andere Arten[edit]

Es gibt auch Tree-Traversal-Algorithmen, die weder als Tiefensuche noch als Breitensuche klassifiziert werden. Ein solcher Algorithmus ist die Monte-Carlo-Baumsuche, die sich auf die Analyse der vielversprechendsten Bewegungen konzentriert und die Erweiterung des Suchbaums auf zufälligen Stichproben des Suchraums basiert.

Anwendungen[edit]

Baum, der den arithmetischen Ausdruck darstellt EIN * (B. – – C.) + (D. + E.)

Das Durchlaufen der Vorbestellung kann verwendet werden, um einen Präfixausdruck (polnische Notation) aus Ausdrucksbäumen zu erstellen: Durchlaufen Sie den Ausdrucksbaum vorab. Wenn Sie beispielsweise den dargestellten arithmetischen Ausdruck in Vorbestellung durchlaufen, erhalten Sie “+ * EIN – – B. C. + D. E.“.

Nachbestellungsdurchlauf kann eine Postfix-Darstellung (umgekehrte polnische Notation) eines Binärbaums erzeugen. Durchlaufen des dargestellten arithmetischen Ausdrucks in Nachbestellungserträgen “EIN B. C. – * D. E. + + “; letzteres kann leicht in Maschinencode umgewandelt werden, um den Ausdruck von einer Stapelmaschine auszuwerten.

In-Order-Traversal wird sehr häufig für binäre Suchbäume verwendet, da es Werte aus der zugrunde liegenden Menge in der angegebenen Reihenfolge zurückgibt, gemäß dem Komparator, der den binären Suchbaum eingerichtet hat.

Durch die Nachbestellung beim Löschen oder Freigeben von Knoten und Werten kann ein ganzer Binärbaum gelöscht oder freigegeben werden. Dadurch wird der Knoten freigegeben, nachdem seine untergeordneten Knoten freigegeben wurden.

Auch das Duplizieren eines Binärbaums ergibt eine Folge von Aktionen nach der Reihenfolge, weil der Zeiger Kopieren der Kopie eines Knotens wird das entsprechende untergeordnete Feld zugeordnet N.child innerhalb der Kopie des Elternteils N. gleich nach returnKopieren in der rekursiven Prozedur. Dies bedeutet, dass der Elternteil nicht fertig sein kann, bevor nicht alle Kinder fertig sind.

Implementierungen[edit]

Tiefensuche[edit]

Vorbestellung[edit]

preorder(node)
    if (node == null)
        return
    visit(node)
    preorder(node.left)
    preorder(node.right)

iterativePreorder(node)
  if (node == null)
    return
  s ← empty stack
  s.push(node)
  while (not s.isEmpty())
    node ← s.pop()
    visit(node)
    //right child is pushed first so that left is processed first
    if node.right ≠ null
      s.push(node.right)
    if node.left ≠ null
      s.push(node.left)

In Ordnung[edit]

inorder(node)
    if (node == null)
        return
    inorder(node.left)
    visit(node)
    inorder(node.right)

iterativeInorder(node)
  s ← empty stack
  while (not s.isEmpty() or node ≠ null)
    if (node ≠ null)
      s.push(node)
      node ← node.left
    else
      node ← s.pop()
      visit(node)
      node ← node.right

Nachbestellung[edit]

postorder(node)
    if (node == null)
        return
    postorder(node.left)
    postorder(node.right)
    visit(node)

iterativePostorder(node)
  s ← empty stack
  lastNodeVisited ← null
  while (not s.isEmpty() or node ≠ null)
    if (node ≠ null)
      s.push(node)
      node ← node.left
    else
      peekNode ← s.peek()
      // if right child exists and traversing node
      // from left child, then move right
      if (peekNode.right ≠ null and lastNodeVisited ≠ peekNode.right)
        node ← peekNode.right
      else
        visit(peekNode)
        lastNodeVisited ← s.pop()

Alle obigen Implementierungen erfordern einen Stapelplatz proportional zur Höhe des Baums, der ein Aufrufstapel für die rekursiven und ein übergeordneter Stapel für die iterativen ist. Bei einem schlecht ausbalancierten Baum kann dies erheblich sein. Mit den iterativen Implementierungen können wir die Stapelanforderung entfernen, indem wir übergeordnete Zeiger in jedem Knoten beibehalten oder den Baum einfädeln (nächster Abschnitt).

Morris In-Order-Traversal mit Threading[edit]

Ein Binärbaum wird eingefädelt, indem jeder linke untergeordnete Zeiger (der sonst null wäre) auf den Vorgänger in der Reihenfolge des Knotens zeigt (falls vorhanden) und jeder rechte untergeordnete Zeiger (der sonst null wäre) auf den in zeigt Auftragsnachfolger des Knotens (falls vorhanden).

Vorteile:

  1. Vermeidet Rekursion, die einen Aufrufstapel verwendet und Speicher und Zeit verbraucht.
  2. Der Knoten zeichnet sein übergeordnetes Element auf.

Nachteile:

  1. Der Baum ist komplexer.
  2. Wir können jeweils nur eine Durchquerung durchführen.
  3. Es ist anfälliger für Fehler, wenn beide untergeordneten Elemente nicht vorhanden sind und beide Knotenwerte auf ihre Vorfahren verweisen.

Morris Traversal ist eine Implementierung von In-Order-Traversal, die Threading verwendet:[6]

  1. Erstellen Sie Links zum Nachfolger in der Reihenfolge.
  2. Drucken Sie die Daten über diese Links.
  3. Setzen Sie die Änderungen zurück, um den ursprünglichen Baum wiederherzustellen.

Breitensuche[edit]

Im Folgenden ist der Pseudocode für eine einfache Warteschlangen-basierte Durchquerung der Ebenenreihenfolge aufgeführt und erfordert Speicherplatz proportional zur maximalen Anzahl von Knoten in einer bestimmten Tiefe. Dies kann so viel sein wie die Gesamtzahl der Knoten / 2. Ein platzsparenderer Ansatz für diese Art der Durchquerung kann mithilfe einer iterativen vertiefenden Tiefensuche implementiert werden. 

levelorder(root)
    q ← empty queue
    q.enqueue(root)
    while not q.isEmpty() do
        node ← q.dequeue()
        visit(node)
        if node.left ≠ null then
            q.enqueue(node.left)
        if node.right ≠ null then
            q.enqueue(node.right)

Unendliche Bäume[edit]

Während das Durchqueren normalerweise für Bäume mit einer endlichen Anzahl von Knoten (und damit endlicher Tiefe und endlichem Verzweigungsfaktor) durchgeführt wird, kann es auch für unendliche Bäume durchgeführt werden. Dies ist von besonderem Interesse für die funktionale Programmierung (insbesondere bei verzögerter Auswertung), da unendliche Datenstrukturen häufig leicht definiert und bearbeitet werden können, obwohl sie nicht (streng) ausgewertet werden, da dies unendlich lange dauern würde. Einige endliche Bäume sind zu groß, um explizit dargestellt zu werden, z. B. der Spielbaum für Schach oder Go. Daher ist es nützlich, sie so zu analysieren, als wären sie unendlich.

Eine Grundvoraussetzung für das Durchlaufen ist es, jeden Knoten irgendwann zu besuchen. Bei unendlichen Bäumen scheitern einfache Algorithmen häufig daran. Wenn beispielsweise ein binärer Baum mit unendlicher Tiefe gegeben ist, wird eine Tiefensuche eine Seite (gemäß Konvention die linke Seite) des Baums hinuntergehen und niemals den Rest besuchen, und tatsächlich wird eine Durchquerung in der Reihenfolge oder nach der Reihenfolge niemals stattfinden Besuch irgendein Knoten, da es kein Blatt erreicht hat (und in der Tat nie wird). Im Gegensatz dazu durchläuft eine Durchquerung der Breite zuerst (Ebenenordnung) problemlos einen Binärbaum mit unendlicher Tiefe und tatsächlich jeden Baum mit begrenztem Verzweigungsfaktor.

Bei einem Baum der Tiefe 2, in dem die Wurzel unendlich viele Kinder hat und jedes dieser Kinder zwei Kinder hat, werden bei einer Tiefensuche alle Knoten besucht, sobald die Enkelkinder (Kinder von Kindern von ein Knoten), geht es weiter zum nächsten (vorausgesetzt, es ist keine Nachbestellung, in diesem Fall erreicht es nie die Wurzel). Im Gegensatz dazu wird eine Breitensuche niemals die Enkelkinder erreichen, da sie versucht, die Kinder zuerst zu erschöpfen.

Eine differenziertere Analyse der Laufzeit kann über unendliche Ordnungszahlen erfolgen. Zum Beispiel wird die Breitensuche des obigen Baums der Tiefe 2 ω · 2 Schritte dauern: ω für die erste Ebene und dann ein weiteres ω für die zweite Ebene.

Einfache Tiefensuchen oder Breitensuchen durchlaufen daher nicht jeden unendlichen Baum und sind bei sehr großen Bäumen nicht effizient. Hybridmethoden können jedoch jeden (zählbar) unendlichen Baum durchlaufen, im Wesentlichen über ein diagonales Argument (“Diagonale” – eine Kombination aus vertikal und horizontal – entspricht einer Kombination aus Tiefe und Breite).

Konkret bezeichnen Sie angesichts des unendlich verzweigten Baumes von unendlicher Tiefe die Wurzel (), die Kinder der Wurzel (1), (2),…, die Enkelkinder (1, 1), (1, 2),…, (2 , 1), (2, 2), … und so weiter. Die Knoten befinden sich somit in einer Eins-zu-Eins-Entsprechung mit endlichen (möglicherweise leeren) Folgen positiver Zahlen, die zählbar sind und zuerst durch die Summe der Einträge und dann durch lexikografische Reihenfolge innerhalb einer gegebenen Summe (nur endlich) geordnet werden können Viele Sequenzen summieren sich zu einem bestimmten Wert, so dass alle Einträge erreicht sind – formal gibt es eine endliche Anzahl von Kompositionen einer bestimmten natürlichen Zahl, insbesondere 2n−1 Kompositionen von n ≥ 1), was eine Durchquerung ergibt. Ausdrücklich: 

0: ()
1: (1)
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.

Dies kann so interpretiert werden, dass der Binärbaum mit unendlicher Tiefe auf diesen Baum abgebildet und dann die Breitensuche angewendet wird: Ersetzen Sie die “Abwärts” -Kanten, die einen übergeordneten Knoten mit seinem zweiten und späteren untergeordneten Knoten verbinden, durch “rechte” Kanten vom ersten zum zweiten untergeordneten Knoten Kind, vom zweiten Kind zum dritten Kind usw. Somit kann man bei jedem Schritt entweder nach unten gehen (ein (, 1) an das Ende anhängen) oder nach rechts gehen (eins zur letzten Zahl hinzufügen) (mit Ausnahme der Wurzel, die ist extra und kann nur runter gehen), was die Entsprechung zwischen dem unendlichen Binärbaum und der obigen Nummerierung zeigt; Die Summe der Einträge (minus eins) entspricht dem Abstand von der Wurzel, der mit der 2 übereinstimmtn−1 Knoten in der Tiefe n – 1 im unendlichen Binärbaum (2 entspricht binär).

Verweise[edit]

Allgemeines
  • Dale, Nell. Lilly, Susan D. “Pascal Plus Datenstrukturen”. DC Heath and Company. Lexington, MA. 1995. Vierte Ausgabe.
  • Drozdek, Adam. “Datenstrukturen und Algorithmen in C ++”. Brook / Cole. Pacific Grove, CA. 2001. Zweite Auflage.
  • [2]

Externe Links[edit]

after-content-x4