Ein Binärbaum der Höhe h heißt fast vollständig, wenn
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.