Arbre binaire de recherche (ABR)
Dernière mise à jour
Un arbre binaire de recherche garde ses valeurs triées : pour chaque nœud, toutes les valeurs de son sous-arbre gauche sont plus petites et toutes celles de son sous-arbre droit sont plus grandes. Pour insérer ou trouver une valeur, vous partez de la racine et allez à gauche ou à droite selon la comparaison, de sorte que chaque étape divise par deux l'espace de recherche. Appuyez sur lecture ci-dessus pour voir les valeurs placées par comparaison et une recherche descendre dans l'arbre.
Sur un arbre équilibré, ces opérations s'exécutent en temps O(log n). Le piège : insérer des données déjà triées fait dégénérer l'arbre en une liste chaînée avec des opérations en O(n), ce qui explique précisément l'existence de variantes auto-équilibrées comme les arbres AVL et rouge-noir.
Complexité en temps et en espace
| Opération | Équilibré | Pire cas (déséquilibré) |
|---|---|---|
| Recherche | O(log n) | O(n) |
| Insertion | O(log n) | O(n) |
| Suppression | O(log n) | O(n) |
| Espace | O(n) | O(n) |
Étape par étape (insertion)
| Étape | Ce qui se passe |
|---|---|
| 1 | Si l'arbre est vide, la nouvelle valeur devient la racine. |
| 2 | Sinon, commencer à la racine. |
| 3 | Si la valeur est plus petite, aller au fils gauche ; si elle est plus grande, aller à droite. |
| 4 | Répéter jusqu'à atteindre un emplacement vide. |
| 5 | Y attacher la nouvelle valeur comme feuille. |
Exemple détaillé
Insertion de [5, 3, 8, 1, 4] dans un arbre vide, une valeur à la fois :
| Insérer | Chemin suivi | Action |
|---|---|---|
5 | - | L'arbre est vide, donc 5 devient la racine. |
3 | 5 | 3 < 5, aller à gauche ; l'emplacement est vide, attacher 3 comme fils gauche de 5. |
8 | 5 | 8 > 5, aller à droite ; l'emplacement est vide, attacher 8 comme fils droit de 5. |
1 | 5 -> 3 | 1 < 5 aller à gauche, puis 1 < 3 aller à gauche ; attacher 1 comme fils gauche de 3. |
4 | 5 -> 3 | 4 < 5 aller à gauche, puis 4 > 3 aller à droite ; attacher 4 comme fils droit de 3. |
Quand utiliser un arbre binaire de recherche
| À utiliser quand | À éviter quand |
|---|---|
| Vous avez besoin d'un ordre trié et de recherches rapides, et les insertions arrivent dans un ordre aléatoire. | Vos données arrivent déjà triées : un ABR déséquilibré dégrade à O(n) par opération. |
| Vous voulez qu'un parcours infixe rende les valeurs en séquence triée gratuitement. | Vous n'avez besoin que de tests d'appartenance sans ordre : une table de hachage offre des recherches en O(1) en moyenne. |
| Vous avez besoin de requêtes par intervalle ou du successeur/prédécesseur d'une clé. | Vous avez besoin de garanties en O(log n) : optez plutôt pour un arbre auto-équilibré AVL ou rouge-noir. |
| Le jeu de données change souvent et mettre à jour un tableau trié serait coûteux. | Le jeu de données est fixe et en lecture seule : un tableau trié avec recherche binaire est plus simple et adapté au cache. |
Code de Binary Search Tree
Une implémentation propre et exécutable de Binary Search Tree en Python, JavaScript, Java, C++, C. Choisissez un langage, copiez le code ou ouvrez-le préchargé dans le Playground Coddy.
Code de Binary Search Tree en Python
Python
1class Node:2 def __init__(self, key):3 self.key = key4 self.left = None5 self.right = None6
7
8def insert(node, key):9 if node is None:10 return Node(key)11 if key < node.key:12 node.left = insert(node.left, key)13 elif key > node.key:14 node.right = insert(node.right, key)15 return node # duplicates are ignored16
17
18def search(node, key):19 if node is None:20 return False21 if key == node.key:22 return True23 if key < node.key:24 return search(node.left, key)25 return search(node.right, key)26
27
28def inorder(node):29 if node is None:30 return []31 return inorder(node.left) + [node.key] + inorder(node.right)32
33
34root = None35for key in [8, 3, 10, 1, 6, 14, 4, 7]:36 root = insert(root, key)37
38print("Inorder (sorted):", inorder(root))39print("search(6): ", search(root, 6))40print("search(5): ", search(root, 5))Code de Binary Search Tree en JavaScript
JavaScript
1class Node {2 constructor(value) {3 this.value = value;4 this.left = null;5 this.right = null;6 }7}8
9class BinarySearchTree {10 constructor() {11 this.root = null;12 }13
14 insert(value) {15 const attach = (node) => {16 if (!node) return new Node(value);17 if (value < node.value) node.left = attach(node.left);18 else node.right = attach(node.right);19 return node;20 };21 this.root = attach(this.root);22 }23
24 search(value) {25 let current = this.root;26 while (current) {27 if (value === current.value) return true;28 current = value < current.value ? current.left : current.right;29 }30 return false;31 }32
33 // Inorder traversal of a BST visits values in sorted order34 inorder(node = this.root, out = []) {35 if (!node) return out;36 this.inorder(node.left, out);37 out.push(node.value);38 this.inorder(node.right, out);39 return out;40 }41}42
43const bst = new BinarySearchTree();44for (const value of [8, 3, 10, 1, 6, 14, 4]) bst.insert(value);45console.log("Inorder:", bst.inorder().join(" "));46console.log("search(6):", bst.search(6));47console.log("search(7):", bst.search(7));Code de Binary Search Tree en Java
Java
1public class Main {2 static class Node {3 int key;4 Node left, right;5 Node(int key) { this.key = key; }6 }7
8 static Node insert(Node node, int key) {9 if (node == null) return new Node(key);10 // Smaller keys go left, larger keys go right11 if (key < node.key) node.left = insert(node.left, key);12 else if (key > node.key) node.right = insert(node.right, key);13 return node;14 }15
16 static boolean search(Node node, int key) {17 if (node == null) return false;18 if (key == node.key) return true;19 return key < node.key ? search(node.left, key) : search(node.right, key);20 }21
22 static void inorder(Node node, StringBuilder sb) {23 if (node == null) return;24 inorder(node.left, sb);25 sb.append(node.key).append(" ");26 inorder(node.right, sb);27 }28
29 public static void main(String[] args) {30 Node root = null;31 int[] keys = {8, 3, 10, 1, 6, 14, 4};32 for (int k : keys) root = insert(root, k);33
34 StringBuilder sb = new StringBuilder();35 inorder(root, sb);36 System.out.println("Inorder (sorted): " + sb.toString().trim());37 System.out.println("search 6: " + search(root, 6));38 System.out.println("search 7: " + search(root, 7));39 }40}Code de Binary Search Tree en C++
C++
1#include <iostream>2
3struct Node {4 int value;5 Node* left = nullptr;6 Node* right = nullptr;7 explicit Node(int v) : value(v) {}8};9
10Node* insert(Node* root, int value) {11 if (root == nullptr) return new Node(value);12 if (value < root->value) root->left = insert(root->left, value);13 else if (value > root->value) root->right = insert(root->right, value);14 return root; // duplicates are ignored15}16
17bool contains(const Node* root, int value) {18 // Walk down: smaller goes left, larger goes right19 while (root != nullptr) {20 if (value == root->value) return true;21 root = value < root->value ? root->left : root->right;22 }23 return false;24}25
26void inorder(const Node* node) {27 if (node == nullptr) return;28 inorder(node->left);29 std::cout << node->value << " ";30 inorder(node->right);31}32
33int main() {34 Node* root = nullptr;35 for (int value : {50, 30, 70, 20, 40, 60, 80}) {36 root = insert(root, value);37 }38 std::cout << "Sorted: ";39 inorder(root);40 std::cout << "\n" << std::boolalpha;41 std::cout << "contains(40): " << contains(root, 40) << "\n";42 std::cout << "contains(45): " << contains(root, 45) << "\n";43 return 0;44}Code de Binary Search Tree en C
C
1#include <stdbool.h>2#include <stdio.h>3#include <stdlib.h>4
5typedef struct Node {6 int value;7 struct Node* left;8 struct Node* right;9} Node;10
11Node* newNode(int value) {12 Node* n = malloc(sizeof(Node));13 n->value = value;14 n->left = n->right = NULL;15 return n;16}17
18Node* insert(Node* root, int value) {19 if (root == NULL) return newNode(value);20 if (value < root->value) root->left = insert(root->left, value);21 else if (value > root->value) root->right = insert(root->right, value);22 return root; // duplicates are ignored23}24
25bool contains(const Node* root, int value) {26 // Walk down: smaller goes left, larger goes right27 while (root != NULL) {28 if (value == root->value) return true;29 root = value < root->value ? root->left : root->right;30 }31 return false;32}33
34void inorder(const Node* node) {35 if (node == NULL) return;36 inorder(node->left);37 printf("%d ", node->value);38 inorder(node->right);39}40
41int main(void) {42 int values[] = {50, 30, 70, 20, 40, 60, 80};43 Node* root = NULL;44 for (int i = 0; i < 7; i++) root = insert(root, values[i]);45 printf("Sorted: ");46 inorder(root);47 printf("\n");48 printf("contains(40): %s\n", contains(root, 40) ? "true" : "false");49 printf("contains(45): %s\n", contains(root, 45) ? "true" : "false");50 return 0;51}FAQ sur l'arbre binaire de recherche
Quelle est la complexité temporelle d'un arbre binaire de recherche ?
La recherche, l'insertion et la suppression sont en
O(log n) sur un arbre équilibré, car chaque comparaison écarte la moitié des nœuds restants. Dans le pire cas - un arbre déséquilibré en chaîne à cause d'insertions triées - elles dégradent à O(n).Quelle est la différence entre un arbre binaire et un arbre binaire de recherche ?
Un arbre binaire est tout arbre où chaque nœud a au plus deux fils, sans règle d'ordre. Un arbre binaire de recherche ajoute l'invariant selon lequel les valeurs du sous-arbre gauche sont plus petites et celles du sous-arbre droit plus grandes que le nœud, ce qui permet une recherche rapide.
Pourquoi un arbre binaire de recherche peut-il devenir lent ?
Si les valeurs sont insérées dans l'ordre trié (ou inverse), chaque nouveau nœud va du même côté, produisant un arbre haut et déséquilibré qui se comporte comme une liste chaînée :
O(n) par opération. Les arbres auto-équilibrés (AVL, rouge-noir) effectuent des rotations de nœuds pour éviter cela.Quelle est la différence entre un arbre binaire de recherche et une table de hachage ?
Une table de hachage offre des recherches en
O(1) en moyenne mais stocke les clés sans ordre particulier, elle ne peut donc pas répondre aux requêtes par intervalle ou de successeur. Un arbre binaire de recherche est un peu plus lent en O(log n) mais garde les clés triées, ce qui permet de les parcourir dans l'ordre et de trouver les valeurs voisines. Choisissez un ABR quand l'ordre compte et une table de hachage quand vous n'avez besoin que de tests d'appartenance.Quand devrais-je utiliser un arbre auto-équilibré plutôt qu'un ABR simple ?
Utilisez un arbre auto-équilibré (AVL, rouge-noir) chaque fois que vous ne pouvez pas contrôler l'ordre d'insertion et que vous avez besoin de performances garanties en
O(log n). Un ABR simple convient pour l'enseignement, pour de petits jeux de données ou quand les clés arrivent dans un ordre aléatoire, mais il n'offre aucune protection contre le pire cas déséquilibré.Un parcours infixe d'un ABR renvoie-t-il des valeurs triées ?
Oui. Visiter le sous-arbre gauche, puis le nœud, puis le sous-arbre droit rend les clés dans l'ordre croissant, ce qui découle directement de l'invariant de l'ABR. Une erreur courante est d'attendre la même chose d'un arbre binaire simple : sans la règle d'ordre, le parcours infixe ne produit aucune séquence significative.
Ressources associées
Plus de visualisations
