Löschen von Knoten in Binärbäumen

flowchart TD
e50((50))
e50---e30((30))
e30---e20((20))
e20---e10((10))
e30---e40((40))
e50---e80((80))
e80---e60((60))
e60---e55((55))
e60---e70((70))
e80---e90((90))
e90---e95((95))

Löschen von Knoten:

Knoten ohne Kinder (= Blatt)

1. Knoten mit Inhalt 10
   • da es sich um ein Blatt handelt muss nur der Entsprechende Knoten gelöscht werden

Knoten mit einem Kind

2. Knoten mit Inhalt 20 und 90

• Setze das Blatt 10/95 als linken/rechten Teilbaum des Knotens 30/80

flowchart TD
dots([...])---e30((30))---e10((10))
e30---e40((40))

dots2([...])---e80((80))---e60((60))
e80---e95((95))
e60---e55((55))
e60---e70((70))

Knoten mit mehreren Kindern

3. Knotens mit Inhalt 80

• Mehrere Möglichkeiten:
  1. Suche im llinken Teilbaum das größte Element (also Blatt) und setze es an die Stelle von 80

flowchart TD
e50((50))---e30((30))---e20((20))---e((10))
e30---e40((40))

e50---e70((70))---e60((60))
e60---e55((55))
e70---e90((90))---e95((95))