Dans ce didacticiel, vous apprendrez comment fonctionne l'arbre de recherche binaire. Vous trouverez également des exemples fonctionnels d'arborescence de recherche binaire en C, C ++, Java et Python.
L'arbre de recherche binaire est une structure de données qui nous permet rapidement de maintenir une liste triée de nombres.
- C'est ce qu'on appelle un arbre binaire car chaque nœud d'arbre a un maximum de deux enfants.
- On l'appelle un arbre de recherche car il peut être utilisé pour rechercher la présence d'un nombre dans le
O(log(n))temps.
Les propriétés qui séparent un arbre de recherche binaire d'un arbre binaire normal sont
- Tous les nœuds du sous-arbre gauche sont inférieurs au nœud racine
- Tous les nœuds du sous-arbre droit sont plus que le nœud racine
- Les deux sous-arbres de chaque nœud sont également des BST, c'est-à-dire qu'ils ont les deux propriétés ci-dessus
Un arbre ayant un sous-arbre droit avec une valeur inférieure à la racine est montré pour démontrer qu'il ne s'agit pas d'un arbre de recherche binaire valide
L'arbre binaire de droite n'est pas un arbre de recherche binaire car le sous-arbre droit du nœud "3" contient une valeur plus petite que lui.
Il existe deux opérations de base que vous pouvez effectuer sur une arborescence de recherche binaire:
Opération de recherche
L'algorithme dépend de la propriété de BST que si chaque sous-arbre gauche a des valeurs sous la racine et chaque sous-arbre droit a des valeurs au-dessus de la racine.
Si la valeur est inférieure à la racine, nous pouvons dire avec certitude que la valeur n'est pas dans le bon sous-arbre; nous n'avons besoin de rechercher que dans le sous-arbre de gauche et si la valeur est au-dessus de la racine, nous pouvons affirmer avec certitude que la valeur n'est pas dans le sous-arbre de gauche; nous devons rechercher uniquement dans le bon sous-arbre.
Algorithme:
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)
Essayons de visualiser cela avec un diagramme.
4 n'est pas trouvé donc, traverser par le sous-arbre gauche de 8 
4 n'est pas trouvé donc, traverser par le sous-arbre droit de 3 
4 n'est pas trouvé donc, traverser par le sous-arbre gauche de 6 4 est trouvé
Si la valeur est trouvée, nous retournons la valeur afin qu'elle soit propagée à chaque étape de récursivité comme indiqué dans l'image ci-dessous.
Si vous avez pu le remarquer, nous avons appelé la recherche de retour (struct node *) quatre fois. Lorsque nous retournons le nouveau nœud ou NULL, la valeur est renvoyée encore et encore jusqu'à ce que la recherche (racine) renvoie le résultat final.
Si la valeur est trouvée dans l'un des sous-arbres, elle est propagée vers le haut pour qu'à la fin elle soit renvoyée, sinon null est retourné
Si la valeur n'est pas trouvée, nous atteignons finalement l'enfant gauche ou droit d'un nœud feuille qui est NULL et il est propagé et renvoyé.
Insérer une opération
L'insertion d'une valeur à la bonne position est similaire à la recherche car nous essayons de maintenir la règle selon laquelle le sous-arbre gauche est inférieur à racine et le sous-arbre droit est plus grand que racine.
Nous continuons à aller soit au sous-arbre droit, soit au sous-arbre gauche en fonction de la valeur et lorsque nous atteignons un point où le sous-arbre gauche ou droit est nul, nous y mettons le nouveau nœud.
Algorithme:
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'algorithme n'est pas aussi simple qu'il en a l'air. Essayons de visualiser comment nous ajoutons un nombre à un BST existant.
4 <8 donc, transversal à l'enfant gauche de 8 
4> 3 donc, transversal à l'enfant droit de 8 
4 <6 donc, transversal à l'enfant gauche de 6 
Insérer 4 en tant qu'enfant gauche de 6
Nous avons attaché le nœud mais nous devons quand même quitter la fonction sans endommager le reste de l'arbre. C'est là que return node;la fin est utile. Dans le cas de NULL, le nœud nouvellement créé est retourné et attaché au nœud parent, sinon le même nœud est retourné sans aucun changement au fur et à mesure que nous remontons jusqu'à ce que nous revenions à la racine.
Cela garantit que lorsque nous remontons dans l'arborescence, les autres connexions de nœuds ne sont pas modifiées.
Image montrant l'importance de renvoyer l'élément racine à la fin pour que les éléments ne perdent pas leur position lors de l'étape de récursivité ascendante.
Opération de suppression
Il existe trois cas pour supprimer un nœud d'un arbre de recherche binaire.
Cas I
Dans le premier cas, le nœud à supprimer est le nœud feuille. Dans un tel cas, supprimez simplement le nœud de l'arborescence.
4 doit être supprimé 
Supprimer le nœud
Cas II
Dans le second cas, le nœud à supprimer se trouve à un seul nœud enfant. Dans un tel cas, suivez les étapes ci-dessous:
- Remplacez ce nœud par son nœud enfant.
- Retirez le nœud enfant de sa position d'origine.
6 doit être supprimé, 
copier la valeur de son enfant dans le nœud et supprimer l' 
arbre final enfant
Cas III
Dans le troisième cas, le nœud à supprimer a deux enfants. Dans un tel cas, suivez les étapes ci-dessous:
- Obtenez le successeur en ordre de ce nœud.
- Remplacez le nœud par le successeur en ordre.
- Retirez le successeur en ordre de sa position d'origine.
3 doit être supprimé Copier la valeur du successeur inorder (4) dans le nœud 
Supprimer le successeur inorder
Exemples Python, Java et 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); )
Complexités de l'arborescence de recherche binaire
Complexité temporelle
| Opération | Meilleure complexité de cas | Complexité moyenne des cas | Pire complexité des cas |
| Chercher | O (log n) | O (log n) | Sur) |
| Insertion | O (log n) | O (log n) | Sur) |
| Effacement | O (log n) | O (log n) | Sur) |
Ici, n est le nombre de nœuds dans l'arborescence.
Complexité spatiale
La complexité spatiale pour toutes les opérations est O (n).
Applications d'arbre de recherche binaire
- En indexation multi-niveaux dans la base de données
- Pour un tri dynamique
- Pour gérer les zones de mémoire virtuelle dans le noyau Unix
