/ Datenstrukturen

Binärbaum min. Tiefe

Minimal benötigte Tiefe eines Binärbaums mit n Knoten (vollständig gefüllte Ebenen): MinTiefe = ⌊log₂(n)⌋. Untere Schranke für Suchoperationen.

01 · Eingabe

Binärbaum min. Tiefe berechnen

Minimal benötigte Tiefe eines Binärbaums mit n Knoten (vollständig gefüllte Ebenen): MinTiefe = ⌊log₂(n)⌋. Untere Schranke für Suchoperationen.

Lösen für

MinTiefe = ⌊log₂(n)⌋

n Knotenanzahl

Worum geht es?

Bei einem perfekt balancierten Binärbaum mit n Knoten ist die geringstmögliche Tiefe MinTiefe = ⌊log₂(n)⌋. Sie ist die theoretische untere Schranke für jede vergleichsbasierte Suche — auch optimierte Bäume wie Red-Black oder AVL können diese Tiefe nur um einen kleinen Faktor überschreiten.

Praktisch heißt das: jeder selbstbalancierende Suchbaum garantiert O(log n) für Suchen, Einfügen und Löschen — egal in welcher Reihenfolge die Werte kommen. Ein degenerierter, einseitig wachsender Baum (entstanden aus sortierter Eingabe in einen unausbalancierten BST) erreicht dagegen die maximale Tiefe n − 1 und damit O(n).

Die Formel

Formel Min. Tiefe

MinTiefe = ⌊log₂(n)⌋

Umkehrung (max. Knoten bei Tiefe d):
    n_max = 2^(MinTiefe + 1) − 1

Die Variablen

Symbol	Bedeutung	Einheit	Erklärung
n	Knotenanzahl	—	Anzahl Knoten im Baum (n ≥ 1).
MinTiefe	Min. Tiefe	—	Kleinste mögliche Baumtiefe.

Minimal-Beispiel

Welche Mindesttiefe hat ein Baum mit 1000 Knoten?

Rechnung n = 1000

MinTiefe = ⌊log₂(1000)⌋
         = ⌊9,966⌋
         = 9

Praxis-Beispiele

Beispiel 1 — Suchschritte im Lexikon

Ein BST über das Duden-Wörterbuch (≈ 145 000 Einträge) bei perfekter Balance:

Rechnung Duden

MinTiefe = ⌊log₂(145 000)⌋
         = ⌊17,15⌋
         = 17
⇒ max. 18 Vergleiche pro Suche.

Beispiel 2 — Datenbank-Index

Ein B-Tree-Index über 1 Mrd. Datensätze. Reduziert auf einen vollständigen Binärbaum wären das:

Rechnung 10⁹ Datensätze

MinTiefe = ⌊log₂(10⁹)⌋
         = ⌊29,897⌋
         = 29

Reale B-Trees haben Ordnung 100+ und brauchen daher nur 4–5 Ebenen für die gleiche Datenmenge — siehe „B-Baum max. Schlüssel".

Beispiel 3 — Worst-Case unbalanciert

Werden die Zahlen 1, 2, 3, …, 1000 in dieser Reihenfolge in einen einfachen BST eingefügt, entsteht eine reine Liste:

Rechnung Degenerierter BST

Min. Tiefe (balanciert):    9
Tatsächliche Tiefe:       999
⇒ Such-Komplexität:        O(n) statt O(log n)