07 — Arbres : Cours complet

Niveau : Université / Ingénierie — Durée de lecture : ~60 min

---

Table des matières

1. Terminologie et représentations
2. Traversals : préfixe, infixe, suffixe, BFS
3. ABR — Binary Search Tree
4. AVL : auto-équilibrage par rotations
5. Arbres Rouge-Noir
6. B-Tree : arbres pour le disque
7. Tas binaire : heapify et heap sort
8. Segment Tree et Fenwick
9. Trie : arbres de préfixes
10. Applications
11. Résumé

---

1. Terminologie et représentations

1.1 Définitions

• Nœud : élément portant une clé (et des valeurs).
• Racine : nœud sans parent.
• Enfants / Parent : relations directes ; feuille : nœud sans enfant.
• Profondeur d'un nœud : distance à la racine. Hauteur d'un arbre : profondeur maximale.
• Arbre binaire : chaque nœud a au plus 2 enfants (gauche/droit).

Diagramme en cours de génération...

Hauteur = 3 (racine → 13). Profondeur de 11 = 2. Feuilles : 3, 13, 18.

1.2 Représentation par nœuds

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

• Java : Node avec left, right ; Java TreeMap utilise un nœud Rouge-Noir.
• C++ : struct Node { int key; Node *left, *right; };
• Go : type Node struct { Key int; Left, Right *Node }.
• TypeScript : interface TreeNode { key: number; left?: TreeNode; right?: TreeNode }.

1.3 Représentation par tableau (tas, segment tree)

Les nœuds sont indexés 0..n-1 : enfants de i = 2i+1, 2i+2 ; parent = (i-1)/2.

Diagramme en cours de génération...

---

2. Traversals : préfixe, infixe, suffixe, BFS

2.1 Parcours en profondeur (DFS)

def prefixe(n):
    if n:
        print(n.cle, end=" ")
        prefixe(n.gauche)
        prefixe(n.droit)

def infixe(n):
    if n:
        infixe(n.gauche)
        print(n.cle, end=" ")
        infixe(n.droit)

def suffixe(n):
    if n:
        suffixe(n.gauche)
        suffixe(n.droit)
        print(n.cle, end=" ")

Version itérative de l'infixe (pile explicite, chapitre 05) :

def infixe_iteratif(n):
    pile, courant = [], n
    while pile or courant:
        while courant:
            pile.append(courant)
            courant = courant.gauche
        courant = pile.pop()
        print(courant.cle, end=" ")
        courant = courant.droit

2.2 Parcours en largeur (BFS)

from collections import deque

def bfs(n):
    if not n:
        return
    file = deque([n])
    while file:
        x = file.popleft()
        print(x.cle, end=" ")
        if x.gauche:
            file.append(x.gauche)
        if x.droit:
            file.append(x.droit)

Ordre de l'exemple 1 : BFS → 15, 7, 22, 3, 11, 18, 13.

---

3. ABR — Binary Search Tree

3.1 Invariant

Pour tout nœud : toutes les clés du sous-arbre gauche < clé du nœud < toutes les clés du sous-arbre droit.

Diagramme en cours de génération...

3.2 Recherche — O(h)

def chercher(n, cle):
    if n is None or n.cle == cle:
        return n
    if cle < n.cle:
        return chercher(n.gauche, cle)
    return chercher(n.droit, cle)

À chaque étape on élimine la moitié du sous-arbre : coût O(h) = O(log n) si l'arbre est équilibré, O(n) s'il dégénère (clés insérées triées).

3.3 Insertion — O(h)

def inserer(n, cle):
    if n is None:
        return Noeud(cle)
    if cle < n.cle:
        n.gauche = inserer(n.gauche, cle)
    elif cle > n.cle:
        n.droit = inserer(n.droit, cle)
    return n

Insérer 1, 2, 3, 4, 5 dans cet ordre → arbre filiforme (hauteur n) → O(n) par recherche ! C'est ce qui motive les arbres équilibrés (§4-5).

3.4 Suppression — O(h)

