Binäre Suchbäume in der Informatik einfach erklärt

Binärbaum

In diesem Beitrag wird es um binäre Suchbäume gehen. Aus diesem Grund erkläre ich zunächst, was denn überhaupt ein Binärbaum ist.

Ein Binärbaum ist ein Spezialfall von einer Baum-Datenstruktur. Jeder Knoten hat maximal Zwei Kind-Knoten, einen Linken und einen Rechten. Ein vollständiger Binärbaum hat 2^d Blätter und 2^(d + 1) – 1 Knoten.

Einfacher Binärbaum
Einfacher Binärbaum

Binäre Suchbäume

Ein binärer Suchbaum eignet sich hervorragend für eine binäre Suche. Für jeden Knoten n gilt:

Binäre Suche mit einem Binärbaum
Es gilt: left.value≤n.value right.value≥n.value

Beispiel für die Suche nach einer Zahl in einem binären Suchbaum

Wir suchen die Zahl 24 in dem Beispielsbild oben und gehen wie folgt vor:

24>20⇒right
24≤28⇒left
24=24⇒found

Beispiel für das Einfügen einer Zahl in einen binären Suchbaum

Um die Zahl 25 in den binären Suchbaum einzufügen, müssen wir wie folgt vorgehen. 

Einfügen der Zahl 25 in einen binären Suchbaum
Einfügen der Zahl 25 in einen binären Suchbaum

Löschen einer Zahl aus einem binären Suchbaum

Hier muss eine Unterscheidung nach der Anzahl von Kind-Knoten erfolgen. Je nach dem ob der zu löschende Knoten noch Kind-Knoten besitzt, können wir diesen nämlich nicht so einfach aus dem Suchbaum löschen.

  1. Besitzt er keine weiterem Kind-Knoten, können wir ihn einfach löschen
  2. Besitzt er einen weiteren Kind-Knoten, ersetzen wir den zu löschenden Knoten mit seinem Kind-Knoten
  3. Besitzt er zwei Kind-Knoten, ersetzen wir den zu löschenden Knoten mit dem Minimum des rechten Pfades und entferne diesen Minimum Knoten.

1) Löschen ohne Kind-Knoten

Wir können die 5 ohne weitere Maßnahmen einfach löschen.
Wir können die 5 ohne weitere Maßnahmen einfach löschen.

2) Löschen mit einem Kind-Knoten

24 mit 25 ersetzen in einem binaeren Suchbaum
Da die 24 nur einen Kind-Knoten besitzt, können wir die 24 entfernen und durch die 25 ersetzen.

3) Löschen mit zwei Kind-Knoten

Loeschen der Zahl 28 in einem binaeren Suchbaum
Die 28 hat Zwei Kind-Knoten, also müssen wir den Minimum-Knoten aus dem rechten Pfad finden.
28 mit 29 ersetzen in einem binaeren Suchbaum
Danach ersetzen wir die 28 mit der gefundenen 29 und löschen die 29.

Balancierter binärer Suchbaum

Da im worst-case die Effizienz von binären Suchbäumen für das Entfernen und Hinzufügen von Knoten auf 0(n) sinkt, verwendet man in der Praxis balancierte binäre Suchbäume.

Ein balancierter binärer Suchbaum erfüllt folgende Eigenschaften:

  • es gibt n Knoten
  • die maximale Tiefe ist d
  • d <= c * log n

Dies garantiert, dass binäre Suchbäume in 0(log n) bleiben.

Rebalancing eines binären Suchbaums

Um einen binären Suchbaum neu zu Rebalancing, muss man wie folgt vorgehen:

  1. Erzeuge eine sortierte Liste.
  2. Erzeuge aus der sortierten Liste einen balancierten binären Suchbaum
Vollstaendige Traversierung eines binaeren Suchbaums
Die vollständige Traversierung des Baums benötigt eine Laufzeit von 0 (n).

 

Nachtraegliche Traversierung eines binaeren Suchbaums
Die nachträgliche Erstellung eines balancierten binären Suchbaums hat ebenfalls eine Laufzeit von O (n).

Gesamte Laufzeit:

O(n + n) = O(n)

Scapegoat-Tree

Ein Scapegoat-Tree ist ein selbst-balancierender binärer Suchbaum, der bei jedem Einfügen und Entfernen von Elementen den Baum auf, “Balanciertheit” prüft und ggf. den unbalancierten Knoten sucht und ein Rebalancing durchführt.

Scapegoat-Tree
Scapegoat-Tree

Sortiertes Einfügen im Scapegoat-Tree

Dieser Vorgang funktioniert im Allgemeinen wie bei einem binärem Suchbaum. Jedoch wird die Tiefe des eingefügten Knotens zwischengespeichert. Danach wird auf “Höhen-Balanciertheit” getestet:

Bildschirmfoto 2021 01 29 um 09.32.12

  • d ⇒ Zwischengespeicherte Tiefe
  • s ⇒ Size, größe des Trees.
  • alpha ⇒ wert Zwischen 0.5 Und 1.0, wobei 0.5 für einen perfekt balancierter Baum steht und 1.0 für einen schlecht balancierten Baum steht.

