Datenstruktur - Binärer Suchbaum

Ein binärer Suchbaum (BST) ist ein Baum, in dem alle Knoten den unten genannten Eigenschaften folgen.

• Der Wert des Schlüssels des linken Teilbaums ist kleiner als der Wert des Schlüssels des übergeordneten (Stamm-) Knotens.

• Der Wert des Schlüssels des rechten Teilbaums ist größer oder gleich dem Wert des Schlüssels des übergeordneten (Stamm-) Knotens.

Somit teilt BST alle seine Unterbäume in zwei Segmente ein; der linke Unterbaum und der rechte Unterbaum und können definiert werden als -

left_subtree (keys) < node (key) ≤ right_subtree (keys)

Darstellung

BST ist eine Sammlung von Knoten, die so angeordnet sind, dass sie die 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 wenn er gefunden wird, wird der zugehörige Wert abgerufen.

Es folgt eine bildliche Darstellung von BST -

Wir beobachten, dass der Wurzelknotenschlüssel (27) alle weniger wertvollen Schlüssel im linken Teilbaum und die höherwertigen Schlüssel im rechten Teilbaum hat.

Grundoperationen

Es folgen die grundlegenden Operationen eines Baums -

• Search - Sucht ein Element in einem Baum.

• Insert - Fügt ein Element in einen Baum ein.

• Pre-order Traversal - Durchquert einen Baum vorbestellt.

• In-order Traversal - Durchquert einen Baum in der richtigen Reihenfolge.

• Post-order Traversal - Durchquert einen Baum nachträglich.

Knoten

Definieren Sie einen Knoten mit einigen Daten und Verweisen auf seinen linken und rechten untergeordneten Knoten.

struct node {
   int data;   
   struct node *leftChild;
   struct node *rightChild;
};

Suchvorgang

Wenn ein Element durchsucht 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 rechten Teilbaum. Befolgen Sie für jeden Knoten den gleichen Algorithmus.

Algorithmus

struct node* search(int data){
   struct node *current = root;
   printf("Visiting elements: ");
	
   while(current->data != data){
	
      if(current != NULL) {
         printf("%d ",current->data);
			
         //go to left tree
         if(current->data > data){
            current = current->leftChild;
         }  //else go to right tree
         else {                
            current = current->rightChild;
         }
			
         //not found
         if(current == NULL){
            return NULL;
         }
      }			
   }
   
   return current;
}

Operation einfügen

Wenn ein Element eingefügt werden soll, suchen Sie zuerst die richtige Position. Starten Sie die Suche vom Stammknoten aus. 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 Stelle im rechten Teilbaum und fügen Sie die Daten ein.

Algorithmus

void insert(int data) {
   struct node *tempNode = (struct node*) malloc(sizeof(struct node));
   struct node *current;
   struct node *parent;

   tempNode->data = data;
   tempNode->leftChild = NULL;
   tempNode->rightChild = NULL;

   //if tree is empty
   if(root == NULL) {
      root = tempNode;
   } else {
      current = root;
      parent = NULL;

      while(1) {                
         parent = current;
			
         //go to left of the tree
         if(data < parent->data) {
            current = current->leftChild;                
            //insert to the left
				
            if(current == NULL) {
               parent->leftChild = tempNode;
               return;
            }
         }  //go to right of the tree
         else {
            current = current->rightChild;
            
            //insert to the right
            if(current == NULL) {
               parent->rightChild = tempNode;
               return;
            }
         }
      }            
   }
}