Suchbäume

Suchbäume speichern geordnete Schlüssel in einer hierarchischen Struktur, sodass Suche, Einfügen und Löschen einem Pfad von der Wurzel zu den Blättern folgen; selbstbalancierende Varianten halten diesen Pfad kurz, um logarithmische Zeitoperationen zu gewährleisten.

Definition

Ein Suchbaum ist eine baumstrukturierte Datenstruktur, die Schlüssel in sortierter Reihenfolge gemäß einer pro Knoten definierten Ordnungsinvariante verwaltet und effiziente Such-, Einfüge-, Lösch- und ordnungsbasierte Abfragen unterstützt; ein balancierter Suchbaum schränkt zusätzlich seine Form ein, sodass die Höhe logarithmisch zur Anzahl der Schlüssel bleibt.

Scope

Dieses Thema behandelt geordnete Wörterbuchstrukturen, die auf Bäumen basieren: den binären Suchbaum und seine Ordnungsinvariante, die selbstbalancierenden Schemata, die die Höhe begrenzen (AVL, Rot-Schwarz und andere), sowie Mehrweg-Balancierte Bäume wie B-Bäume, die für externen Speicher konzipiert sind. Es befasst sich mit den Operationen, die diese Strukturen über die einfache Suche hinaus unterstützen – Vorgänger, Nachfolger, Bereichsabfragen und geordnete Traversierung – und kontrastiert sie mit Hash-Tabellen, die keine Ordnung bewahren.

Core questions

• Wie ermöglicht die Ordnungsinvariante des binären Suchbaums die Suche als einen Gang von der Wurzel zu den Blättern?
• Warum kann ein unbalancierter Baum zu linearer Zeit degenerieren, und wie verhindert Balancierung dies?
• Welche Rotationen oder Strukturregeln halten AVL- und Rot-Schwarz-Bäume balanciert?
• Warum eignen sich B-Bäume eher für Festplatten- und Datenbankspeicher als Binärbäume?
• Wann sind ordnungserhaltende Operationen den zusätzlichen Aufwand gegenüber einer Hash-Tabelle wert?

Key concepts

• Invariante des binären Suchbaums
• Baumrotationen
• AVL-Bäume
• Rot-Schwarz-Bäume
• B-Bäume
• Baumhöhe und Balance
• In-Order-Traversierung
• Bereichs- und Nachfolgerabfragen

Key theories

Höhenbalancierung garantiert logarithmische Operationen

Durch die Aufrechterhaltung einer Balance-Invariante mittels Rotationen oder Strukturregeln halten selbstbalancierende Bäume die Höhe O(log n), was worst-case O(log n) Such-, Einfüge- und Löschoperationen unabhängig von der Eingabereihenfolge garantiert.

Mehrwegbäume für externen Speicher

B-Bäume speichern viele Schlüssel pro Knoten, um den Größen von Festplattenblöcken zu entsprechen, wodurch die Anzahl langsamer Zugriffe auf externen Speicher minimiert wird; dies macht sie zur Standardstruktur für Datenbanken und Dateisysteme.

Clinical relevance

Suchbäume sind zentral für Systeme, die einen geordneten Zugriff benötigen: Rot-Schwarz-Bäume implementieren geordnete Maps und Sets in Standardbibliotheken, B-Bäume und ihre Varianten sind die dominierende Indexstruktur in relationalen Datenbanken und Dateisystemen, und balancierte Bäume unterstützen Bereichsabfragen, Intervallplanung und geometrische Suchstrukturen.

History

AVL-Bäume, die ersten selbstbalancierenden binären Suchbäume, wurden 1962 von Adelson-Velsky und Landis eingeführt. Bayer und McCreight führten 1972 B-Bäume für große geordnete Indizes ein, und Rot-Schwarz-Bäume wurden 1978 von Guibas und Sedgewick als praktisches Balancierungsschema entwickelt und bildeten die Grundlage vieler Standardbibliotheksimplementierungen.

Key figures

• Georgy Adelson-Velsky
• Evgenii Landis
• Rudolf Bayer
• Robert Sedgewick
• Robert Tarjan

Seminal works

• bayer1972
• cormen2009

Frequently asked questions

Warum sollte man nicht immer eine Hash-Tabelle anstelle eines Suchbaums verwenden?

Hash-Tabellen bieten schnellere durchschnittliche Suchvorgänge, aber keine Ordnung. Suchbäume halten Schlüssel sortiert, was Bereichsabfragen, geordnete Iteration und Vorgänger-/Nachfolger-Suchen in O(log n) ermöglicht, was Hash-Tabellen nicht effizient können. Die Wahl hängt davon ab, ob die Reihenfolge wichtig ist.

Warum verwenden Datenbanken B-Bäume anstelle von binären Suchbäumen?

B-Bäume packen viele Schlüssel in jeden Knoten, um der Größe eines Festplattenblocks zu entsprechen, sodass eine Suche weitaus weniger langsame externe Speicherblöcke berührt als ein Binärbaum mit der gleichen Schlüsselanzahl. Dies minimiert die E/A-Vorgänge, die die Leistung in Datenbanken und Dateisystemen dominieren.