Falls der Baum nicht alpha-Höhen-balanciert ist, muss der „Sündenbock” gefunden werden. Dabei wird an der zwischengespeicherten Höhe d begonnen und der erste Eltern knoten p gesucht, der nicht alpha-balanciert ist und für den gilt:

Bildschirmfoto 2021 01 29 um 09.33.30

Danach wird der Knoten rebalanciert.

Zusammenhang von Gewichts-und Höhenbalanciertheit

Wenn ein Baum nicht a-höhen-balanciert ist, existiert mindestens ein Knoten im Baum, der nicht a- gewichts-balanciert ist.
Um diese Behauptung zu begründen, betrachten wir zunächst die maximale Tiefe des Baums. Die maximale Knotenanzahl auf der tiefsten Ebene dieses Baums ist:

Bildschirmfoto 2021 01 29 um 09.33.54

Die tiefste Ebene sollte die Ebene sein, auf der N_max = 1 ist. Für die tiefste Ebene gilt:

Bildschirmfoto 2021 01 29 um 09.34.17

Bildschirmfoto 2021 01 29 um 09.34.38
Umso mehr sich Alpha der 1 nähert desto eher ist der Baum höhen balanciert.

Beispiel Einfügen einer Zahl

Scapegoat Tree Einfuegen
Die „ -1″ wurde neu eingefügt. Gegeben ist ein alpha-balancier-wert von 0,6. Nun suchen wir unseren “Sündenbock” im Baum. Beginnend beim zuletzt eingefügten Wert und danach weiter in Richtung Wurzel.

Für „-1″:

  • a × size = 0,6
  • left size <= 0,6 ✓
  • right size <= 0,6 ✓
  • left und right size sind 0

 Für „0″

  • a × size = 1,2
  • left size <= 1,2 ✓
  • right size <= 1,2 ✓
  • left size = 1
  • right size = 0

Für „2″:

  • a × size = 1,8
  • left size <= 1,8 X
  • right size <= 1,8 ✓
  • left size =3
  • wir haben die „2″ als Sündenbock identifiziert. Demnach muss an dieser Stelle ein Rebalacing stattfinden und wir erhalten den folgenden Baum:
Scapegoat Tree Einfuegen balanciert
Rebalancing

Beispiel für das Löschen einer Zahl

Wenn einseitig gelöscht wird, kann die Balanciertheit darunter leiden. Wenn das Folgende gilt, muss der ganze Baum neu balanciert werden:

size<α·maxsize

Dies ist ein perfekt balancierter Baum für den gilt:

perfekt balancierter Baum

 

Wir löschen nur solange Elemente einseitig aus dem Baum, bis ein Rebalancing nötig ist.

Loeschen

Es gilt:

size<α·maxsize
4<4,2

Und daraus folgt unser neuer Baum:

Nach dem Loeschen
Laufzeit von Scapegoat Trees:

  • b-search: O(log n)
  • Sorted Insert: O(log n)
  • Sorted Remove: O(log n)

Scapegoat Tree im Vergleich zu Red-Black-Tree und AVL-Tree

Red-Black-Trees (Binärer Bäume) eignen sich für häufiges Einfügen und Löschen besser, während man bei Scapegoat Trees Alpha frei wählen kann.

Array als Binärbaum

Es ist möglich einen Binärbaum mittels Arrays zu implementieren. Im Vergleich zu einer verketteten Liste als Datenstruktur ergeben sich folgende Vorteile:

  • Referenzen werden errechnet
  • Die Daten liegen im Speicher direkt hintereinander, wodurch sich ein schnellerer Zugriff ergibt

Heap

Heaps sind mit Arrays realisierte Bäume, die eine Heap-Eigenschaft besitzen. Die Kind-Knoten haben dabei immer einen größeren Wert, als ihre Eltern-Knoten. Für weitere Informationen siehe hier.

Trie – Präfixbaum

Ein Trie, oder auch Präfixbaum genannt, gehört zur Familie der Suchbäume. Anders als bei einem binären Suchbaum kann ein Eltern-Knoten in einem Trie mehrere Kind-Knoten haben. Er repräsentiert nicht den Wert selbst, sondern nur den Präfix.

Beispiel für die Suche in einem Trie

Ein Trie, der aus den Worten „bier”, „bla” , „car”und „biene” besteht .

Trie Praefixbaum Beispiel
Um nach dem wort „car” Zu suchen beginnt man an der Wurzel und sucht zur iten-Ebenen den iten-Buchstaben und findet zum Schluss den grünen Blattknoten. Das heißt, dass gesuchte Wort befindet sich in unserem Trie. Wenn wir das Wort ,, ca” suchen, werden wir zwar den Präfix finden, aber keinen zugehörigen Blatt-Knoten. Was bedeutet, dass der gesuchte String sich nicht in unserem Trie befindet.

Weitere Beiträge aus dieser Serie

Schreibe einen Kommentar

Deine E-Mail-Adresse wird nicht veröffentlicht. Erforderliche Felder sind mit * markiert.

Notify me of followup comments via e-mail. You can also subscribe without commenting.