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.