Vollständige Binärbäume
Ein interessanter Sonderfall einer Datenstruktur,
deren Strukturinformation implizit gegeben ist
und daher nicht gespeichert werden muß,
sind vollständige Binärbäume.
Diese haben bei gegebener Knotenzahl die minimale Höhe
und damit die kürzesten Suchwege;
Anwendung finden sie beispielsweise bei dem
(hier nicht besprochenen) Sortierverfahren Heapsort.
Ein vollständiger Binärbaum wird schrittweise aufgebaut,
indem man beginnend an der Wurzel die folgenden "Ebenen"
von links beginnend jeweils soweit möglich und nötig auffüllt.
Die laufende Nummer eines Knotens bestimmt somit seine Position im Baum
vollständig, und man kann die Dateninhalte einfach hintereinander
in einem ab 1 indizierten Array ablegen.
Ausgehend von der Platznummer eines Knotens im Array findet man die
Nummer seines Vaters durch Halbieren; der ältere Sohn hat
die doppelte Platznummer, und dessen Bruder liegt unmittelbar dahinter.
So kann man bequem im Baum auf- und absteigen,
ohne irgendwelche Zeiger mitführen zu müssen.
Nr(Vater(n)) = Nr(n) DIV 2
Nr(Sohn1(n)) = Nr(n) * 2 
Nr(Sohn2(n)) = Nr(n) * 2 + 1
zurück |
Inhalt | Index |
vor |
Vorlesung
Klaus Lagally, 22. Februar 2000, 19:36