|
Gegeben sei ein neues Element u mit k = v(u),
das in T einzufügen ist:
| |||||||||||
Das Einfügen hat einen Aufwand von O(h(T)).
| |||||||||||
Wenn Elemente in sortierter Reihenfolge eingefügt werden,
degeneriert der Baum zur linearen Liste mit
h(T) = card(T).
Dieses ``worst case''-Szenario läßt sich durch diverse
Algorithmen vermeiden, die den Baum bei Bedarf umbauen
(z.B. die Höhenausgeglichenheit sicherstellen).
|
Copyright © 1999 Andreas Borchert, in HTML konvertiert am 29.06.1999 |