Baumstruktur

Ein Baum ist einenicht-lineareDatenstruktur, die die verzweigte Hierarchie von Bäumen in der Natur simuliert. Im Gegensatz zu linearen Strukturen wie Arrays und verketteten Listen, bei denen die Elemente nacheinander angeordnet sind, gibt es unter den Datenelementen in einem Baum (genanntKnoten) eine klare hierarchische Eins-zu-viele-Beziehung zwischen ihnen.

BaumstrukturGenau wie ein echter Baum:

  • Wurzelknoten: der Wurzelteil des Baums, der einzige Knoten ohne Elternknoten
  • Kindknoten: Knoten, die von einem Knoten abzweigen
  • Blattknoten: ein Knoten ohne Kinder, wie ein Blatt
  • Pfad: der Weg von einem Knoten zu einem anderen Knoten
  • Tiefe: die Pfadlänge vom Wurzelknoten zu diesem Knoten
  • Höhe: die Pfadlänge von diesem Knoten zum am weitesten entfernten Blattknoten

Lebensanalogie:

  • Stammbaum: Großeltern → Eltern → Kinder → Enkelkinder
  • Organisationsstruktur: CEO → Direktor → Manager → Mitarbeiter
  • Dateisystem: Wurzelverzeichnis → Unterverzeichnis → Datei
  • Buchklassifikation: allgemeine Kategorie → Unterkategorie → spezifisches Buch
Strukturtyp Sucheffizienz Einfügeeffizienz Löscheffizienz Reihenfolge
array O(n) O(n) O(n) Keine
Verkettete Liste O(n) O(1) O(1) Keine
Hash-Tabelle O(1) O(1) O(1) Keine
Binärer Suchbaum O(log n) O(log n) O(log n) Ja

Grundbegriffe

Bevor wir tiefer eingehen, machen wir uns zunächst mit der grundlegenden Terminologie von Bäumen vertraut:

  • Knoten: jedes Element in einem Baum. Er enthält die gespeicherten Daten und Verweise auf seine Kindknoten.
  • Wurzelknoten: der Knoten an der Spitze des Baums, der Ausgangspunkt des gesamten Baums. Ein Baum hat genau einen Wurzelknoten.
  • Elternknoten und Kindknoten (Eltern & Kind): Wenn ein Knoten A mit einem Knoten B unter ihm verbunden ist, dann ist A derElternknotenvon B, B ist derKindknotenvon A. Ein Elternknoten kann mehrere Kindknoten haben.
  • Geschwisterknoten (Geschwister): Knoten, die denselben Elternknoten teilen, sind Geschwister.
  • Blattknoten (Blatt): ein Knoten ohne Kindknoten, auch Endknoten genannt.
  • Kante: die Linie, die zwei Knoten verbindet und die Beziehung zwischen ihnen darstellt.
  • Pfad: die Abfolge von Knoten, die vom Wurzelknoten zu einem bestimmten Knoten durchlaufen werden.
  • Höhe: auf dem längsten Pfad von einem Knoten zu seinem am weitesten entfernten BlattknotenAnzahl der Kanten. Die Höhe des Baums ist die Höhe des Wurzelknotens.
  • Tiefe: auf dem Pfad vom Wurzelknoten zu einem bestimmten KnotenAnzahl der Kanten. Die Tiefe des Wurzelknotens ist 0.
  • Ebene: Alle Knoten mit derselben Tiefe gehören zur selben Ebene. Der Wurzelknoten befindet sich auf Ebene 0.

Grundlegende Eigenschaften von Bäumen

  1. eindeutiger Pfad: Zwischen zwei beliebigen Knoten in einem Baum gibt es genau einen Pfad.
  2. N Knoten, N-1 Kanten: Ein Baum mit N Knoten hat insgesamt N-1 Kanten.
  3. azyklisch: In einem Baum gibt es keine Zyklen (d. h., wenn man von einem Knoten startet und den Kanten folgt, kann man nicht zu diesem Knoten zurückkehren).

Warum brauchen wir Bäume? — Vorteile und Anwendungen von Bäumen

