Benutzer-Werkzeuge

Webseiten-Werkzeuge


glossar:fast_vollstaendig_binaerbaum

Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen gezeigt.

Link zu dieser Vergleichsansicht

glossar:fast_vollstaendig_binaerbaum [2017/09/26 10:20] (aktuell)
Zeile 1: Zeile 1:
 +====== fast vollständig (Binärbaum) ======
 +
 +===== Bedeutung ======
 +Ein Binärbaum der Höhe h heißt fast vollständig,​ wenn
 +  * jedes Blatt die Tiefe h − 1 oder h − 2 hat,
 +  * jeder Knoten mit einer Tiefe kleiner h − 2 zwei nicht-leere Unterbäume hat,
 +  * für die Knoten K des Niveaus h − 2 gilt:
 +
 +1. Hat K 2 nicht-leere Unterbäume,​ dann auch alle linken Nachbarn von K .
 +
 +2. Ist K ein Blatt, dann sind auch alle rechten Nachbarn von K Blätter.
 +
 +3. Es gibt maximal ein K mit genau einem nicht-leeren Unterbaum und der ist links.
 +
 +Ein Baum der Größe n heißt indiziert, wenn man seine Knoten mittels der Indizes 0, ..., n − 1 ansprechen kann.
 +
  
glossar/fast_vollstaendig_binaerbaum.txt · Zuletzt geändert: 2017/09/26 10:20 (Externe Bearbeitung)