Vorlesung Informatik 2 - Teil B: Theorie
4.14 Vollständige Bäume
Ein vollständiger Baum ist in allen Schichten voll besetzt, d.h. alle Blätter liegen auf der untersten Ebene, haben also die gleiche Tiefe. Ein vollständiger Binärbaum der Höhe h hat genau 2h-1 Knoten.
Ein Binärbaum der Höhe h heißt fast vollständig, wenn
-
jedes Blatt die Tiefe h oder h − 1 hat,
-
die Knoten bis zur Ebene h-1 einen vollständigen Binärbaum bilden,
-
die Blätter der unteren Ebene h von links ohne Lücken aufgefüllt sind.
A
/ \
B C
/ \
D E
Solche fast vollständigen Bäume spielen eine wichtige Rolle, weil sie sich sehr effizient in einem Array speichern lassen:
Der Baum wird in seiner Level-Order im Array gespeichert, wobei die Wurzel in das Array-Element mit dem Index 1 kommt, den Index 0 übergehen wir.
Der oben gezeigte Baum würde demnach so im Array stehen:
-------------------------------
| - | A | B | C | D | E | ...
-------------------------------
0 1 2 3 4 5
Jetzt gilt für ein Array Element mit dem Index i:
- der Vater-Knoten steht am Index i/2 (Integer Division)
- das linke Kind steht am Index 2i, das rechte Kind bei 2i+1.
Diese Implementierung von fast vollständigen Bäumen ist aus mehreren Gründen effizient:
- Die Speicherung ist sehr dicht, wir brauchen keine Referenzen zwischen den Knoten zu speichern.
- Die Navigation entlang eines Pfades geschieht durch Multiplikation oder Division mit 2. Das kann durch Shift-Operationen geschehen, und diese Operationen gehören zu den schnellsten im Befehlssatz eines Prozessors, die in der Regel
nur einen Taktzyklus brauchen.
Beispiel: die Zahl 510 ist binär eine 1012. Shiftet man sie um ein Bit nach rechts entsteht die 102, also eine 2. Shiftet man sie um ein Bit nach links bekommt man 10102 , also die 1010.
Fast vollständige Binärbäume spielen deshalb bei der Verwaltung von Speicher und Prozessen im Betriebssystem eine wichtige Rolle.