Arbres binaires de recherche

3.1 Définition d'un arbre binaire de recherche (BST)

Un arbre binaire de recherche (BST) est un arbre binaire possédant les propriétés suivantes :

• Pour tout nœud, son sous-arbre gauche ne contient que des nœuds avec des clés inférieures à la clé de ce nœud.
• Pour tout nœud, son sous-arbre droit ne contient que des nœuds avec des clés supérieures à la clé de ce nœud.
• Les deux sous-arbres de chaque nœud sont également des arbres binaires de recherche.

Exemple de BST :

BST est l'abréviation de Binary Search Tree – littéralement « Arbre binaire de recherche ». En fait, c'est une organisation des données sous forme d'« arbre », permettant une recherche très rapide. La structure de cet arbre est une sorte de tri caché/subtil des éléments.

Parcours en ordre (in-order traversal)

L'objectif du parcours est de former une liste de nœuds d'une certaine manière (ou des données des nœuds, en fonction de la terminologie, ce qui est important en pratique). Le parcours en ordre (symétrique) — est un parcours où la racine de l'arbre prend place entre les résultats des parcours respectifs des sous-arbres gauche et droit.

Avec la propriété de l'arbre binaire de recherche (où il y a des inégalités, voir la théorie), cela implique que le parcours en ordre d'un arbre binaire de recherche nous donnera une liste triée de nœuds — génial ! Voici à quoi ressemblera le parcours de l'arbre défini précédemment :

3.2 Principes de fonctionnement et propriétés du BST

Principes de fonctionnement :

• Organisation des données : Le BST organise les données de manière à assurer une recherche, insertion et suppression efficace des éléments.
• Structure récursive : Chaque nœud dans le BST obéit aux mêmes règles que la racine de l'arbre, rendant la structure récursive.
• Équilibre : Pour garantir une performance optimale, le BST doit être équilibré, c'est-à-dire que la hauteur des sous-arbres gauche et droit doit être à peu près identique.

Propriétés du BST :

• Ordre: À tout moment, on peut parcourir l'arbre en ordre "in-order" (sous-arbre gauche → nœud actuel → sous-arbre droit), pour obtenir tous les éléments dans un ordre trié.
• Temps d'opérations:
  • En moyenne, le temps d'exécution des opérations de recherche, d'insertion et de suppression est de O(log n), où n est le nombre de nœuds.
  • Dans le pire des cas (si l'arbre n'est pas équilibré), le temps d'exécution des opérations peut atteindre O(n).
• Clés uniques : Toutes les clés dans le BST doivent être uniques pour maintenir l'ordre.

3.3 Opérations principales

1. Insertion (Insertion):

Principe de fonctionnement :

• Commencer à partir du nœud racine.
• Comparer la clé du nouveau nœud avec la clé du nœud actuel.
• Si la nouvelle clé est inférieure, passer au sous-arbre gauche, si supérieure — au sous-arbre droit.
• Répéter le processus jusqu'à trouver une place appropriée pour insérer le nouveau nœud (soit le descendant gauche, soit le descendant droit est manquant).

Algorithme :

1. Si l'arbre est vide, le nouveau nœud devient le nœud racine.
2. Sinon, trouver récursivement la bonne place et ajouter le nouveau nœud.

2. Suppression (Deletion):

Principe de fonctionnement :

• Trouver le nœud à supprimer.
• Considérer trois cas :
• Le nœud est une feuille (n'a pas d'enfants) : il suffit de supprimer le nœud.
• Le nœud a un enfant : remplacer le nœud par son enfant.
• Le nœud a deux enfants : trouver le nœud le plus petit dans le sous-arbre droit (ou le plus grand dans le gauche), copier sa valeur dans le nœud à supprimer et supprimer récursivement le nœud le plus petit du sous-arbre droit.

Algorithme :

1. Trouver le nœud avec la clé donnée.
2. Selon le cas, effectuer la suppression et la redistribution des nœuds correspondantes.

3. Recherche (Search):

Principe de fonctionnement :

• Commencer à partir du nœud racine.
• Comparer la clé du nœud recherché avec la clé du nœud actuel.
• Si la clé correspond, renvoyer le nœud.
• Si la clé est inférieure, passer au sous-arbre gauche, si supérieure — au sous-arbre droit.
• Répéter le processus jusqu'à trouver un nœud avec la clé recherchée ou atteindre la fin de l'arbre (dans ce cas, le nœud n'est pas trouvé).

Algorithme :

1. Si l'arbre est vide ou si la clé du nœud correspond à celle recherchée, retourner le nœud.
2. Si la clé du nœud recherché est inférieure, rechercher récursivement dans le sous-arbre gauche.
3. Si la clé du nœud recherché est supérieure, rechercher récursivement dans le sous-arbre droit.

3.4 Exemples de problèmes résolus à l'aide de BST

1. Recherche d'un élément dans un ensemble dynamique

Il est nécessaire de maintenir un ensemble de nombres dans lequel on peut ajouter de nouveaux éléments, supprimer les existants et rapidement vérifier si un nombre donné est présent dans l'ensemble.

Solution avec BST :

• Insertion de nouveaux éléments dans l'arbre.
• Suppression des éléments existants.
• Recherche des éléments dans l'arbre.

Exemple d'utilisation :

Maintien d'une liste des utilisateurs enregistrés dans un système, où des utilisateurs peuvent être ajoutés et supprimés, et le système doit rapidement vérifier si un utilisateur est enregistré.

2. Trouver l'élément minimal et maximal

Il est nécessaire de trouver rapidement les valeurs minimales et maximales dans un ensemble de données.

Solution avec BST :

• L'élément minimal se trouve dans le nœud le plus à gauche de l'arbre.
• L'élément maximal se trouve dans le nœud le plus à droite de l'arbre.

Exemple d'utilisation :

Maintien d'un système de suivi des prix des actions, où il est nécessaire de rapidement trouver le prix minimal et maximal à un moment donné.

3. Vérification de l'équilibre d'une expression

Étant donné une expression mathématique, il est nécessaire de vérifier son équilibre en termes de nombre de parenthèses ouvrantes et fermantes.

Solution avec BST :

Utiliser le BST pour stocker les états intermédiaires de la vérification de l'équilibre des parenthèses.

Exemple d'utilisation :

Analyse et compilation de code, où il est nécessaire de vérifier la bonne disposition des parenthèses dans les expressions.

4. Construction d'un dictionnaire

Il est nécessaire de créer une structure de données pour stocker un dictionnaire, dans lequel les mots peuvent être ajoutés, supprimés et rapidement trouvés.

Solution avec BST :

• Les mots sont ajoutés à l'arbre par ordre alphabétique.
• La recherche des mots s'effectue par clés.

Exemple d'utilisation :

Système de correction automatique de texte, où il est nécessaire de rapidement trouver et corriger les mots.