Binäre Suchbäume remove

[MrXeth]

moin, warum sucht man beim löschen eines Elements mit 2 Kindknoten oder mehr das kleinste im rechten kindbaum bzw. das größte im linken kindbaum? Man könnte ja auch das erste nehmen und die referenzen ändern. Als vorteil sehe ich nur einen einen näheren wert an dem gelöschten knoten und als nachteil eine längere Laufzeit.

Danke für eure hilfe ^^

 

[mihe7]

warum sucht man beim löschen eines Elements mit 2 Kindknoten oder mehr das kleinste im rechten kindbaum bzw. das größte im linken kindbaum?

Also ich suche beim Löschen nach dem Element, das gelöscht werden soll.

 

[MrXeth]

Nach dem suchen tauscht man zum löschen hab mich doof ausgedrückt, sorry

Es geht mir darum, warum man den oben genannten Knoten zum wieder einsetzen nimmt und nicht einen der direkten kindknoten.

Hier ist es bspw als Löschen beider Kindknoten aufgeführt
http://u-helmich.de/inf/BlueJ/kurs121/folge17/folge17-8.html

 

[mihe7]

Um die Invariante des Baums aufrecht zu erhalten.

 

[MrXeth]

Da kann man dann aber doch trotzdem den direkten linken kindknoten eig wählen und referenzen ändern , sodass das kriterium erfüllt ist??

 

[mihe7]

Bildlich:

    4
 2     6
1 3   5 7

Alternative 1: Löschen der 4 durch Ersetzen mit 2:

    2
1 3    6
      5 7

Problem: 3 > 2 befindet sich im linken Teilbaum von 2

Alternative 2: Löschen der 4 durch Ersetzen mit 6:

    6
 2    5 7
1 3  

Problem: 5 < 6 befindet sich im rechten Teilbaum von 6

Welche Referenzen willst Du denn ändern?

 

[MrXeth]

Okay, hat sich erledigt, danke dafür🙂

 

[mihe7]

BTW: wenn Du den Suchbaum als Array darstellst, wirds noch einfacher. Der Baum oben wäre [1,2,3,4,5,6,7]. Wir löschen die 4: [1,2,3,5,6,7]

Abgebildet als Baum:

    3
  1   6
   2 5 7

oder

    5
  2   6
 1 3   7

 

[MrXeth]

Abitur nrw mag aber keine arrays ^^