Binärbaum max. Knoten

Worum geht es?

Ein vollständiger Binärbaum der Tiefe h hat auf jeder Ebene k genau 2^k Knoten. Die Summe der geometrischen Reihe 2⁰ + 2¹ + … + 2^h ergibt MaxKnoten = 2^(h+1) − 1.

Diese Formel ist die obere Schranke für Knotenanzahlen in Heaps, Suchbäumen und Tournament Trees. Für balancierte Bäume gilt umgekehrt: bei n Knoten ist die Mindesttiefe h ≥ ⌈log₂(n+1)⌉ − 1.

Die Formel

MaxKnoten = 2^(h + 1) − 1

Umstellung:
    h = log₂(MaxKnoten + 1) − 1

Die Variablen

Minimal-Beispiel

Wie viele Knoten hat ein vollständiger Binärbaum der Tiefe 3?

MaxKnoten = 2^4 − 1
          = 15

Praxis-Beispiele

Beispiel 1 — Heap-Tiefe

Ein Min-Heap mit 1000 Elementen hat welche Tiefe?

h = log₂(1001) − 1
  ≈ 9,97 − 1
  ≈ 8,97
⇒ h = 9 (aufgerundet)

Beispiel 2 — Vergleich der Tiefen

h =  0   →     1 Knoten
h =  3   →    15 Knoten
h = 10   →  2047 Knoten
h = 20   →  ≈ 2,1 Mio. Knoten
h = 30   →  ≈ 2,1 Mrd. Knoten

Beispiel 3 — Speicherbedarf eines balancierten Suchbaums

Ein AVL-Tree mit 10⁶ int32-Knoten und jeweils 16 Byte Overhead (zwei Pointer + Balance) benötigt:

h ≈ log₂(10⁶) ≈ 20
n ≤ 2²¹ − 1 = 2 097 151
Speicher = 10⁶ · (4 + 16) = 20 MB