Höhe und vollständige Bäume

Die Höhe eines Baumes ist die Länge des längsten Pfades von der Wurzel zu einem Blatt (Konventionen variieren um 1; hier: Blatt hat Höhe 0). Ein vollständiger Binärbaum füllt Ebenen von links nach rechts.

In einem ausgeglichenen Baum wächst die Höhe nur langsam mit der Knotenzahl. In einer entarteten Kette wächst sie proportional zur Knotenzahl.

Viele Algorithmen hängen von der Höhe ab (Suche, Einfügen).

$$h_{\mathrm{complete}} = \lfloor \log_2 n \rfloor$$

$$h_{\mathrm{complete}}=\lfloor \log n \rfloor$$

Wo gebraucht

Balancierung, Worst-Case-Suche, Speicherlayout von Heaps. Die Höhe steuert Latenz von Suchstrukturen und die Stacktiefe rekursiver Walks.

Vertiefung

Die Höhe misst den längsten Wurzel-Blatt-Pfad, je nach Konvention in Kanten oder Knoten. Diese Konvention verändert Basiswerte für leere Bäume und Blätter, nicht aber die asymptotische Aussage.

Ein vollständig gefüllter Baum verdoppelt die maximale Knotenzahl mit jeder zusätzlichen Ebene. Daher reicht eine im Verhältnis zur Knotenzahl kleine Höhe aus. Ein stark einseitiger Baum verliert diesen Vorteil und verhält sich strukturell wie eine Liste.

Vollständig, perfekt und komplett bezeichnen unterschiedliche Formbedingungen. Für Heap-Implementierungen ist besonders wichtig, dass alle Ebenen bis auf die letzte gefüllt sind und die letzte von links belegt wird.

Schwierigkeitsstufen

1. Höhe unter einer angegebenen Konvention berechnen.
2. Knotenzahl und Ebenenzahl eines perfekten Baums verknüpfen.
3. Perfekte, vollständige und einseitige Formen unterscheiden.

Fallstricke

Ohne genannte Konvention sind Höhenwerte um eins mehrdeutig. Eine grosse Knotenzahl garantiert ausserdem keine geringe Höhe, wenn keine Balancebedingung vorliegt.