Struttura dei dati - Albero di ricerca binario

Un albero di ricerca binario (BST) è un albero in cui tutti i nodi seguono le proprietà indicate di seguito:

• Il valore della chiave del sottoalbero sinistro è inferiore al valore della chiave del suo nodo padre (radice).

• Il valore della chiave del sottoalbero destro è maggiore o uguale al valore della chiave del suo nodo padre (radice).

Pertanto, BST divide tutti i suoi sottoalberi in due segmenti; il sottoalbero sinistro e il sottoalbero destro e può essere definito come -

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

Rappresentazione

BST è una raccolta di nodi disposti in modo tale da mantenere le proprietà BST. Ogni nodo ha una chiave e un valore associato. Durante la ricerca, la chiave desiderata viene confrontata con le chiavi in ​​BST e, se trovata, viene recuperato il valore associato.

Di seguito è una rappresentazione pittorica della BST -

Osserviamo che la chiave del nodo radice (27) ha tutte le chiavi di minor valore nel sottoalbero di sinistra e le chiavi di valore più alto sul sottoalbero di destra.

Operazioni di base

Di seguito sono riportate le operazioni di base di un albero:

• Search - Cerca un elemento in un albero.

• Insert - Inserisce un elemento in un albero.

• Pre-order Traversal - Attraversa un albero in modalità pre-ordine.

• In-order Traversal - Attraversa un albero in modo ordinato.

• Post-order Traversal - Attraversa un albero in modo post-ordine.

Nodo

Definisci un nodo con alcuni dati, riferimenti ai suoi nodi figlio sinistro e destro.

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

Operazione di ricerca

Ogni volta che si deve cercare un elemento, avviare la ricerca dal nodo radice. Quindi, se i dati sono inferiori al valore chiave, cerca l'elemento nella sottostruttura sinistra. Altrimenti, cerca l'elemento nella sottostruttura a destra. Segui lo stesso algoritmo per ogni nodo.

Algoritmo

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

Inserisci operazione

Ogni volta che deve essere inserito un elemento, individuare prima la sua posizione corretta. Inizia la ricerca dal nodo radice, quindi se i dati sono inferiori al valore della chiave, cerca la posizione vuota nella sottostruttura sinistra e inserisci i dati. Altrimenti, cerca la posizione vuota nella sottostruttura destra e inserisci i dati.

Algoritmo

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