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.

Angenommen, wir haben das Array [1, 3, 4, 5], und wir fügen 2 hinzu, sodass daraus [1, 3, 4, 5, 2] wird. Jetzt müssen wir das gesamte Array erneut sortieren! Wir können das verbessern, indem wir erkennen, dass wir nur Platz für das neue Element schaffen müssen: [1, nil, 3, 4, 5], und dann fügen wir das Element in den geschaffenen Platz ein. Aber das erfordert trotzdem, 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 verbundener Knoten. Jeder Knoten enthält ein Datenelement (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 den Daten 4 hätten und die Daten 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.