In questo tutorial imparerai come funziona l'albero di ricerca binario. Inoltre, troverai esempi funzionanti di albero di ricerca binario in C, C ++, Java e Python.
L'albero di ricerca binario è una struttura di dati che ci consente rapidamente di mantenere un elenco ordinato di numeri.
- È chiamato albero binario perché ogni nodo dell'albero ha un massimo di due figli.
- È chiamato albero di ricerca perché può essere utilizzato per cercare la presenza di un numero nel
O(log(n))tempo.
Le proprietà che separano un albero di ricerca binario da un albero binario regolare sono
- Tutti i nodi della sottostruttura sinistra sono inferiori al nodo radice
- Tutti i nodi della sottostruttura destra sono più del nodo radice
- Entrambi i sottoalberi di ciascun nodo sono anche BST, ovvero hanno le due proprietà precedenti
Viene mostrato un albero con una sottostruttura destra con un valore inferiore alla radice per dimostrare che nonèun albero di ricerca binario valido
L'albero binario a destra non è un albero di ricerca binario perché il sottoalbero destro del nodo "3" contiene un valore più piccolo di esso.
Ci sono due operazioni di base che puoi eseguire su un albero di ricerca binario:
Operazione di ricerca
L'algoritmo dipende dalla proprietà di BST che se ogni sottostruttura di sinistra ha valori sotto la radice e ogni sottostruttura di destra ha valori sopra la radice.
Se il valore è inferiore alla radice, possiamo dire con certezza che il valore non è nella sottostruttura corretta; dobbiamo cercare solo nella sottostruttura sinistra e se il valore è sopra la radice, possiamo dire con certezza che il valore non è nella sottostruttura sinistra; dobbiamo cercare solo nella sottostruttura giusta.
Algoritmo:
If root == NULL return NULL; If number == root->data return root->data; If number data return search(root->left) If number> root->data return search(root->right)
Proviamo a visualizzarlo con un diagramma.
4 non viene trovato così, traslazione attraverso il sottoalbero sinistro 8 
4 non viene trovato così, tramite traslazione sottoalbero destro di 3 
4 non viene trovato così, traslazione attraverso il sottoalbero sinistro 6 4 è trovato
Se il valore viene trovato, restituiamo il valore in modo che venga propagato in ogni passaggio di ricorsione come mostrato nell'immagine seguente.
Se l'avete notato, abbiamo chiamato la ricerca di ritorno (struct node *) quattro volte. Quando restituiamo il nuovo nodo o NULL, il valore viene restituito ancora e ancora fino a quando search (root) restituisce il risultato finale.
Se il valore si trova in uno qualsiasi dei sottoalberi, viene propagato verso l'alto in modo che alla fine venga restituito, altrimenti viene restituito null
Se il valore non viene trovato, alla fine raggiungiamo il figlio sinistro o destro di un nodo foglia che è NULL e viene propagato e restituito.
Inserisci operazione
Inserire un valore nella posizione corretta è simile alla ricerca perché cerchiamo di mantenere la regola secondo cui il sottoalbero sinistro è minore di root e il sottoalbero destro è più grande di root.
Continuiamo ad andare sul sottoalbero destro o sul sottoalbero sinistro a seconda del valore e quando raggiungiamo un punto che il sottoalbero sinistro o destro è nullo, mettiamo il nuovo nodo lì.
Algoritmo:
If node == NULL return createNode(data) if (data data) node->left = insert(node->left, data); else if (data> node->data) node->right = insert(node->right, data); return node;
L'algoritmo non è così semplice come sembra. Proviamo a visualizzare come aggiungiamo un numero a un BST esistente.
4 <8 così, trasversale per il bambino sinistro di 8 
4> 3 così, trasversale per il bambino destro di 8 
4 <6 così, trasversale per il bambino sinistro di 6 
Inserisci 4 come bambino sinistro di 6
Abbiamo collegato il nodo ma dobbiamo ancora uscire dalla funzione senza fare alcun danno al resto dell'albero. È qui che return node;torna utile la fine. Nel caso di NULL, il nodo appena creato viene restituito e collegato al nodo genitore, altrimenti lo stesso nodo viene restituito senza alcuna modifica mentre si sale fino a tornare alla radice.
Ciò garantisce che mentre risaliamo l'albero, le altre connessioni del nodo non vengono modificate.
Immagine che mostra l'importanza di restituire l'elemento radice alla fine in modo che gli elementi non perdano la loro posizione durante la fase di ricorsione verso l'alto.
Operazione di cancellazione
Esistono tre casi per l'eliminazione di un nodo da un albero di ricerca binario.
Caso I.
Nel primo caso, il nodo da eliminare è il nodo foglia. In tal caso, è sufficiente eliminare il nodo dall'albero.
4 deve essere cancellato 
Eliminare il nodo
Caso II
Nel secondo caso, il nodo da eliminare si trova ha un unico nodo figlio. In tal caso, attenersi alla procedura seguente:
- Sostituisci quel nodo con il suo nodo figlio.
- Rimuovi il nodo figlio dalla sua posizione originale.
6 deve essere cancellato, 
copiare il valore del suo figlio nel nodo e cancellare l' 
albero finale figlio
Caso III
Nel terzo caso, il nodo da eliminare ha due figli. In tal caso, seguire i passaggi seguenti:
- Ottieni il successore inordine di quel nodo.
- Sostituisci il nodo con il successore inorder.
- Rimuovere il successore inordine dalla sua posizione originale.
3 deve essere cancellato Copiare il valore del successore inorder (4) nel nodo 
Cancellare il successore inorder
Esempi di Python, Java e C / C ++
Python Java C C ++ # Binary Search Tree operations in Python # Create a node class Node: def __init__(self, key): self.key = key self.left = None self.right = None # Inorder traversal def inorder(root): if root is not None: # Traverse left inorder(root.left) # Traverse root print(str(root.key) + "->", end=' ') # Traverse right inorder(root.right) # Insert a node def insert(node, key): # Return a new node if the tree is empty if node is None: return Node(key) # Traverse to the right place and insert the node if key < node.key: node.left = insert(node.left, key) else: node.right = insert(node.right, key) return node # Find the inorder successor def minValueNode(node): current = node # Find the leftmost leaf while(current.left is not None): current = current.left return current # Deleting a node def deleteNode(root, key): # Return if the tree is empty if root is None: return root # Find the node to be deleted if key root.key): root.right = deleteNode(root.right, key) else: # If the node is with only one child or no child if root.left is None: temp = root.right root = None return temp elif root.right is None: temp = root.left root = None return temp # If the node has two children, # place the inorder successor in position of the node to be deleted temp = minValueNode(root.right) root.key = temp.key # Delete the inorder successor root.right = deleteNode(root.right, temp.key) return root root = None root = insert(root, 8) root = insert(root, 3) root = insert(root, 1) root = insert(root, 6) root = insert(root, 7) root = insert(root, 10) root = insert(root, 14) root = insert(root, 4) print("Inorder traversal: ", end=' ') inorder(root) print("Delete 10") root = deleteNode(root, 10) print("Inorder traversal: ", end=' ') inorder(root)
// Binary Search Tree operations in Java class BinarySearchTree ( class Node ( int key; Node left, right; public Node(int item) ( key = item; left = right = null; ) ) Node root; BinarySearchTree() ( root = null; ) void insert(int key) ( root = insertKey(root, key); ) // Insert key in the tree Node insertKey(Node root, int key) ( // Return a new node if the tree is empty if (root == null) ( root = new Node(key); return root; ) // Traverse to the right place and insert the node if (key root.key) root.right = insertKey(root.right, key); return root; ) void inorder() ( inorderRec(root); ) // Inorder Traversal void inorderRec(Node root) ( if (root != null) ( inorderRec(root.left); System.out.print(root.key + " -> "); inorderRec(root.right); ) ) void deleteKey(int key) ( root = deleteRec(root, key); ) Node deleteRec(Node root, int key) ( // Return if the tree is empty if (root == null) return root; // Find the node to be deleted if (key root.key) root.right = deleteRec(root.right, key); else ( // If the node is with only one child or no child if (root.left == null) return root.right; else if (root.right == null) return root.left; // If the node has two children // Place the inorder successor in position of the node to be deleted root.key = minValue(root.right); // Delete the inorder successor root.right = deleteRec(root.right, root.key); ) return root; ) // Find the inorder successor int minValue(Node root) ( int minv = root.key; while (root.left != null) ( minv = root.left.key; root = root.left; ) return minv; ) // Driver Program to test above functions public static void main(String() args) ( BinarySearchTree tree = new BinarySearchTree(); tree.insert(8); tree.insert(3); tree.insert(1); tree.insert(6); tree.insert(7); tree.insert(10); tree.insert(14); tree.insert(4); System.out.print("Inorder traversal: "); tree.inorder(); System.out.println("After deleting 10"); tree.deleteKey(10); System.out.print("Inorder traversal: "); tree.inorder(); ) )
// Binary Search Tree operations in C #include #include struct node ( int key; struct node *left, *right; ); // Create a node struct node *newNode(int item) ( struct node *temp = (struct node *)malloc(sizeof(struct node)); temp->key = item; temp->left = temp->right = NULL; return temp; ) // Inorder Traversal void inorder(struct node *root) ( if (root != NULL) ( // Traverse left inorder(root->left); // Traverse root printf("%d -> ", root->key); // Traverse right inorder(root->right); ) ) // Insert a node struct node *insert(struct node *node, int key) ( // Return a new node if the tree is empty if (node == NULL) return newNode(key); // Traverse to the right place and insert the node if (key key) node->left = insert(node->left, key); else node->right = insert(node->right, key); return node; ) // Find the inorder successor struct node *minValueNode(struct node *node) ( struct node *current = node; // Find the leftmost leaf while (current && current->left != NULL) current = current->left; return current; ) // Deleting a node struct node *deleteNode(struct node *root, int key) ( // Return if the tree is empty if (root == NULL) return root; // Find the node to be deleted if (key key) root->left = deleteNode(root->left, key); else if (key> root->key) root->right = deleteNode(root->right, key); else ( // If the node is with only one child or no child if (root->left == NULL) ( struct node *temp = root->right; free(root); return temp; ) else if (root->right == NULL) ( struct node *temp = root->left; free(root); return temp; ) // If the node has two children struct node *temp = minValueNode(root->right); // Place the inorder successor in position of the node to be deleted root->key = temp->key; // Delete the inorder successor root->right = deleteNode(root->right, temp->key); ) return root; ) // Driver code int main() ( struct node *root = NULL; root = insert(root, 8); root = insert(root, 3); root = insert(root, 1); root = insert(root, 6); root = insert(root, 7); root = insert(root, 10); root = insert(root, 14); root = insert(root, 4); printf("Inorder traversal: "); inorder(root); printf("After deleting 10"); root = deleteNode(root, 10); printf("Inorder traversal: "); inorder(root); )
// Binary Search Tree operations in C++ #include using namespace std; struct node ( int key; struct node *left, *right; ); // Create a node struct node *newNode(int item) ( struct node *temp = (struct node *)malloc(sizeof(struct node)); temp->key = item; temp->left = temp->right = NULL; return temp; ) // Inorder Traversal void inorder(struct node *root) ( if (root != NULL) ( // Traverse left inorder(root->left); // Traverse root cout right); ) ) // Insert a node struct node *insert(struct node *node, int key) ( // Return a new node if the tree is empty if (node == NULL) return newNode(key); // Traverse to the right place and insert the node if (key key) node->left = insert(node->left, key); else node->right = insert(node->right, key); return node; ) // Find the inorder successor struct node *minValueNode(struct node *node) ( struct node *current = node; // Find the leftmost leaf while (current && current->left != NULL) current = current->left; return current; ) // Deleting a node struct node *deleteNode(struct node *root, int key) ( // Return if the tree is empty if (root == NULL) return root; // Find the node to be deleted if (key key) root->left = deleteNode(root->left, key); else if (key> root->key) root->right = deleteNode(root->right, key); else ( // If the node is with only one child or no child if (root->left == NULL) ( struct node *temp = root->right; free(root); return temp; ) else if (root->right == NULL) ( struct node *temp = root->left; free(root); return temp; ) // If the node has two children struct node *temp = minValueNode(root->right); // Place the inorder successor in position of the node to be deleted root->key = temp->key; // Delete the inorder successor root->right = deleteNode(root->right, temp->key); ) return root; ) // Driver code int main() ( struct node *root = NULL; root = insert(root, 8); root = insert(root, 3); root = insert(root, 1); root = insert(root, 6); root = insert(root, 7); root = insert(root, 10); root = insert(root, 14); root = insert(root, 4); cout << "Inorder traversal: "; inorder(root); cout << "After deleting 10"; root = deleteNode(root, 10); cout << "Inorder traversal: "; inorder(root); )
Complessità dell'albero di ricerca binaria
Complessità temporale
| Operazione | Migliore complessità del caso | Complessità media dei casi | Complessità del caso peggiore |
| Ricerca | O (log n) | O (log n) | Su) |
| Inserimento | O (log n) | O (log n) | Su) |
| Cancellazione | O (log n) | O (log n) | Su) |
Qui n è il numero di nodi nell'albero.
Complessità spaziale
La complessità dello spazio per tutte le operazioni è O (n).
Applicazioni dell'albero di ricerca binaria
- Nell'indicizzazione multilivello nel database
- Per l'ordinamento dinamico
- Per la gestione delle aree di memoria virtuale nel kernel Unix
