binärer suchbaum - frage

[lars_]

Gegeben ist der Baum
-----8-------
---/----\----
---7----10---
--/-\--------
-2---5-------
-----/-------
----3--------

Die 7 soll gelöscht werden. 5 kommt an die Stelle der 7. Was passiert aber mit dem linken Element bei der 5? Wo zur Hölle kommt die 3 hin?

[lars__]

----8-------
---/----\----
---7----10---
--/-\--------
-2---5-------
-----/-------
----3--------

[CStoll]

Schau mal in unser Magazin, da gibt es einige ausführliche Artikel zu Binärbäumen.

[lars0]

Ergibt sich mir aus dem Artikel nicht.

[Nobuo T]

Beim Loeschen eines Elements mit 2 Nachfolgern, ersetzt du dieses durch seinen Nachfolger in der Werteordnung. Heisst also den "linkesten" Knoten im rechten Unterbaum (==3 - nicht 5 ) oder den "rechtesten" Knoten im linken Unterbaum (==2).

[Lars]

Hab das programm aus dem magazin, das macht beim löschen der 7 aus:

----8-------
---/----\----
---7----10---
--/-\--------
-2---5-------
-----/-------
----3--------

den baum:

----8-------
---/----\----
---2----10---
----\--------
-----3-------

Warum kommt nich die 5 an die Stelle der 7? Ist doch das größte Element im linken Teilbaum?

[Nobuo T]

Weil dein Baum kein gueltiger binaerer Suchbaum ist *gerade mal auffaellt*.

[Lars]

Shit, hab euch den Baum falsch gezeichnet

----8-------
---/----\----
---7----10---
--/----------
-2-----------
--\-----------
----5-------
---/
--3

Jetzt ist es so zick-zack und es gibt kein linkestes bzw rechtestets Element

[Nobuo T]

Sieht schon besser aus. Und wo ist jetzt das Problem beim Loeschen der 7? Die kannst du einfach ueberbruecken und gut ist.