binaere suchbaeume

[lookias]

kann man in binaerten suchbaeumen die wurzel loeschen, oder besser gesagt ist das im normalen Fall sinnvoll, zwecks effizients usw?

mfg

[Ponto]

Kannst du dein Problem genauer darstellen?

[pasti]

Ja kann man In balancierten Binärbäumen ( AVL-Baum usw. ) sind alle Wörterbuchoperationen ( Einfügen, Löschen, Suchen ) in O(log(n)) Zeit möglich.

[lookias]

Ponto schrieb:

Kannst du dein Problem genauer darstellen?

ja, und zwar hab ich einen binaeren suchbaum in c++ programmiert mit allen gaengigen operationen: loeschen suchen und einfuegen

nun bin ich mir niht so wirklich darueber im klaren wenn, dann wie man die wurzel loescht.

ich wuerds auch gerne ohne machen weil das prog dann fertig waer

deswegen wuerde ich auch gern wissen ob das in diesem ADT ueberhaupt so gaengig ist.

FG

edit: ist auch kein AVL sondern son einfacher, soll halt nur ne kleine demonstration sein

[MisterX]

Hallo,

da du einen binären Suchbaum hast müsste gelten, dass alle Daten in den Knoten im linken Teilbaum eines Knoten kleiner sind als das datum im betrachteten Knoten. Und im rechten Teilbaum sind alle größer als der betrachete Knoten.

Beispiel:

7
     / \
    5   9
   /\  /  \
  2  6 8  20

Also wie löscht man die Wurzel?
So wie man alle inneren Knoten löschen sollte. Man tauscht das Wurzelelement gegen das größte Element, das noch kleiner als die Wurzel ist.

=>

6
     / \
    5   9
   /\  /  \
  2  7 8  20

Nun kan man das Element Löschen, da es entweder in einem Blatt steht, oder nur einen Nachfolger hat.

6
     / \
    5   9
   /   /  \
  2   8   20

[lookias]

ok das wird mir klar muss dann nur noch meine statische wurzel variable handeln

sollte aber nicht das problem sein

danke

edit: oder einfach die werte tauschen

[MisterX]

oder einfach die werte tauschen

Das wird nur ein Problem wenn du nacheinander alle elemente im Baum löschen weillst und nur noch die Wurzel zum Löschen überig ist!

[lookias]

MisterX schrieb:

oder einfach die werte tauschen

Das wird nur ein Problem wenn du nacheinander alle elemente im Baum löschen weillst und nur noch die Wurzel zum Löschen überig ist!

ja stimmt, aber es ist ebend gemacht um die arbeitsweise zu erlaeutern AVL ist dann danach dran denke ich