Structure des données - Arborescence de recherche binaire

Un arbre de recherche binaire (BST) est un arbre dans lequel tous les nœuds suivent les propriétés mentionnées ci-dessous -

  • La valeur de la clé du sous-arbre gauche est inférieure à la valeur de la clé de son nœud parent (racine).

  • La valeur de la clé du sous-arbre droit est supérieure ou égale à la valeur de la clé de son nœud parent (racine).

Ainsi, BST divise tous ses sous-arbres en deux segments; le sous-arbre gauche et le sous-arbre droit et peuvent être définis comme -

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

Représentation

BST est une collection de nœuds disposés de manière à conserver les propriétés BST. Chaque nœud a une clé et une valeur associée. Lors de la recherche, la clé souhaitée est comparée aux clés dans BST et si elle est trouvée, la valeur associée est récupérée.

Voici une représentation picturale de BST -

Nous observons que la clé du nœud racine (27) a toutes les clés de moindre valeur sur le sous-arbre de gauche et les clés de valeur supérieure sur le sous-arbre de droite.

Opérations de base

Voici les opérations de base d'un arbre -

  • Search - Recherche un élément dans un arbre.

  • Insert - Insère un élément dans une arborescence.

  • Pre-order Traversal - Traverse un arbre en pré-commande.

  • In-order Traversal - Traverse un arbre dans l'ordre.

  • Post-order Traversal - Traverse un arbre de manière post-ordre.

Nœud

Définissez un nœud contenant des données, des références à ses nœuds enfants gauche et droit.

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

Opération de recherche

Chaque fois qu'un élément doit être recherché, lancez la recherche à partir du nœud racine. Ensuite, si les données sont inférieures à la valeur de clé, recherchez l'élément dans le sous-arbre de gauche. Sinon, recherchez l'élément dans le sous-arbre de droite. Suivez le même algorithme pour chaque nœud.

Algorithme

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;
}

Insérer une opération

Chaque fois qu'un élément doit être inséré, localisez d'abord son emplacement approprié. Commencez la recherche à partir du nœud racine, puis si les données sont inférieures à la valeur de clé, recherchez l'emplacement vide dans le sous-arbre de gauche et insérez les données. Sinon, recherchez l'emplacement vide dans le sous-arbre de droite et insérez les données.

Algorithme

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;
            }
         }
      }            
   }
}