Fortgeschrittene Baumstrukturen

Nachdem wir grundlegende Baumstrukturen wie Binärbäume und binäre Suchbäume beherrschen, stehen wir kurz davor, in ein breiteres und effizienteres Gebiet einzutreten – fortgeschrittene Baumstrukturen.

Wenn grundlegende Bäume die gewöhnlichen Straßen in der Welt der Datenstrukturen sind, dann sind fortgeschrittene Baumstrukturen sorgfältig entworfene Schnellstraßen und Autobahnkreuze. Durch geniale Balance-Regeln und Speicherstrategien gewährleisten sie eine hervorragende Leistung, selbst wenn die Datenmengen riesig oder die Operationen häufig sind.

In diesem Abschnitt werdenAVL-Baum、Rot-Schwarz-Baum、B-BaumundB+-Baum vorgestelltDiese vier klassischen fortgeschrittenen Baumstrukturen.

Warum brauchen wir fortgeschrittene Baumstrukturen?

Bevor wir tiefer eintauchen, stellen wir zunächst eine Frage: Wenn wir bereits einen effizienten binären Suchbaum (BST) zur Hand haben, warum brauchen wir dann noch komplexere Bäume?

Stellen Sie sich vor, Sie haben eine Bibliothek und verwenden einen BST, um nach Titel sortierte Bücher zu speichern. Wenn Sie Bücher nacheinander in alphabetischer Reihenfolge einfügen (zum Beispiel:A..., B..., C...), entartet der Baum zu einer Kette (ähnlich einer verketteten Liste). Zu diesem Zeitpunkt ändert sich die Zeit, um ein Buch zu finden, von der idealenO(log n)Verschlechterung im schlimmsten FallO(n), extrem niedrige Effizienz.

Abbildung: ein schematisches Diagramm eines binären Suchbaums, der beim Einfügen geordneter Daten zu einer verketteten Liste entartet, wodurch die Suchleistung abnimmt.

Fortgeschrittene Baumstrukturen (selbstbalancierende Bäume) entstanden genau, um dieses Problem zu lösen.. Sie passen die Form des Baums beim Einfügen oder Löschen von Knoten automatisch an, halten den Baum im Gleichgewicht und gewährleisten dadurch, dass die Zeitkomplexität von Operationen wie Suchen, Einfügen und Löschen stets auf demO(log n)Niveau.

AVL-Baum: Der Wächter der Höhenbalance

Der AVL-Baum ist der früheste je erfundene selbstbalancierende binäre Suchbaum; er ist nach seinen Erfindern Adelson-Velsky und Landis benannt.

Die Kernidee des AVL-Baums ist sehr einfach:Für jeden Knoten im Baum darf der Höhenunterschied zwischen seinem linken und rechten Teilbaum nicht größer als 1 sein.。

Kernkonzept: Balance-Faktor

Jeder Knoten hat einenBalance-Faktor, und seine Berechnungsformel lautet:Balance factor = height of left subtree - height of right subtreeIn einem AVL-Baum kann der Balance-Faktor jedes Knotens nur -1, 0 oder 1 sein.

Ungleichgewicht und Rotationsanpassung

Nach dem Einfügen oder Löschen eines Knotens, wenn der Balance-Faktor eines Knotens 2 oder -2 wird, ist der Baum unausgeglichen. Um das Gleichgewicht wiederherzustellen, verwendet der AVL-Baum vierRotationsoperationen zur Anpassung:

  • Linksrotation: Behandelt den "rechts-rechts"-Ungleichgewichtsfall.
  • Rechtsrotation: Behandelt den "links-links"-Ungleichgewichtsfall.
  • Links-Rechts-Rotation: zuerst Linksrotation, dann Rechtsrotation, behandelt den "links-rechts"-Ungleichgewichtsfall.
  • Rechts-Links-Rotation: zuerst Rechtsrotation, dann Linksrotation, behandelt den "rechts-links"-Ungleichgewichtsfall.

Beispiel

class AVLNode:
    def __init__(self, key):
        self.key = key
        self.height = 1  # Knotenhöhe, anfangs 1
        self.left = None
        self.right = None

def get_height(node):
    """Knotenhöhe ermitteln (leere Knoten behandeln)"""
    return node.height if node else 0

def get_balance_factor(node):
    """Berechne den Balancefaktor eines Knotens"""
    if not node:
        return 0
    return get_height(node.left) - get_height(node.right)

def right_rotate(y):
    """
Führe eine Rechtsrotation am Teilbaum mit Wurzel y durch
         y                              x
        / \                          /   \
x T4 right rotate (y) z y
      / \      - - - - - - - ->    / \  / \
     z   T3                       T1  T2 T3 T4
    / \
  T1   T2
    """
    x = y.left
    T3 = x.right

    # Führe die Rotation durch
    x.right = y
    y.left = T3

    # Höhen aktualisieren (zuerst die Höhe von y aktualisieren, dann die Höhe von x)
    y.height = 1 + max(get_height(y.left), get_height(y.right))
    x.height = 1 + max(get_height(x.left), get_height(x.right))

    # Gib den neuen Wurzelknoten zurück
    return x

