Numérique et Sciences Informatiques > Algorithmique : Structures de Données Avancées > Arbres Binaires > Arbres binaires de recherche (insertion, recherche)

Arbres Binaires de Recherche : Insertion et Recherche

Comprendre le fonctionnement des arbres binaires de recherche, incluant les algorithmes d'insertion et de recherche. Ce cours est destiné aux élèves de lycée en spécialité NSI.

Introduction aux Arbres Binaires de Recherche

Un arbre binaire de recherche (ABR) est une structure de données arborescente où chaque nœud a au plus deux enfants, appelés enfant gauche et enfant droit. La propriété fondamentale d'un ABR est que, pour chaque nœud:

  • La valeur de tous les nœuds dans son sous-arbre gauche est inférieure à sa propre valeur.
  • La valeur de tous les nœuds dans son sous-arbre droit est supérieure à sa propre valeur.
Cette propriété permet une recherche efficace des éléments, car elle élimine la nécessité d'explorer des parties entières de l'arbre.

Insertion dans un Arbre Binaire de Recherche

L'insertion d'un nouvel élément dans un ABR maintient l'ordre de recherche. Voici l'algorithme d'insertion :

  1. Commencer à la racine de l'arbre.
  2. Comparer la valeur à insérer avec la valeur du nœud courant.
  3. Si la valeur à insérer est inférieure à la valeur du nœud courant, déplacer vers l'enfant gauche.
  4. Si la valeur à insérer est supérieure à la valeur du nœud courant, déplacer vers l'enfant droit.
  5. Répéter les étapes 2 à 4 jusqu'à atteindre un nœud vide (un endroit où l'enfant gauche ou droit est null).
  6. Insérer le nouveau nœud à cet emplacement vide.
Exemple: Considérons un ABR initialement vide. Insérons les valeurs suivantes dans l'ordre : 5, 3, 7, 2, 4, 6, 8.
  • 5 devient la racine.
  • 3 est inférieur à 5, donc il devient l'enfant gauche de 5.
  • 7 est supérieur à 5, donc il devient l'enfant droit de 5.
  • 2 est inférieur à 5 et à 3, donc il devient l'enfant gauche de 3.
  • 4 est inférieur à 5 mais supérieur à 3, donc il devient l'enfant droit de 3.
  • 6 est supérieur à 5 mais inférieur à 7, donc il devient l'enfant gauche de 7.
  • 8 est supérieur à 5 et à 7, donc il devient l'enfant droit de 7.
Il est crucial de comprendre que l'ordre d'insertion influence la structure de l'arbre. Un ordre d'insertion malheureux (par exemple, une séquence croissante) peut conduire à un arbre dégénéré qui ressemble à une liste chaînée, compromettant l'efficacité de la recherche.

Recherche dans un Arbre Binaire de Recherche

La recherche dans un ABR exploite la propriété d'ordre pour trouver un élément rapidement. Voici l'algorithme de recherche :

  1. Commencer à la racine de l'arbre.
  2. Comparer la valeur recherchée avec la valeur du nœud courant.
  3. Si la valeur recherchée est égale à la valeur du nœud courant, la recherche est réussie.
  4. Si la valeur recherchée est inférieure à la valeur du nœud courant, déplacer vers l'enfant gauche.
  5. Si la valeur recherchée est supérieure à la valeur du nœud courant, déplacer vers l'enfant droit.
  6. Répéter les étapes 2 à 5 jusqu'à trouver la valeur ou atteindre un nœud vide (ce qui signifie que la valeur n'est pas présente dans l'arbre).
Exemple: Dans l'ABR construit dans l'exemple précédent, recherchons la valeur 4.
  • On commence à la racine (5).
  • 4 est inférieur à 5, donc on va à l'enfant gauche (3).
  • 4 est supérieur à 3, donc on va à l'enfant droit (4).
  • On trouve la valeur 4, la recherche est réussie.
Si on recherchait la valeur 9, on aurait suivi le chemin racine (5) -> enfant droit (7) -> enfant droit (8) et finalement atteint un nœud vide, indiquant que 9 n'est pas présent dans l'arbre.

Complexité temporelle

La complexité temporelle des opérations d'insertion et de recherche dans un ABR dépend de la forme de l'arbre.

  • Dans le meilleur des cas (arbre équilibré), la complexité est de O(log n), où n est le nombre de nœuds dans l'arbre. Chaque étape divise l'espace de recherche par deux.
  • Dans le pire des cas (arbre dégénéré), la complexité est de O(n), car l'arbre se comporte comme une liste chaînée.
Il est donc important d'utiliser des techniques d'équilibrage d'arbres (comme les arbres AVL ou les arbres rouge-noir) pour garantir une complexité de O(log n) même dans le pire des cas.

Ce qu'il faut retenir

  • Un arbre binaire de recherche (ABR) organise les données de manière hiérarchique pour une recherche efficace.
  • L'insertion maintient la propriété d'ordre de l'ABR.
  • La recherche exploite la propriété d'ordre pour trouver rapidement un élément.
  • La complexité des opérations est O(log n) dans un arbre équilibré, et O(n) dans un arbre dégénéré.
  • L'ordre d'insertion influence la structure de l'arbre.

← Applications Pratiques des Piles et des Files Comparaison Pile: Liste Python vs Tableau →

FAQ

  • Qu'est-ce qui se passe si j'insère des valeurs en ordre croissant dans un arbre binaire de recherche ?

    Si vous insérez des valeurs en ordre croissant, l'arbre dégénérera en une structure similaire à une liste chaînée, où chaque nœud a seulement un enfant droit. Cela rendra la recherche inefficace, avec une complexité de O(n) au lieu de O(log n).
  • Comment puis-je m'assurer que mon arbre binaire de recherche reste équilibré ?

    Vous pouvez utiliser des algorithmes d'équilibrage d'arbres tels que l'algorithme AVL ou l'algorithme des arbres rouge-noir. Ces algorithmes effectuent des rotations de nœuds pour maintenir l'arbre équilibré après chaque insertion ou suppression.
  • Pourquoi les arbres binaires de recherche sont-ils préférés aux listes chaînées ou aux tableaux pour la recherche ?

    Dans le meilleur des cas, les arbres binaires de recherche offrent une complexité temporelle de O(log n) pour la recherche, l'insertion et la suppression, ce qui est plus efficace que les listes chaînées (O(n) pour la recherche et la suppression) et les tableaux non triés (O(n) pour la recherche) pour les grandes quantités de données. Les tableaux triés offrent une recherche rapide (O(log n)) mais l'insertion et la suppression sont coûteuses (O(n)).