Binärer Suchbaum ist eine Datenstruktur, mit der Sie eine sortierte Liste von Zahlen verwalten können.
- Ein binärer (binärer) Baum wird aufgerufen, weil jeder Baumknoten maximal zwei untergeordnete Elemente hat.
- Ein Suchbaum, weil damit in O(log(n))-Zeit nach einer Zahl gesucht werden kann (Algorithmus mit Zeitkomplexität T(n) = O(log(n))(Anm. d. Red.)).
Eigenschaften, die einen binären Suchbaum von einem regulären binären Baum unterscheiden:
- Alle Knoten des linken Teilbaums sind kleiner als der Wurzelknoten.
- Alle Knoten des rechten Teilbaums sind größer als der Wurzelknoten.
- Beide Teilbäume jedes Knotens sind auch BSTs, d. h. sie haben die beiden oben genannten Eigenschaften.
Der binäre Baum auf der rechten Seite ist kein binärer Suchbaum, da der rechte Teilbaum des Knotens "3" einen Wert enthält, der kleiner als dieser ist.
Es gibt zwei Hauptoperationen, die Sie an einem binären Suchbaum ausführen können:
eines. Prüfen, ob eine Zahl in einem binären Suchbaum vorhanden ist.
Der Algorithmus hängt von der BST-Eigenschaft ab, sodass, wenn jeder linke Teilbaum Werte unterhalb der Wurzel hat, jeder rechte Teilbaum Werte oberhalb der Wurzel hat.
Wenn der Wert kleiner als die Wurzel ist, können wir mit Sicherheit sagen, dass der Wert nicht im rechten Teilbaum ist, was bedeutet, dass wir ihn im linken Teilbaum suchen sollten.
Und umgekehrt, wenn der Wert größer als die Wurzel ist, ist es sicher, dass der Wert nicht im linken Teilbaum ist, was bedeutet, dass Sie im rechten nachsehen müssen.
Algorithmus:
If root == NULL
return NULL;
If number == root->data
return root->data;
If number < root->data
return search(root->left)
If number > root->data
return search(root->right)
Versuchen wir, den Algorithmus mit einem Diagramm zu visualisieren.
Wenn ein Wert gefunden wird, geben wir den Wert zurück, damit er sich durch jeden Schritt der Rekursion ausbreitet, wie in der folgenden Abbildung gezeigt.
Sie haben vielleicht bemerkt, dass wir die Funktion return search (struct node) viermal aufgerufen haben. Wenn wir entweder einen neuen Knoten oder NULL zurückgeben, wird der Wert immer wieder zurückgegeben, bis search(root) das Endergebnis zurückgibt.
Wenn kein Wert gefunden wird, erreichen wir schließlich das linke oder rechte untergeordnete Element des Endknotens, das NULL ist, und es wird weitergegeben und zurückgegeben.
2. Einfügen eines Werts in einen binären Suchbaum (BST)
Das Einfügen eines Werts an der richtigen Position ähnelt einer Suche, da wir versuchen, die Regel zu erfüllen, dass der linke Teilbaum kleiner als die Wurzel und der rechte Teilbaum größer als die Wurzel ist.
Je nach Wert gehen wir weiter entweder zum rechten oder linken Teilbaum, und wenn wir einen Punkt erreichen, an dem der linke oder rechte Teilbaum null ist, setzen wir dort einen neuen Knoten.
Algorithmus:
If node == NULL
return createNode(data)
if (data < node->data)
node->left = insert(node->left, data);
else if (data > node->data)
node->right = insert(node->right, data);
return node;
Der Algorithmus ist nicht so einfach, wie es scheint. Versuchen wir uns vorzustellen, wie wir einer bestehenden BST eine Zahl hinzufügen.
Wir haben den Knoten verbunden, aber wir müssen die Funktion noch verlassen, ohne den Rest des Baums zu beschädigen. Hier ist der Rückgabeknoten am Ende praktisch. In diesem Fall NULL wird der neu erstellte Knoten zurückgegeben und an den übergeordneten Knoten angehängt, ansonsten wird derselbe Knoten ohne Änderungen zurückgegeben, bis wir zum Wurzelknoten zurückkehren.
Dadurch wird sichergestellt, dass sich die Verbindungen zu anderen Knoten nicht ändern, wenn wir im Baum nach oben gehen.
Der vollständige Code zum Einfügen und Suchen in BST in der Programmiersprache C ist unten angegeben:
#include<stdio.h>
#include<stdlib.h>
struct node
{
int data;
struct node* left;
struct node* right;
};
struct node* createNode(value){
struct node* newNode = malloc(sizeof(struct node));
newNode->data = value;
newNode->left = NULL;
newNode->right = NULL;
return newNode;
}
struct node* insert(struct node* root, int data)
{
if (root == NULL) return createNode(data);
if (data < root->data)
root->left = insert(root->left, data);
else if (data > root->data)
root->right = insert(root->right, data);
return root;
}
void inorder(struct node* root){
if(root == NULL) return;
inorder(root->left);
printf("%d ->", root->data);
inorder(root->right);
}
int main(){
struct node *root = NULL;
root = insert(root, 8);
insert(root, 3);
insert(root, 1);
insert(root, 6);
insert(root, 7);
insert(root, 10);
insert(root, 14);
insert(root, 4);
inorder(root);
}
Programmausgabe
1 ->3 ->4 ->6 ->7 ->8 ->10 ->14 ->
