My IT Utilities

Binärer Suchbaum (BST)

Von einem zufälligen binären Suchbaum ausgehen und Werte Schritt für Schritt einfügen, suchen oder löschen, mit Array-Form und hervorgehobenem C++-Code.

Alles wird in diesem Browser simuliert; nichts wird an einen Server gesendet.

Keine Schritte

Keine Schritte

Binärer Suchbaum

Array-Index

60[0]45[1]85[2]68[5]21[3]55[4]32[8]

Array-Form

Die Kinder von Index i liegen bei 2i+1 und 2i+2.

  • Unbeteiligt
  • Bereits passiert
  • Wird verglichen
  • Gefunden
  • Neu
  • Zu löschen
  • Nachfolger

Keine Schritte

Code

#include <iostream>
using namespace std;
class Node { // Ein Knoten enthält seinen Wert und Zeiger auf seine beiden Kinder
private: // Private Attribute: nur die Methoden greifen darauf zu
int value;
Node* left;
Node* right;
public:
Node(int v) : value(v), left(nullptr), right(nullptr) {}
int getValue() const { return value; }
Node* getLeft() const { return left; }
Node* getRight() const { return right; }
void setValue(int v) { value = v; }
void setLeft(Node* n) { left = n; }
void setRight(Node* n) { right = n; }
};
Node* insert(Node* root, int v) { // Fügt v in den Suchbaum ein und gibt die Wurzel zurück
if (root == nullptr) // Freie Stelle: hier kommt der neue Knoten hin
return new Node(v); // Erzeugt den neuen Knoten
if (v < root->getValue()) // Kleinere Werte gehen nach links, größere nach rechts
root->setLeft(insert(root->getLeft(), v)); // Steigt in den linken Teilbaum ab
else
root->setRight(insert(root->getRight(), v)); // Steigt in den rechten Teilbaum ab
return root;
}
int main() {
Node* root = buildTree(); // Der angezeigte Baum, bereits aufgebaut
root = insert(root, v); // Erster Aufruf, aus main
return 0; // Ende der Operation
}

Dieses Tool startet mit einem zufälligen binären Suchbaum (BST) und lässt Sie ihn von Hand verändern: Geben Sie einen Wert von 1 bis 99 ein und drücken Sie Einfügen, Suchen oder Löschen. Jede Operation wird am Baum schrittweise animiert, mit Knoten, die nach ihrer Rolle gefärbt sind: wird verglichen, bereits passiert, neu, zu löschen oder Nachfolger. Darunter sehen Sie denselben Baum als Array, mit den Kindern von Index i bei 2i+1 und 2i+2, und der C++-Code hebt die ausgeführte Zeile hervor. Sie können die Größe von 3 bis 15 Knoten ändern, einen anderen Baum erzeugen und zu jedem Schritt zurückgehen. Alles wird in Ihrem Browser simuliert.

So funktioniert es

  1. Stellen Sie die Baumgröße mit dem Schieberegler ein oder drücken Sie Neuen Baum erzeugen, um den Ausgangspunkt zu ändern.
  2. Geben Sie einen Wert von 1 bis 99 ein und drücken Sie Einfügen, Suchen oder Löschen. Die Animation startet von selbst.
  3. Gehen Sie mit den Schaltflächen für vorigen und nächsten Schritt vor oder zurück, oder drücken Sie Abspielen und ändern Sie die Geschwindigkeit.
  4. Beobachten Sie die farbigen Knoten, die Array-Form des Baums und die hervorgehobene Zeile des C++-Codes.

Häufig gestellte Fragen

Was ist ein binärer Suchbaum und welche Eigenschaft hält er ein?
Ein Binärbaum, in dem jeder Knoten höchstens zwei Kinder hat und alle Werte im linken Teilbaum kleiner als der Wert des Knotens sind, alle im rechten größer. Dank dieser Eigenschaft lässt sich bei jedem Vergleich die Hälfte des verbleibenden Wegs ausschließen.
Wie funktionieren Einfügen und Suchen im BST und was kosten sie?
Beide beginnen an der Wurzel und vergleichen den Wert mit jedem Knoten: Ist er kleiner, geht es nach links, ist er größer, nach rechts. Die Suche endet, wenn der Wert gefunden oder nullptr erreicht wird, und das Einfügen legt den neuen Knoten an dieser leeren Stelle an. Der Aufwand ist proportional zur Höhe des Baums: logarithmisch bei Balance, linear bei einer Kette.
Welche drei Fälle hat das Löschen und warum wird der Inorder-Nachfolger genutzt?
Ist der Knoten ein Blatt, wird er einfach entfernt. Hat er ein Kind, tritt dieses an seine Stelle. Hat er zwei, wird der Wert des Inorder-Nachfolgers, des kleinsten im rechten Teilbaum, in ihn kopiert und der Knoten des Nachfolgers gelöscht. Der Nachfolger ist der nächste Wert in der Ordnung, passt also dorthin, ohne die BST-Eigenschaft zu verletzen, und da er kein linkes Kind hat, ist sein Löschen einer der einfachen Fälle.
Wie wird ein Baum in einem Array gespeichert und warum gibt es Lücken?
Im Heap-Layout: Die Wurzel liegt bei Index 0 und die Kinder von Index i bei 2i+1 und 2i+2. Fehlt einem Knoten ein Kind, bleibt diese Position leer, und je unausgewogener der Baum ist, desto mehr Lücken entstehen, weil die Indizes mit der Tiefe wachsen.

Verwandte Tools