Einfügen in einen binären sortierten Baum

 [Vorheriges Kapitel]  [Vorherige Seite]  [Inhaltsverzeichnis]  [Nächste Seite]  [Nächstes Kapitel]

*Gegeben sei ein neues Element u mit k = v(u), das in T einzufügen ist:

1.Erzeuge einen neuen binären sortieren Baum U, der nur aus der Wurzel u besteht.
 
2.Wenn T leer ist, dann ist T durch U zu ersetzen.
 
3.Es geht weiter mit dem zweiten Schritt, wobei

*T = T1, falls k < v(t), und
 
*T = T2, falls k >= v(t).
 

*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).
 

 [Vorheriges Kapitel]  [Vorherige Seite]  [Inhaltsverzeichnis]  [Nächste Seite]  [Nächstes Kapitel]
Copyright © 1999 Andreas Borchert, in HTML konvertiert am 29.06.1999