Trois cas :

1. Feuille : on détache le nœud.
2. Un enfant : on remplace le nœud par son enfant.
3. Deux enfants : on remplace par le successeur (min du sous-arbre droit) ou le prédécesseur, puis on supprime ce nœud.

def supprimer(n, cle):
    if n is None:
        return None
    if cle < n.cle:
        n.gauche = supprimer(n.gauche, cle)
    elif cle > n.cle:
        n.droit = supprimer(n.droit, cle)
    else:
        if n.gauche is None:
            return n.droit
        if n.droit is None:
            return n.gauche
        s = n.droit
        while s.gauche:
            s = s.gauche          # successeur : min du droit
        n.cle = s.cle
        n.droit = supprimer(n.droit, s.cle)
    return n

3.5 Complexités (ABR non équilibré)

---

4. AVL : auto-équilibrage par rotations

4.1 Invariant de hauteur

Chaque nœud stocke un facteur d'équilibre bf = hauteur(droit) − hauteur(gauche) ∈ {−1, 0, +1}.

Diagramme en cours de génération...

4.2 Rotations

Quatre cas, nommés selon le chemin de déséquilibre :

Diagramme en cours de génération...

Rotation droite sur 10 : 5 devient racine, 6 (=droit de 5) devient gauche de 10.

4.3 Insertion AVL — O(log n)

def rotation_droite(y):
    x = y.gauche
    t2 = x.droit
    x.droit = y
    y.gauche = t2
    return x

def rotation_gauche(x):
    y = x.droit
    t2 = y.gauche
    y.gauche = x
    x.droit = t2
    return y

def inserer_avl(n, cle):
    if n is None:
        return NoeudAVL(cle)
    if cle < n.cle:
        n.gauche = inserer_avl(n.gauche, cle)
    else:
        n.droit = inserer_avl(n.droit, cle)
    n.hauteur = 1 + max(hauteur(n.gauche), hauteur(n.droit))
    bf = hauteur(n.droit) - hauteur(n.gauche)
    if bf > 1 and cle > n.droit.cle:
        return rotation_gauche(n)                 # RR
    if bf < -1 and cle < n.gauche.cle:
        return rotation_droite(n)                 # LL
    if bf > 1 and cle < n.droit.cle:
        n.droit = rotation_droite(n.droit)        # RL
        return rotation_gauche(n)
    if bf < -1 and cle > n.gauche.cle:
        n.gauche = rotation_gauche(n.gauche)      # LR
        return rotation_droite(n)
    return n

4.4 Propriété clé

La hauteur d'un AVL à n nœuds est toujours O(log n) (au pire ~1,44 log₂ n). Toutes les opérations sont donc O(log n) garanti.

---

5. Arbres Rouge-Noir

5.1 Règles

1. Chaque nœud est rouge ou noir.
2. La racine est noire.
3. Toutes les feuilles (NIL) sont noires.
4. Un rouge n'a pas d'enfant rouge (pas deux rouges consécutifs).
5. Tous les chemins racine → feuille ont le même nombre de nœuds noirs (black-height).

Diagramme en cours de génération...

5.2 Pourquoi

• Hauteur ≤ 2·black-height → O(log n) garanti.
• Moins de rotations qu'un AVL sur l'insertion (au plus 2 rotations, plus des recoloriages) → meilleur pour les écritures fréquentes.
• Utilisés dans : Java TreeMap/TreeSet, C++ std::map/std::set, noyau Linux (CFS scheduler), implémentation des seaux de Java HashMap (> 8 éléments, chapitre 06).

5.3 AVL vs Rouge-Noir

---

6. B-Tree : arbres pour le disque

6.1 Principe

Un B-Tree d'ordre t : chaque nœud contient jusqu'à 2t−1 clés et jusqu'à 2t enfants.

Diagramme en cours de génération...

6.2 Pourquoi