Vielleicht fragen Sie sich: Wo wir doch Arrays und verkettete Listen haben, warum brauchen wir noch Bäume? Die Antwort liegt in der Effizienz.

  • Array: schnelles Nachschlagen (über Index), aber langsames Einfügen und Löschen (erfordert das Verschieben vieler Elemente).
  • Verkettete Liste: schnelles Einfügen und Löschen, aber langsames Nachschlagen (erfordert das Durchlaufen vom Anfang).
  • Bäume (insbesondere binäre Suchbäume): Während sie Daten geordnet halten, können sie eine viel schnellere Suchgeschwindigkeit als verkettete Listen und effizientere Einfüge-/Löschoperationen als Arrays bieten.

Praktische Anwendungsszenarien:

  • Dateisystem: Ordner und Dateien in Computern sind in Form eines Baumes organisiert.
  • Datenbankindex: B-Baum und B+-Baum sind Kern-Datenstrukturen für effiziente Abfragen in Datenbanken.
  • Organigramm: die hierarchische Verwaltung eines Unternehmens oder einer Abteilung.
  • Entscheidungsbaum: Klassifikationsmodelle in der künstlichen Intelligenz und im maschinellen Lernen.
  • HTML DOM: das Document Object Model einer Webseite ist ein Baum.

Binärbaum: das wichtigste Mitglied der Baumfamilie

Ein Binärbaum ist ein Baum, in dem jeder Knoten höchstens zwei Kindknoten hat. Diese beiden Kindknoten heißen üblicherweiselinker Kindknotenundrechter Kindknoten, er ist die Grundlage vieler leistungsfähiger Baumstrukturen (wie binäre Suchbäume, Heaps und AVL-Bäume).

Die Grundstruktur ist wie folgt:

Grundbegriffe für Binärbäume

Begriff Definition Alltagsanalogie
Knoten die Grundeinheit, die Daten und Zeiger enthält Eine Person in der Familie
Wurzelknoten Der oberste Knoten eines Baums Ein Vorfahre in der Familie
Elternknoten Ein Knoten mit Kindknoten Elternknoten
Kindknoten der Knoten, auf den sein Elternknoten zeigt children
Geschwisterknoten Kindknoten desselben Elternknotens Geschwisterknoten
Blattknoten ein Knoten ohne Kinder eine Person in der Familie ohne Kinder
depth die Anzahl der Kanten von der Wurzel zu diesem Knoten Anzahl der Generationen
height die Anzahl der Kanten von diesem Knoten zum am weitesten entfernten Blattknoten die Anzahl der Generationen, über die sich die Familie fortsetzt

Binärbaumtyp

Type Funktionen Zeitkomplexität Anwendungsszenarien
gewöhnlicher Binärbaum jeder Knoten hat höchstens 2 Kindknoten O(n) Ausdrucksbaum
vollständiger Binärbaum jeder Knoten hat entweder 0 oder 2 Kindknoten O(n) Huffman-Kodierung
vollständiger Binärbaum alle Ebenen außer der letzten sind voll O(n) Heap-Implementierung
Binärer Suchbaum links < Wurzel < rechts Durchschnittlich O(log n) Suchen, Sortieren
balancierter Binärbaum Der Höhenunterschied zwischen dem linken und dem rechten Teilbaum ist ≤ 1 O(log n) Datenbankindex
Rot-Schwarz-Baum Farbiger balancierter Baum O(log n) Linux-Kernel

Operationen auf binären Suchbäumen

Aktion Beschreibung Zeitkomplexität
Suche Knoten nach Wert suchen durchschnittlich O(log n), im schlechtesten Fall O(n)
Einfügen neuen Knoten einfügen durchschnittlich O(log n), im schlechtesten Fall O(n)
Delete Angegebenen Knoten löschen durchschnittlich O(log n), im schlechtesten Fall O(n)
Traversierung Alle Knoten besuchen O(n)

Traversierung eines Binärbaums

