Aller au contenu principal

Arbres binaires de recherche

#Arbres binaires de recherche (BST)

Un arbre binaire de recherche (Binary Search Tree - BST) est un arbre binaire où chaque nœud respecte la propriété de recherche : la valeur de chaque nœud est supérieure à toutes les valeurs de son sous-arbre gauche et inférieure à toutes les valeurs de son sous-arbre droit.

#Propriété fondamentale

Pour chaque nœud N :

  • Toutes les valeurs dans le sous-arbre gauche de N sont < valeur(N)
  • Toutes les valeurs dans le sous-arbre droit de N sont > valeur(N)
  • Cette propriété s'applique récursivement à tous les sous-arbres

#Animation interactive

Voici une animation qui illustre le fonctionnement d'un arbre binaire de recherche :

Arbre vide
Arbre binaire de recherche vide
Vitesse:1100ms
Étape 1 / 1

#Opérations principales

#Recherche

La recherche dans un BST est efficace grâce à la propriété de recherche :

pythonpython
1class Noeud:2    def __init__(self, valeur):3        self.valeur = valeur4        self.gauche = None5        self.droit = None6 7def rechercher(noeud, valeur):8    # Cas de base : arbre vide ou valeur trouvée9    if noeud is None or noeud.valeur == valeur:10        return noeud11    12    # Si la valeur est plus petite, rechercher dans le sous-arbre gauche13    if valeur < noeud.valeur:14        return rechercher(noeud.gauche, valeur)

#Insertion

L'insertion suit le même principe que la recherche :

pythonpython
1def inserer(noeud, valeur):2    # Si l'arbre est vide, créer un nouveau nœud3    if noeud is None:4        return Noeud(valeur)5    6    # Sinon, insérer récursivement dans le sous-arbre approprié7    if valeur < noeud.valeur:8        noeud.gauche = inserer(noeud.gauche, valeur)9    elif valeur > noeud.valeur:10        noeud.droit = inserer(noeud.droit, valeur)11    # Si valeur == noeud.valeur, on ne fait rien (pas de doublons)12    13    return noeud14

#Suppression

La suppression est plus complexe car elle doit maintenir la propriété de BST :

pythonpython
1def supprimer(noeud, valeur):2    # Cas de base : arbre vide3    if noeud is None:4        return noeud5    6    # Si la valeur à supprimer est plus petite, aller à gauche7    if valeur < noeud.valeur:8        noeud.gauche = supprimer(noeud.gauche, valeur)9    # Si la valeur à supprimer est plus grande, aller à droite10    elif valeur > noeud.valeur:11        noeud.droit = supprimer(noeud.droit, valeur)12    else:13        # Valeur trouvée, c'est le nœud à supprimer14

#Parcours

Les parcours d'arbres binaires de recherche produisent des séquences ordonnées :

pythonpython
1def parcours_infixe(noeud):2    """Parcours infixé : gauche, racine, droit (ordonné)"""3    if noeud:4        parcours_infixe(noeud.gauche)5        print(noeud.valeur, end=' ')6        parcours_infixe(noeud.droit)7 8def parcours_prefixe(noeud):9    """Parcours préfixé : racine, gauche, droit"""10    if noeud:11        print(noeud.valeur, end=' ')12        parcours_prefixe(noeud.gauche)13        parcours_prefixe(noeud.droit)14

#Complexité

| Opération | Meilleur cas | Cas moyen | Pire cas | |-----------|--------------|-----------|----------| | Recherche | O(log n) | O(log n) | O(n) | | Insertion | O(log n) | O(log n) | O(n) | | Suppression | O(log n) | O(log n) | O(n) |

Le pire cas O(n) se produit quand l'arbre est dégénéré en une liste (par exemple, si les valeurs sont insérées en ordre croissant).

#Exercice : Vérifier si un arbre est un BST

Implémentez une fonction qui vérifie si un arbre binaire est un arbre binaire de recherche valide.

#Instructions

  1. Créez une fonction est_bst(noeud, min_val, max_val) qui vérifie si un arbre est un BST.
  2. Utilisez des bornes pour vérifier que chaque nœud respecte les contraintes.
  3. Un nœud est valide s'il est dans les bornes et si ses sous-arbres sont valides.

#Exemple de code

pythonpython
1class Noeud:2    def __init__(self, valeur):3        self.valeur = valeur4        self.gauche = None5        self.droit = None6 7def est_bst(noeud, min_val=float('-inf'), max_val=float('inf')):8    # Un arbre vide est un BST9    if noeud is None:10        return True11    12    # Vérifier si la valeur du nœud est dans les bornes13    if not (min_val < noeud.valeur < max_val):14        return False

#Applications

  1. Dictionnaires et ensembles : Pour stocker des paires clé-valeur avec recherche rapide
  2. Intervalles : Pour stocker des intervalles avec recherche efficace
  3. Expressions : Pour représenter des expressions arithmétiques
  4. Compression : Dans les algorithmes de compression comme Huffman

Les arbres binaires de recherche sont une structure de données fondamentale qui combine les avantages des tableaux (recherche ordonnée) et des listes (insertion/suppression efficace).