• Une lecture disque coûte ~10⁶× plus qu'une lecture mémoire. Un B-Tree de facteur de branchement élevé a une hauteur de 3-4 pour des milliards de clés → peu d'accès disque.
• Les index des bases de données (MySQL InnoDB, PostgreSQL, MongoDB, SQLite) sont des B+Tree (variante où seules les feuilles portent les valeurs, chaînées entre elles).

6.3 B+Tree en SQL

CREATE INDEX idx_users_email ON users(email);

La requête SELECT * FROM users WHERE email = 'x@y.z' descend l'index : O(log_t n) accès disque, chaque nœud faisant la taille d'une page (4-16 Ko).

---

7. Tas binaire : heapify et heap sort

7.1 Rappels (chapitre 05)

Tas min/max : arbre binaire complet dans un tableau ; push et extract_min en O(log n).

7.2 Heapify — construire un tas en O(n)

def tamiser(tab, i, n):
    while True:
        g, d = 2 * i + 1, 2 * i + 2
        p = i
        if g < n and tab[g] > tab[p]:
            p = g
        if d < n and tab[d] > tab[p]:
            p = d
        if p == i:
            return
        tab[i], tab[p] = tab[p], tab[i]
        i = p

def construire_tas_max(tab):
    n = len(tab)
    for i in range(n // 2 - 1, -1, -1):
        tamiser(tab, i, n)

Pourquoi O(n) : seuls les nœuds non-feuilles sont tamisés ; le tamisage d'un nœud à profondeur h coûte O(h) et il y a n/2^(h+1) nœuds à cette profondeur. Σ = O(n).

7.3 Heap sort — O(n log n) en place

def tri_tas(tab):
    n = len(tab)
    construire_tas_max(tab)
    for fin in range(n - 1, 0, -1):
        tab[0], tab[fin] = tab[fin], tab[0]   # max en place
        tamiser(tab, 0, fin)
    return tab

• En place (O(1) mémoire supplémentaire), instable, O(n log n) pire cas garanti.
• C'est le tri de la file de priorité : heapq Python, std::priority_queue C++, PriorityQueue Java.
• En pratique Python sorted (Timsort) et Java/C++ sort (introsort) sont plus rapides grâce à la localité de cache.

7.4 Comparaison des tris

---

8. Segment Tree et Fenwick

8.1 Problème

Soit un tableau ; on veut répondre à des requêtes de plage (ex. somme ou min sur [l, r]) avec mises à jour ponctuelles. Naïf : O(n) par requête. Objectif : O(log n) les deux.

8.2 Segment Tree

Arbre binaire où chaque nœud stocke l'opération (somme, min, max, xor…) sur un segment du tableau.

Diagramme en cours de génération...

• Requête de somme : O(log n) (on combine O(log n) nœuds).
• Mise à jour d'un élément : O(log n) (on remonte la chaîne de la feuille à la racine).
• Tableau de taille 4n. Facile à généraliser : min, max, GCD, produit, opérations combinables.

class SegmentTree:
    def __init__(self, tab):
        self.n = len(tab)
        self.tree = [0] * (4 * self.n)
        self._build(tab, 1, 0, self.n - 1)

    def _build(self, tab, noeud, l, r):
        if l == r:
            self.tree[noeud] = tab[l]
            return
        m = (l + r) // 2
        self._build(tab, 2 * noeud, l, m)
        self._build(tab, 2 * noeud + 1, m + 1, r)
        self.tree[noeud] = self.tree[2 * noeud] + self.tree[2 * noeud + 1]

    def _query(self, noeud, l, r, ql, qr):
        if ql <= l and r <= qr:
            return self.tree[noeud]
        if r < ql or qr < l:
            return 0
        m = (l + r) // 2
        return (self._query(2 * noeud, l, m, ql, qr)
                + self._query(2 * noeud + 1, m + 1, r, ql, qr))

    def somme(self, l, r):
        return self._query(1, 0, self.n - 1, l, r)

8.3 Fenwick / BIT

Le Binary Indexed Tree utilise les bits du plus petit 1 (i & -i) pour stocker des sommes préfixes partielles.

class Fenwick:
    def __init__(self, n):
        self.n = n
        self.tree = [0] * (n + 1)      # indices 1..n

    def ajouter(self, i, delta):       # mise à jour : i → n
        while i <= self.n:
            self.tree[i] += delta
            i += i & -i

    def prefixe(self, i):              # somme [1..i]
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s

    def somme(self, l, r):             # [l..r]
        return self.prefixe(r) - self.prefixe(l - 1)

• Plus simple et plus économe que le Segment Tree (tableau n+1, pas 4n).
• Restreint aux opérations inversibles (somme, xor) ; le Segment Tree gère min/max.
• Nombre d'inversions : comptage classique — on insère les éléments un à un en comptant les plus grands déjà vus.

---

9. Trie : arbres de préfixes

9.1 Principe

Un Trie (prononcé « try ») stocke des chaînes nœud à nœud : chaque chemin racine → nœud forme un préfixe.

Diagramme en cours de génération...

Mots : cat, cot, too, bob. * marque la fin d'un mot.

9.2 Opérations

class NoeudTrie:
    def __init__(self):
        self.enfants = {}
        self.fin_de_mot = False

class Trie:
    def __init__(self):
        self.racine = NoeudTrie()

    def inserer(self, mot):
        n = self.racine
        for c in mot:
            n = n.enfants.setdefault(c, NoeudTrie())
        n.fin_de_mot = True

    def chercher(self, mot):
        n = self.racine
        for c in mot:
            if c not in n.enfants:
                return False
            n = n.enfants[c]
        return n.fin_de_mot

    def commence_par(self, prefixe):
        n = self.racine
        for c in prefixe:
            if c not in n.enfants:
                return False
            n = n.enfants[c]
        return True

9.3 Analyse

• Insertion/recherche : O(L) où L = longueur du mot (indépendant du nombre de mots !).
• Mémoire : O(total des caractères) — mais coûteux si beaucoup de mots courts et peu de préfixes communs (compacter en Patricia/Radix tree).
• Usages : autocomplétion, correcteur orthographique, prédiction de touches, IP routing (longest prefix match), compression.

---

10. Applications

10.1 Arbre d'expression

Diagramme en cours de génération...

Le traversal suffixe évalue : 3 4 * 2 + = 14 (même exemple que le chapitre 05).

10.2 Compilateurs

L'AST (Abstract Syntax Tree) est au cœur de tous les compilateurs et interprètes. python -c "import ast; ast.dump(ast.parse('a + b'))" affiche l'arbre.

---

11. Résumé

1. Terminologie : racine, enfant, feuille, hauteur ; tableau vs nœuds.
2. Traversals : préfixe, infixe (ABR → trié), suffixe (évaluation), BFS (file).
3. ABR : O(h) ; dégénère en O(n) si inséré trié.
4. AVL : |bf| ≤ 1, rotations LL/RR/LR/RL → O(log n) garanti, recherche rapide.
5. Rouge-Noir : 5 règles, moins de rotations, TreeMap/std::map/HashMap buckets.
6. B-Tree/B+Tree : multi-clés, hauteur 3-4 sur disque, index SQL.
7. Tas : heapify O(n), heap sort O(n log n) en place, PQ.
8. Segment Tree / Fenwick : requêtes de plage + mise à jour en O(log n) ; Fenwick plus léger, segment tree plus général.
9. Trie : O(L) par opération, autocomplétion, routing.

---

Exercices d'auto-évaluation

1. Pourquoi insérer des clés déjà triées dans un ABR le dégénère-t-il en liste ?
2. Donner le traversal infixe de l'arbre du §3.1.
3. Quelles rotations pour un déséquilibre LR ? RL ?
4. Différence de hauteur garantie entre AVL et Rouge-Noir ?
5. Pourquoi heapify est O(n) et pas O(n log n) ?
6. Quand préférer Fenwick à Segment Tree ? Et l'inverse ?
7. Complexité de chercher dans un Trie pour un mot de 10 lettres et 10⁶ mots stockés ?

Passez au quiz puis aux TP.