Traversierung bedeutet, jeden Knoten im Baum nach einer bestimmten Regel zu besuchen, wobei jeder Knoten nur einmal besucht wird. Dies ist die Grundlage baumbezogener Algorithmen. Es gibt hauptsächlich vier Möglichkeiten:

  1. Preorder-Traversierung:Wurzel -> Links -> Rechts

    • Zuerst wird der Wurzelknoten besucht, dann wird der linke Teilbaum rekursiv in Preorder-Reihenfolge durchlaufen und schließlich der rechte Teilbaum rekursiv in Preorder-Reihenfolge durchlaufen.
    • Anwendung: Einen Baum kopieren, Präfixausdruck erhalten.
  2. In-order-Traversierung:Links -> Wurzel -> Rechts

    • Zuerst rekursiv den linken Teilbaum inorder durchlaufen, dann den Wurzelknoten besuchen und schließlich rekursiv den rechten Teilbaum inorder durchlaufen.
    • Anwendung: inbinärem SuchbaumUnter ihnen wird die In-order-Traversierungaufsteigende ReihenfolgeOutput all values.
  3. Post-order-Traversierung:Links -> Rechts -> Wurzel

    • Zuerst rekursiv den linken Teilbaum postorder durchlaufen, dann rekursiv den rechten Teilbaum postorder durchlaufen und schließlich den Wurzelknoten besuchen.
    • Anwendung: Einen Baum löschen, Verzeichnisgröße berechnen.
  4. Level-order-Traversierung:Ebene für Ebene, von links nach rechts

    • Ausgehend vom Wurzelknoten werden Knoten Ebene für Ebene besucht.
    • Anwendung: Daten ebenenweise verarbeiten (z. B. Drucken eines Organigramms).Sie wird üblicherweise mithilfe einer Warteschlange (Queue) implementiert.。

Beispiel: Für den untenstehenden Baum sind die Traversierungsergebnisse wie folgt:

        1
       / \
      2   3
     / \   \
    4   5   6
  • Preorder:1, 2, 4, 5, 3, 6
  • Inorder:4, 2, 5, 1, 3, 6
  • Postorder:4, 5, 2, 6, 3, 1
  • Ebenenreihenfolge:1, 2, 3, 4, 5, 6

Übung: Implementiere einen Binärbaum in Python

Genug der Theorie, lass uns etwas Code schreiben! Wir werden eine einfache Knotenklasse für Binärbäume implementieren und Einfüge- und Traversierungsoperationen vervollständigen.

Schritt 1: Definiere die Knotenklasse

Jeder Knoten muss Daten speichern und auf seinen linken und rechten Kindknoten verweisen.

Beispiel

class TreeNode:
    """Binärbaum-Knotenklasse"""
    def __init__(self, value):
        self.value = value  # Im Knoten gespeicherte Daten
        self.left = None    # Zeigt auf den linken Kindknoten
        self.right = None   # Zeigt auf den rechten Kindknoten

    def __str__(self):
        """Praktisch zum Ausgeben von Knoteninformationen"""
        return f"Node({self.value})"

Schritt 2: Einen Beispielbaum erstellen

Lass uns den Baum manuell anhand des vorherigen Beispieldiagramms aufbauen.

Beispiel

# Knoten erstellen
root = TreeNode(1)
node2 = TreeNode(2)
node3 = TreeNode(3)
node4 = TreeNode(4)
node5 = TreeNode(5)
node6 = TreeNode(6)

# Verbindungen aufbauen (Verknüpfungen)
root.left = node2
root.right = node3
node2.left = node4
node2.right = node5
node3.right = node6

print(f"Wurzelknoten: {root}")
print(f"Linkes Kind des Wurzelknotens: {root.left}")
print(f"Rechtes Kind des Wurzelknotens: {root.right}")

Schritt 3: Traversierungsalgorithmen implementieren (rekursive Version)

Rekursion ist der intuitivste Weg, Baumtraversierung zu implementieren.

Beispiel

def preorder_traversal(node):
    """Preorder-Traversierung: Wurzel -> links -> rechts"""
    if node is None:
        return
    print(node.value, end=' ')  # 1. Wurzelknoten besuchen
    preorder_traversal(node.left)   # 2. Linken Teilbaum durchlaufen
    preorder_traversal(node.right)  # 3. Rechten Teilbaum durchlaufen

