Binärer Suchbaum

Anleitung

Füge Zahlen in einen binären Baum ein und suche nach ihnen.

Wenn wir sortierte Daten darstellen wollen, ist ein Array keine gute Datenstruktur.

Angenommen, wir haben das Array [1, 3, 4, 5] und fügen 2 hinzu, sodass daraus [1, 3, 4, 5, 2] wird. Jetzt müssen wir das gesamte Array erneut sortieren! Das können wir verbessern, wenn wir erkennen, dass wir nur Platz für das neue Element [1, nil, 3, 4, 5] schaffen müssen und das Element dann in den geschaffenen Platz einfügen. Aber auch das erfordert, dass wir viele Elemente um eine Position nach hinten verschieben.

Binäre Suchbäume hingegen können mit sortierten Daten viel effizienter arbeiten.

Ein binärer Suchbaum besteht aus einer Reihe von miteinander verbundenen Knoten. Jeder Knoten enthält einen Datenwert (z. B. die Zahl 3), eine Variable namens left und eine Variable namens right. Die Variablen left und right zeigen auf nil oder auf andere Knoten. Da diese anderen Knoten wiederum weitere Knoten unter sich haben, sagen wir, dass die Variablen left und right auf Teilbäume zeigen. Alle Daten im linken Teilbaum sind kleiner oder gleich den Daten des aktuellen Knotens, und alle Daten im rechten Teilbaum sind größer als die Daten des aktuellen Knotens.

Wenn wir zum Beispiel einen Knoten mit dem Datenwert 4 hätten und den Datenwert 2 hinzufügten, sähe unser Baum so aus:

  4
 /
2

Wenn wir dann 6 hinzufügten, sähe er so aus:

  4
 / \
2   6

Wenn wir dann 3 hinzufügten, sähe er so aus

   4
 /   \
2     6
 \
  3

Und wenn wir dann 1, 5 und 7 hinzufügten, sähe er so aus

      4
    /   \
   /     \
  2       6
 / \     / \
1   3   5   7

Hinweise

Um diese Übung abzuschließen, musst du den Datentyp BST mit Eq- und Show-Instanzen erstellen und die folgenden Funktionen implementieren:

• bstLeft
• bstRight
• bstValue
• empty
• fromList
• insert
• singleton
• toList

Eine Dummy-Datendeklaration und die Typsignaturen sind bereits vorhanden, aber es liegt an dir, die Funktionen zu definieren und einen sinnvollen Datentyp, ein Newtype oder ein Typsynonym zu erstellen.