# Die Linksrotationsfunktion ist symmetrisch zur Rechtsrotation; die detaillierte Implementierung wird hier ausgelassen
def left_rotate(x):
    """Führe eine Linksrotation am Teilbaum mit Wurzel x durch (die Logik ist symmetrisch zur Rechtsrotation)"""
    pass

Zusammenfassung der Eigenschaften von AVL-Bäumen

Funktionen Beschreibung
Streng balanciert Die Balance-Bedingung ist streng (Höhenunterschied ≤ 1), die Baumhöhe liegt am nächsten bei log n und die Suchleistung ist hervorragend.
Häufige Anpassungen Nach Einfügen/Löschen können mehrere Rotationen von unten nach oben erforderlich sein, um das Gleichgewicht wiederherzustellen.
Anwendbare Szenarien Geeignet fürSzenarien mit mehr Abfragen, weniger Einfügungen/Löschungen, wie z. B. die mittlere Ebene von Datenbankindizes oder In-Memory-Lookup-Tabellen.

Rot-Schwarz-Baum: Der König der Ingenieurspraxis

Der Rot-Schwarz-Baum ist ein weiterer selbstbalancierender binärer Suchbaum. Er geht einige „Kompromisse“ auf Grundlage des AVL-Baums ein. Anstatt wie der AVL-Baum absolute Balance anzustreben, verwendet er eine Reihe lockererer Regeln, um annähernde Balance zu gewährleisten, wodurch die Anzahl der Rotationen beim Einfügen/Löschen reduziert und insgesamt bessere technische Ergebnisse bei der Gesamtleistung erzielt werden. JavasTreeMap、TreeSetund die von C++ STLmap、setAlle ihre zugrunde liegenden Implementierungen verwenden Rot-Schwarz-Bäume.

Die fünf Kernregeln von Rot-Schwarz-Bäumen

Rot-Schwarz-Bäume halten das Gleichgewicht aufrecht, indem sie Knoten ein Farbattribut (rot oder schwarz) hinzufügen und die folgenden Regeln befolgen:

  • Jeder Knoten ist entweder rot oder schwarz.
  • Der Wurzelknoten ist schwarz。
  • Alle Blattknoten (NIL-Leerknoten) sind schwarz.
  • Die beiden Kinder eines roten Knotens müssen schwarz sein.(d. h., es darf keine aufeinanderfolgenden roten Knoten geben).
  • Alle Pfade von jedem Knoten zu jedem seiner Blattknoten enthaltendieselbe Anzahlschwarzer Knoten.

Regeln 4 und 5 sind entscheidend für die Balance des Rot-Schwarz-Baums. Regel 5 stellt sicher, dass kein Pfad mehr als doppelt so lang ist wie ein anderer Pfad, wodurch eine annähernde Balance erreicht wird.

Einfüge-Anpassungsstrategie

Wenn wir einen neuen Knoten einfügen, färben wir ihn immer zuerstrot(um einen Verstoß gegen Regel 5 zu vermeiden). Wenn dadurch ein Konflikt entsteht (hauptsächlich ein Verstoß gegen Regel 2 oder Regel 4), muss er durchFarbänderungundRotation angepasst werdenanzupassen. Die Kernidee der Anpassung besteht darin, den Konflikt (rot) kontinuierlich zur Wurzel "nach oben zu verschieben", bis er durch Umfärben oder Rotation aufgelöst werden kann.

Beispiel

class RBNode:
    RED = "RED"
    BLACK = "BLACK"

    def __init__(self, key):
        self.key = key
        self.color = self.RED  # Neuer Knoten ist anfangs rot
        self.left = None
        self.right = None
        self.parent = None  # Der Rot-Schwarz-Baum benötigt einen Elternzeiger

def insert_fixup(tree, node):
    """Eigenschaften des Rot-Schwarz-Baums nach dem Einfügen reparieren (vereinfachte Beschreibung der Logik)"""
    while node.parent and node.parent.color == RBNode.RED:
        # Fall 1: Der Onkelknoten ist rot -> umfärben
        # Fälle 2 & 3: Der Onkelknoten ist schwarz -> durch Rotation und Umfärben gelöst
        # ... (Die tatsächliche Implementierung umfasst eine große Anzahl von Zeigeroperationen; hier folgt eine logische Beschreibung)
        pass
    tree.root.color = RBNode.BLACK  # Stelle sicher, dass der Wurzelknoten schwarz ist

Rot-Schwarz-Baum vs. AVL-Baum

Funktionen AVL-Baum Rot-Schwarz-Baum
Balancekriterium Strikt (Höhendifferenz ≤ 1) Locker (ungefähre Balance durch Farbregeln garantiert)
Suchleistung Besser(der Baum ist ausgewogener) Etwas geringer, aber immer noch O(log n)
Einfügen/Löschen Kannmehr Rotationen erfordern Weniger Rotationen,effizienter
Anwendbare Szenarien Szenarien mit häufigen Suchvorgängen Szenarien mit hohen Anforderungen an die Gesamtleistung, wie Standardbibliotheken von Programmiersprachen und Dateisysteme.

