Löschen in einem binären sortierten Baum
Der Knoten
u
T
ist aus
T
zu entfernen:
1.
Sei
U
der Teilbaum von
T
mit root(
U
) =
u
.
2.
Falls
U
1
leer ist, dann ist
U
durch
U
2
zu ersetzen.
3.
Falls
U
2
leer ist, dann ist
U
durch
U
1
zu ersetzen.
4.
Wenn jedoch
U
1
und
U
2
nicht leer sind, dann
ist
u
2
U
2
so auszuwählen, daß
v
(
u
2
)
v
(
t
)
t
U
2
(einfach nur links absteigen, bis es nicht weitergeht),
u
2
aus
U
2
zu entfernen (recht einfach, da zumindest der linke Teilbaum leer ist) und
u
2
als Ersatz für den Knoten
u
zu verwenden.
Das Löschen hat einen Aufwand von
O
(
h
(
T
)), der im wesentlichen durch die Suche nach dem minimalen Element in
U
2
bestimmt ist.
Copyright © 1999
Andreas Borchert
, in HTML konvertiert am 29.06.1999
![[Vorheriges Kapitel]](pprev.gif)
![[Vorherige Seite]](prev.gif)
![[Inhaltsverzeichnis]](up.gif)
![[Nächste Seite]](next.gif)
![[Nächstes Kapitel]](nnext.gif)
T ist aus T zu entfernen:
v(t) 
t