Les arbres binaires

Un arbre binaire est une structure de données arborescente dans laquelle chaque nœud peut avoir au plus deux enfants, appelés fils gauche et fils droit. Cette structure est largement utilisée en informatique pour organiser des données et optimiser des opérations comme la recherche, le tri et la manipulation d'expressions mathématiques.

Définition et représentation

Un arbre binaire est composé de nœuds, chacun contenant une valeur et des liens vers ses sous-arbres gauche et droit. En Python, on peut représenter un nœud de la manière suivante :

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

Chaque arbre binaire possède une racine, qui est le point d’entrée de la structure. À partir de cette racine, on peut parcourir l’arbre pour accéder aux différentes valeurs stockées.

Arbres binaires de recherche (ABR)

Un arbre binaire de recherche (ABR) est un type particulier d’arbre binaire où chaque nœud suit la règle suivante :

Toutes les valeurs du sous-arbre gauche sont inférieures à la valeur du nœud.
Toutes les valeurs du sous-arbre droit sont supérieures à la valeur du nœud.

Cette propriété permet d’effectuer des recherches efficacement, avec une complexité moyenne en $O(\log n)$ si l’arbre est équilibré.

Insertion dans un ABR

L’insertion d’un élément dans un ABR suit une approche récursive, où l’on descend dans l’arbre jusqu’à trouver une place libre :

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

Parcours d'un arbre binaire

Il existe plusieurs méthodes pour parcourir un arbre binaire, selon l'ordre dans lequel les nœuds sont visités :

Parcours en profondeur

Préfixe (racine → gauche → droite)

def prefixe(self, noeud):
    if noeud:
        print(noeud.data, end=" ")  # Racine
        self.prefixe(noeud.left)    # Sous-arbre gauche
        self.prefixe(noeud.right)   # Sous-arbre droit

Infixe (gauche → racine → droite)

def infixe(self, noeud):
    if noeud:
        self.infixe(noeud.left)     # Sous-arbre gauche
        print(noeud.data, end=" ")  # Racine
        self.infixe(noeud.right)    # Sous-arbre droit

Suffixe (gauche → droite → racine)

def suffixe(self, noeud):
    if noeud:
        self.suffixe(noeud.left)    # Sous-arbre gauche
        self.suffixe(noeud.right)   # Sous-arbre droit
        print(noeud.data, end=" ")  # Racine

Parcours en largeur

Le parcours en largeur explore l’arbre niveau par niveau, en utilisant une file :

from collections import deque

def parcours_largeur(racine):
    if racine is None:
        return
    file = deque([racine])
    while file:
        noeud = file.popleft()
        print(noeud.valeur, end=" ")
        if noeud.gauche:
            file.append(noeud.gauche)
        if noeud.droite:
            file.append(noeud.droite)

Exemple d'exécution

Considérons l’arbre suivant :

Représentation en Python :

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

racine = Noeud(1)
racine.gauche = Noeud(2)
racine.droite = Noeud(3)
racine.gauche.gauche = Noeud(4)
racine.gauche.droite = Noeud(5)
racine.droite.droite = Noeud(6)

parcours_largeur(racine)

Sortie :

1 2 3 4 5 6

On voit que le parcours en largeur explore l’arbre niveau par niveau :

Niveau 1 : 1
Niveau 2 : 2 3
Niveau 3 : 4 5 6

Problèmes et optimisations

Un problème fréquent avec les ABR est leur déséquilibre, qui peut entraîner une hauteur excessive et une dégradation des performances. Dans le pire cas, l’arbre devient une simple liste chaînée, et la recherche tombe en $O(n)$.

Pour éviter cela, on utilise des arbres équilibrés comme :

Les arbres AVL, qui rééquilibrent l’arbre après chaque insertion ou suppression.
Les arbres rouge-noir, qui garantissent une hauteur logarithmique en appliquant des rotations et des recolorisations.

Applications des arbres binaires

Les arbres binaires sont utilisés dans de nombreux domaines de l’informatique :

Bases de données : Les B-Trees sont utilisés pour indexer des données.
Compression de données : L’algorithme de Huffman utilise un arbre binaire pour coder efficacement des données.
Intelligence artificielle : Les arbres de décision permettent de modéliser des choix logiques.

Les arbres binaires

All work licensed under CC BY-NC-SA 4.0