Positionssuche mit balancierten Bäumen
- sind linearen Listen in fast allen Grundoperationen überlegen
- Positionssuche (Suche nach k-tem Element der Sortierreihenfolge) kann jedoch noch verbessert werden.
Definition: Der Rang eines Knotens ist die um 1 erhöhte Anzahl der Knoten seines linken Unterbaums
Verbesserung bei Positionssuche mit AVL - Bäumen
Jeder Knoten erhält Rang als Hilfsgröße