Benutzer-Werkzeuge

Webseiten-Werkzeuge


glossar:fast_vollstaendig_binaerbaum

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: 2014/09/24 16:43 (Externe Bearbeitung)