Ein binärer Suchbaum (BST) ist ein Baum, in dem alle Knoten den unten genannten Eigenschaften folgen-
-
Der Wert des Schlüssels des linken Unterbaums ist kleiner als der Wert des Schlüssels des übergeordneten (Stamm−) Knotens.
-
Der Wert des Schlüssels des rechten Unterbaums ist größer oder gleich dem Wert des Schlüssels des übergeordneten (Stamm -) Knotens.,
Somit teilt BST alle seine Unterbäume in zwei Segmente; der linke Unterbaum und der rechte Unterbaum und kann definiert werden als –
left_subtree (keys) < node (key) ≤ right_subtree (keys)
BST ist eine Sammlung von Knoten, die so angeordnet sind, dass sie BST-Eigenschaften beibehalten. Jeder Knoten hat einen Schlüssel und einen zugehörigen Wert. Während der Suche wird der gewünschte Schlüssel mit den Schlüsseln in BST verglichen und, falls gefunden, der zugehörige Wert abgerufen.,
Es folgt eine bildliche Darstellung von BST –
Wir beobachten, dass der Stammknotenschlüssel (27) alle wenigerwertigen Schlüssel im linken Unterbaum und die höherwertigen Schlüssel im rechten Unterbaum hat.
Grundoperationen
Es folgen die Grundoperationen eines Baums −
-
Suche − Durchsucht ein Element in einem Baum.
-
Insert-Fügt ein Element in einen Baum ein.
-
Vorbestellung Traversal-Durchquert einen Baum in einer Vorbestellung.
-
In-order Traversal-Durchquert einen Baum in einer In-Order-Weise.,
-
Post-order Traversal-Durchquert einen Baum in einer Post-Order-Weise.
Knoten
Definieren Sie einen Knoten mit einigen Daten, Verweisen auf seine linken und rechten untergeordneten Knoten.
struct node { int data; struct node *leftChild; struct node *rightChild;};
Suchvorgang
Wenn ein Element gesucht werden soll, starten Sie die Suche vom Stammknoten aus. Wenn die Daten kleiner als der Schlüsselwert sind, suchen Sie nach dem Element im linken Teilbaum. Suchen Sie andernfalls nach dem Element im richtigen Teilbaum. Folgen Sie dem gleichen Algorithmus für jeden Knoten.,
Algorithmus
Insert Operation
Wenn ein Element eingefügt werden soll, suchen Sie zuerst seine richtige Position. Starten Sie die Suche vom Stammknoten aus, und wenn die Daten kleiner als der Schlüsselwert sind, suchen Sie nach der leeren Position im linken Teilbaum und fügen Sie die Daten ein. Suchen Sie andernfalls nach der leeren Position im rechten Teilbaum und fügen Sie die Daten ein.