Contenu du cours

1. Introduction aux Arbres Binaires de Recherche

Un Arbre Binaire de Recherche (ABR) est une structure de données fondamentale en informatique qui permet de stocker et organiser des données de manière hiérarchique tout en permettant des opérations efficaces.

Exemple visuel :

                8
               / \
              3   10
             / \   \
            1   6   14
               / \  /
              4  7 13

Analogies pour débutants :

  • Comme un arbre généalogique où chaque personne a au plus deux enfants
  • Comme un système de classement où les éléments plus petits vont à gauche, les plus grands à droite
À retenir : Les ABR combinent les avantages des listes chaînées (insertion/suppression rapide) et des tableaux triés (recherche efficace).

2. Définition et Propriétés Fondamentales

Un ABR est un arbre binaire qui respecte les propriétés suivantes :

Propriétés formelles : 1. Pour tout nœud N : - Tous les nœuds du sous-arbre gauche ont une valeur ≤ N - Tous les nœuds du sous-arbre droit ont une valeur > N 2. Les sous-arbres gauche et droit sont eux-mêmes des ABR

Exemple valide :

                5
               / \
              3   7
             / \   \
            2   4   8

Exemple invalide :

                5
               / \
              3   7
             / \   \
            2   6   8  # 6 > 5 (violation)

3. Représentation en Mémoire (Structure de Nœuds)

En Python, on représente généralement un nœud ainsi :

class Noeud: def __init__(self, valeur): self.valeur = valeur self.gauche = None self.droit = None

Exemple concret :

# Création manuelle d'un petit ABR racine = Noeud(10) racine.gauche = Noeud(5) racine.droit = Noeud(15) racine.gauche.droit = Noeud(7) # Structure résultante : # 10 # / \ # 5 15 # \ # 7

4. Parcours d'un ABR

Il existe trois principaux types de parcours :

# Parcours infixe (gauche-racine-droit) - donne les valeurs triées def parcours_infixe(noeud): if noeud is not None: parcours_infixe(noeud.gauche) print(noeud.valeur) parcours_infixe(noeud.droit) # Parcours préfixe (racine-gauche-droit) # Parcours postfixe (gauche-droit-racine)

Exemple : Pour l'arbre suivant :

                4
               / \
              2   6
             / \ / \
            1  3 5 7
  • Infixe : 1, 2, 3, 4, 5, 6, 7 (ordre croissant)
  • Préfixe : 4, 2, 1, 3, 6, 5, 7
  • Postfixe : 1, 3, 2, 5, 7, 6, 4

5. Opération d'Insertion

Algorithme récursif d'insertion :

def inserer(racine, valeur): if racine is None: return Noeud(valeur) if valeur <= racine.valeur: racine.gauche = inserer(racine.gauche, valeur) else: racine.droit = inserer(racine.droit, valeur) return racine

Exemple d'insertion de la valeur 9 :

Avant :       Après :
      8             8
     / \           / \
    3   10        3   10
   / \   \       / \   \
  1   6   14    1   6   14
     / \  /       / \  / \
    4  7 13      4  7 13 9

6. Opération de Recherche

Algorithme de recherche :

def rechercher(racine, valeur): if racine is None: return False if racine.valeur == valeur: return True if valeur < racine.valeur: return rechercher(racine.gauche, valeur) else: return rechercher(racine.droit, valeur)
Complexité : En moyenne O(log n) si l'arbre est équilibré, O(n) dans le pire cas (arbre dégénéré).

Exemple visuel de recherche :

Exemple de recherche dans un ABR

7. Opération de Suppression

Trois cas à considérer :

  1. Le nœud est une feuille (suppression directe)
  2. Le nœud a un seul enfant (remplacement par l'enfant)
  3. Le nœud a deux enfants (remplacement par le successeur infixe)
def supprimer(racine, valeur): if racine is None: return racine if valeur < racine.valeur: racine.gauche = supprimer(racine.gauche, valeur) elif valeur > racine.valeur: racine.droit = supprimer(racine.droit, valeur) else: # Cas 1: Feuille ou un seul enfant if racine.gauche is None: return racine.droit elif racine.droit is None: return racine.gauche # Cas 2: Deux enfants temp = trouver_min(racine.droit) racine.valeur = temp.valeur racine.droit = supprimer(racine.droit, temp.valeur) return racine

8. Complexité Algorithmique

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

Visualisation des complexités :

Graphique de complexité des ABR
Astuce : Pour garantir O(log n), utiliser des ABR équilibrés (AVL, Rouge-Noir).
Contact

Apprenez à coder en ligne, où vous voulez, quand vous voulez.

Cours

Cours

Conception et développement Rachid Saad