def inorder_traversal(node):
    """Inorder-Traversierung: links -> Wurzel -> rechts"""
    if node is None:
        return
    inorder_traversal(node.left)    # 1. Linken Teilbaum durchlaufen
    print(node.value, end=' ')  # 2. Wurzelknoten besuchen
    inorder_traversal(node.right)   # 3. Rechten Teilbaum durchlaufen

def postorder_traversal(node):
    """Postorder-Traversierung: links -> rechts -> Wurzel"""
    if node is None:
        return
    postorder_traversal(node.left)  # 1. Linken Teilbaum durchlaufen
    postorder_traversal(node.right) # 2. Rechten Teilbaum durchlaufen
    print(node.value, end=' ')  # 3. Wurzelknoten besuchen

print("\n--- Traversierungsdemo ---")
print("Ergebnis der Preorder-Traversierung:", end=' ')
preorder_traversal(root) # Ausgabe: 1 2 4 5 3 6

print("\nErgebnis der Inorder-Traversierung:", end=' ')
inorder_traversal(root)  # Ausgabe: 4 2 5 1 3 6

print("\nErgebnis der Postorder-Traversierung:", end=' ')
postorder_traversal(root) # Ausgabe: 4 5 2 6 3 1

Schritt 4: Level-Order-Traversierung implementieren (mithilfe einer Warteschlange)

Die Level-Order-Traversierung muss die "First-In-First-Out"-Eigenschaft einer Warteschlange nutzen.

Beispiel

from collections import deque

def level_order_traversal(root):
    """Levelorder-Traversierung: Verwenden einer Warteschlange"""
    if root is None:
        return

    queue = deque([root]) # Warteschlange initialisieren und Wurzelknoten einreihen

    while queue:
        current_node = queue.popleft() # 1. Knoten von links aus der Warteschlange entnehmen
        print(current_node.value, end=' ') # 2. Diesen Knoten besuchen

        # 3. Die Kindknoten dieses Knotens (falls vorhanden) der Reihe nach rechts an die Warteschlange anhängen
        if current_node.left:
            queue.append(current_node.left)
        if current_node.right:
            queue.append(current_node.right)

print("\nErgebnis der Levelorder-Traversierung:", end=' ')
level_order_traversal(root) # Output: 1 2 3 4 5 6

Übung und Herausforderung

Herzlichen Glückwunsch zum Abschluss der Grundlagen! Um Bäume wirklich zu beherrschen, ist praktische Übung unerlässlich.

Übung 1: Berechne die Höhe des Baums

Eine Funktion schreibentree_height(node), nimmt den Wurzelknoten eines Baums und gibt die Höhe des Baums zurück (die Höhe eines leeren Baums ist per Konvention -1 oder 0; in diesem Beispiel definieren wir sie als die Anzahl der Kanten).

Hinweis: Baumhöhe = 1 + max(Höhe des linken Teilbaums, Höhe des rechten Teilbaums). Dies ist ein klassisches rekursives Problem.

Übung 2: Suche nach einem Wert in einem Binärbaum

Eine Funktion schreibensearch_in_tree(node, target_value), suche in dem gegebenen Binärbaum nach einem Wert gleichtarget_valuedem Knoten. Wenn gefunden, gib zurückTrue, andernfalls zurückgebenFalse。

Hinweis: Jede Traversierungsmethode kann verwendet werden, und vergleiche den Wert jedes Knotens beim Besuch.

Herausforderung: Binärer Suchbaum (BST)

Dies ist eine klassische Variante des Binärbaums. In einem binären Suchbaum gilt für jeden Knoten:

  • seinemlinken Teilbaumdie Werte aller Knoten in<Der Wert dieses Knotens.
  • seinemrechten Teilbaumdie Werte aller Knoten in>Der Wert dieses Knotens.

Deine Herausforderung ist:

  1. Implementierunginsert_into_bst(root, value)Funktion, füge einen Wert an der richtigen Position in den binären Suchbaum ein.
  2. Implementierungsearch_in_bst(root, value)Funktion, die die Eigenschaften des BST für eine effiziente Suche nutzt (durchschnittliche Zeitkomplexität O(log N)).
Weitere Erweiterungen