Struttura dei dati e algoritmi - Albero

L'albero rappresenta i nodi collegati dai bordi. Discuteremo specificamente l'albero binario o l'albero di ricerca binario.

L'albero binario è una struttura dati speciale utilizzata per scopi di archiviazione dei dati. Un albero binario ha una condizione speciale che ogni nodo può avere un massimo di due figli. Un albero binario ha i vantaggi sia di un array ordinato che di un elenco collegato poiché la ricerca è veloce come in un array ordinato e le operazioni di inserimento o eliminazione sono veloci come in un elenco collegato.

Termini importanti

Di seguito sono riportati i termini importanti rispetto all'albero.

  • Path - Il percorso si riferisce alla sequenza di nodi lungo i bordi di un albero.

  • Root- Il nodo nella parte superiore dell'albero è chiamato root. C'è solo una radice per albero e un percorso dal nodo radice a qualsiasi nodo.

  • Parent - Qualsiasi nodo tranne il nodo radice ha un bordo verso l'alto a un nodo chiamato genitore.

  • Child - Il nodo sotto un dato nodo connesso dal suo bordo verso il basso è chiamato il suo nodo figlio.

  • Leaf - Il nodo che non ha alcun nodo figlio è chiamato nodo foglia.

  • Subtree - Il sottoalbero rappresenta i discendenti di un nodo.

  • Visiting - La visita si riferisce al controllo del valore di un nodo quando il controllo è sul nodo.

  • Traversing - Attraversare significa passare attraverso i nodi in un ordine specifico.

  • Levels- Il livello di un nodo rappresenta la generazione di un nodo. Se il nodo radice è al livello 0, il suo successivo nodo figlio è al livello 1, il suo nipote è al livello 2 e così via.

  • keys - La chiave rappresenta un valore di un nodo in base al quale deve essere eseguita un'operazione di ricerca per un nodo.

Rappresentazione dell'albero di ricerca binaria

L'albero di ricerca binario mostra un comportamento speciale. Il figlio sinistro di un nodo deve avere un valore inferiore al valore del suo genitore e il figlio destro del nodo deve avere un valore maggiore del suo valore genitore.

Implementeremo l'albero utilizzando l'oggetto nodo e collegandoli tramite riferimenti.

Nodo dell'albero

Il codice per scrivere un nodo della struttura ad albero sarebbe simile a quanto riportato di seguito. Ha una parte dati e riferimenti ai suoi nodi figlio sinistro e destro.

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

In un albero, tutti i nodi condividono un costrutto comune.

BST Operazioni di base

Le operazioni di base che possono essere eseguite su una struttura dati ad albero di ricerca binario, sono le seguenti:

  • Insert - Inserisce un elemento in un albero / crea un albero.

  • Search - Cerca un elemento in un albero.

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

  • Inorder Traversal - Attraversa un albero in modo ordinato.

  • Postorder Traversal - Attraversa un albero in modo post-ordine.

In questo capitolo impareremo a creare (inserire in) una struttura ad albero e cercare un elemento di dati in un albero. Impareremo i metodi di attraversamento degli alberi nel prossimo capitolo.

Inserisci operazione

Il primo vero inserimento crea l'albero. Successivamente, 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

If root is NULL 
   then create root node
return

If root exists then
   compare the data with node.data
   
   while until insertion position is located

      If data is greater than node.data
         goto right subtree
      else
         goto left subtree

   endwhile 
   
   insert data
	
end If

Implementazione

L'implementazione della funzione di inserimento dovrebbe essere simile a questa:

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, create root node
   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;
            }
         }
      }            
   }
}

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 della chiave, cercare l'elemento nella sottostruttura sinistra. Altrimenti, cerca l'elemento nella sottostruttura a destra. Segui lo stesso algoritmo per ogni nodo.

Algoritmo

If root.data is equal to search.data
   return root
else
   while data not found

      If data is greater than node.data
         goto right subtree
      else
         goto left subtree
         
      If data found
         return node
   endwhile 
   
   return data not found
   
end if

L'implementazione di questo algoritmo dovrebbe essere simile a questa.

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

Per conoscere l'implementazione della struttura dei dati dell'albero di ricerca binario, fare clic qui .