B-Baum und B+-Baum: Die Engine der Datenträgerspeicherung

Wenn Daten zu groß sind, um vollständig in den Speicher zu passen, müssen sie auf der Festplatte gespeichert werden. Die Geschwindigkeit von Festplatten-E/A (Lesen/Schreiben) ist viel langsamer als der Speicherzugriff. B-Bäume und B+-Bäume sind darauf ausgelegt,die Anzahl der Festplatten-E/A-Operationen zu reduzierenKonzipiert fürMehrweg-balancierter Suchbaum, und sie werden häufig in Datenbank- und Dateisystemindizes verwendet.

B-Baum: balancierter Mehrweg-Suchbaum

Bei einem B-Baum speichert nicht mehr jeder Knoten nur ein Datenelement und zwei Zeiger. EinB-Baum der Ordnung mEin Knoten hat die folgenden Eigenschaften:

  • Jeder Knoten hat höchstensm Kindknoten。
  • Jeder Nicht-Wurzel- und Nicht-Blatt-Knoten hat mindestens⌈m/2⌉ Kindknoten。
  • Der Wurzelknoten hat mindestens 2 Kindknoten (es sei denn, er ist selbst ein Blattknoten).
  • Alle Blattknoten befinden sich auf derselben Ebene.
  • Wenn ein Nicht-Blatt-Knoten k Kindknoten hat, enthält erk-1 Schlüssel, und diese Schlüssel partitionieren die Wertebereiche der Teilbäume.

Abbildung: Ein Strukturdiagramm eines B-Baum-Knotens der Ordnung 3. Er enthält zwei Schlüssel und drei Zeiger und teilt den Datenbereich in drei Intervalle auf.

Die Vorteile des B-Baumsliegen in seiner kurzen, breiten Baumform. Weil ein Knoten mehrere Schlüssel speichern und mehrere Kindknoten haben kann, wird die Baumhöhe stark reduziert. Bei der Suche nach einem Datenelement müssen weniger Festplattenseiten (Knoten) geladen werden, was die Effizienz verbessert.

B+-Baum: Die verbesserte Version des B-Baums

B+-Bäume bringen entscheidende Verbesserungen gegenüber B-Bäumen und sind derDe-facto-Standard。

Hauptunterschiede zwischen B+-Bäumen und B-Bäumen:

  1. Datenspeicherort: Im B+-Baum werdenalle Datensätze (oder Zeiger auf Datensätze) nur in Blattknoten gespeichert.. Interne Knoten (Nicht-Blattknoten) speichern nur Schlüssel für das Routing.
  2. Verkettung der Blattknoten: Alle Blattknoten sind durch Zeiger zu einersortierten doppelt verketteten Liste verknüpft。

Abbildung: B+-Baum-Diagramm. Beachten Sie, dass sich Daten nur in Blattknoten befinden und Blattknoten eine sortierte verkettete Liste bilden.

Der enorme Vorteil von B+-Bäumen

Vorteile Erklärung
Stabilere Abfrageeffizienz Jede Suche muss zu einem Blattknoten führen; die Pfadlängen sind gleich, daher ist die Leistung stabil.
Höhere Speicherplatznutzung Interne Knoten speichern keine Daten, daher können sie mehr Schlüssel aufnehmen, was den Baum kürzer macht und I/O reduziert.
Leistungsstarke Bereichsabfrage Durch die verkettete Liste der Blattknoten können effizientWHERE age BETWEEN 20 AND 30Bereichsabfragen durchgeführt werden, während B-Bäume eine komplexe In-Order-Traversierung erfordern.
Besser für das Vorabrufen von der Festplatte geeignet Festplattenlese-/-schreibvorgänge erfolgen seitenweise (in Blöcken). B+-Baumknoten sind normalerweise so ausgelegt, dass sie genau eine Seite groß sind, sodass ein E/A-Vorgang mehr Schlüssel laden kann, wodurch E/A weiter reduziert wird.

Zusammenfassung

Verwenden wir eine Tabelle, um diese vier fortgeschrittenen Baumstrukturen zu überprüfen:

Baumstruktur Kernziel Hauptmerkmale Typische Anwendungen
AVL-Baum Höchstmögliche Abfragegeschwindigkeit Hochgradig streng ausbalanciert, mit häufigen Rotationsanpassungen Szenarien, die schnelle Suchvorgänge im Speicher erfordern
Rot-Schwarz-Baum Ausgewogene Gesamtleistung Näherungsweise ausbalanciert durch Farbregeln, effizientes Einfügen und Löschen Sprachstandardbibliotheken (Map/Set), Prozess-Scheduling
B-Baum Festplatten-I/O reduzieren Mehrwege-balanciert, Daten können in internen Knoten gespeichert werden Frühe Dateisysteme, bestimmte Datenbankindizes
B+-Baum Datenbankindex optimieren Daten nur in Blättern gespeichert, Blätter bilden eine verkettete Liste, starke Bereichsabfragen Indizes moderner relationaler Datenbanken (MySQL, PostgreSQL)
Weitere Erweiterungen