Binärer Suchbaum

Anleitung

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

Wenn wir sortierte Daten darstellen müssen, ist ein Array keine gute Datenstruktur.

Nehmen wir an, 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 lässt sich verbessern, wenn wir erkennen, dass wir nur Platz für das neue Element schaffen müssen: [1, nil, 3, 4, 5], und dann das Element in den geschaffenen Platz einfügen. Aber auch das erfordert, dass wir viele Elemente um eine Position nach hinten verschieben.

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

Ein binärer Suchbaum besteht aus einer Reihe miteinander verbundener Knoten. Jeder Knoten enthält ein Datum (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 Datum 4 hätten und das Datum 2 hinzufügen würden, sähe unser Baum so aus:

      4
     /
    2

Wenn wir dann 6 hinzufügen würden, sähe er so aus:

      4
     / \
    2   6

Wenn wir dann 3 hinzufügen würden, sähe er so aus

       4
     /   \
    2     6
     \
      3

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

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

Danksagung

Die Bilder wurden von habere-et-dispertire mit PGF/TikZ von Till Tantau erstellt.