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.

Implementierung

Eine effiziente und veränderbare Baumstruktur in Cairo (oder in jeder rein funktionalen Programmiersprache mit unveränderlichem Speicher) zu implementieren, ist eine Herausforderung, denn diese Sprachen sind darauf ausgelegt, Daten nach ihrer Erstellung nicht mehr zu verändern. Diese Unveränderlichkeit bedeutet: Statt einen Baumknoten direkt zu aktualisieren, musst du bei jeder Veränderung eine neue Version des Baums erstellen.

Um zu zeigen, warum das so ist, stell dir eine einfache binäre Baumstruktur vor, in der jeder Knoten ein linkes und ein rechtes Kind hat. Nehmen wir an, wir beginnen mit einem kleinen Baum wie diesem:

       1
      / \
     2   3

Angenommen, wir möchten einen neuen Knoten 4 als linkes Kind von Knoten 2 hinzufügen. In einer rein funktionalen Sprache (wie Cairo oder Haskell) ist der Speicher unveränderlich, wir können Knoten 4 also nicht einfach direkt zu 2 hinzufügen. Stattdessen müssen wir für jeden Knoten auf dem Pfad von der Wurzel bis zum veränderten Knoten eine neue Version erstellen, denn jeder Knoten auf diesem Pfad zeigt jetzt auf einen neuen oder veränderten Teilbaum.

So würde der Vorgang aussehen:

1. Knoten 4 zu Knoten 2 hinzufügen:

   • Erstelle eine neue Version von Knoten 2, die jetzt 4 als linkes Kind hat.

       2'
      / 
     4   
   

2. Den Wurzelknoten aktualisieren:

   • Da Knoten 1 ursprünglich auf den alten 2 zeigte, erstellen wir eine neue Version des Wurzelknotens 1', der jetzt links auf den aktualisierten Knoten 2' zeigt und rechts Knoten 3 behält.

       1'
      / \
     2'  3
   

Der resultierende Baum sieht dann so aus:

       1'
      / \
     2'  3
    /
   4

Dieser neue Baum (1') ähnelt noch immer dem ursprünglichen, nur mit einem aktualisierten Pfad. Der entscheidende Punkt ist, dass wir jeden Knoten auf dem Pfad (1 bis 2) neu erstellen mussten, um die Unveränderlichkeit zu wahren, denn bestehende Knoten können nicht an Ort und Stelle verändert werden. Der ursprüngliche Baum existiert weiterhin (zum Beispiel für alle Verweise auf seine ursprüngliche Wurzel 1), während dieser neue Baum den veränderten Zustand darstellt.

Bei großen Bäumen kann dieser Ansatz aufwendig werden, denn jede neue Veränderung erfordert es, einen Pfad von Knoten von der Wurzel bis zum aktualisierten Knoten neu zu erstellen, selbst wenn sich nur ein kleiner Teil des Baums tatsächlich ändert.