Arbre binaire : définitions

Un arbre binaire est une structure hiérarchique où chaque nœud possède au plus deux enfants : un fils gauche et un fils droit. La terminologie essentielle :

• Racine (root) : le nœud sans parent, point d’entrée unique.
• Feuille (leaf) : un nœud sans enfant.
• Profondeur d’un nœud : nombre d’arêtes depuis la racine jusqu’à ce nœud.
• Hauteur de l’arbre : profondeur maximale parmi toutes les feuilles.

         10
        /  \
       5    15
      / \     \
     3   7    20

Un arbre binaire complet a tous ses niveaux remplis sauf éventuellement le dernier, qui est rempli de gauche à droite. Un arbre binaire parfait a tous ses niveaux complètement remplis.

Pour un arbre binaire de hauteur $h$ :

• Nombre maximal de nœuds : $2^{h+1} - 1$
• Nombre de nœuds à un niveau $k$ : au plus $2^k$
• Hauteur minimale pour $n$ nœuds (arbre complet) : $h = \lfloor \log_2 n \rfloor$

struct tree_node {
    int data;
    struct tree_node *left;
    struct tree_node *right;
};

L’overhead mémoire est de deux pointeurs par nœud (16 octets en 64 bits), auquel s’ajoute la donnée. Pour stocker un entier (4 octets), on utilise donc 20 octets minimum par nœud (avant padding), soit un overhead d’environ $O(5n)$, comparable à la liste doublement chaînée.

Parcours d’arbres

Le parcours d’un arbre binaire se fait soit en profondeur (DFS), soit en largeur (BFS). Le DFS existe sous trois variantes, définies par le moment où le nœud courant est traité par rapport à ses sous-arbres :

Parcours en profondeur (DFS), utilise une pile (implicite via la récursion) :

// Préfixe (preorder) : Nœud → Gauche → Droite
void preorder(struct tree_node *n) {
    if (!n) return;
    process(n->data);     // traiter le nœud
    preorder(n->left);
    preorder(n->right);
}

// Infixe (inorder) : Gauche → Nœud → Droite
void inorder(struct tree_node *n) {
    if (!n) return;
    inorder(n->left);
    process(n->data);     // sur un BST : ordre trié
    inorder(n->right);
}

// Postfixe (postorder) : Gauche → Droite → Nœud
void postorder(struct tree_node *n) {
    if (!n) return;
    postorder(n->left);
    postorder(n->right);
    process(n->data);     // libération mémoire, éval. expressions
}

Le parcours infixe est particulièrement important : appliqué à un arbre binaire de recherche, il produit les éléments en ordre croissant.

Parcours en largeur (BFS), utilise une file :

void bfs(struct tree_node *root) {
    struct queue *q = queue_new(1024);
    enqueue(q, root);
    while (q->size > 0) {
        struct tree_node *n = dequeue(q);
        process(n->data);
        if (n->left)  enqueue(q, n->left);
        if (n->right) enqueue(q, n->right);
    }
}

Ce parcours visite les nœuds niveau par niveau, de gauche à droite. Il est fondamental pour trouver le chemin le plus court dans un graphe non pondéré.

Tous ces parcours ont une complexité de $O(n)$ en temps (chaque nœud est visité une seule fois).

Arbre binaire de recherche (BST)

Un arbre binaire de recherche (Binary Search Tree) est un arbre binaire satisfaisant la propriété d’ordre : 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$

         10
        /  \
       5    15
      / \   / \
     3   7 12  20

La recherche suit une dichotomie naturelle :

struct tree_node *search(struct tree_node *root, int key) {
    if (root == NULL || root->data == key)
        return root;
    if (key < root->data)
        return search(root->left, key);
    return search(root->right, key);
}

L’insertion suit la même logique pour trouver la position correcte :

struct tree_node *insert(struct tree_node *root, int key) {
    if (root == NULL) {
        struct tree_node *n = (struct tree_node*)malloc(sizeof(struct tree_node));
        n->data = key;
        n->left = n->right = NULL;
        return n;
    }
    if (key < root->data)
        root->left = insert(root->left, key);
    else if (key > root->data)
        root->right = insert(root->right, key);
    return root;
}

Complexités :

Le pire cas en $O(n)$ survient lorsque l’arbre dégénère en liste chaînée (insertions dans l’ordre croissant ou décroissant). Insérer les éléments $1, 2, 3, 4, 5$ dans un BST produit :

1
 \
  2
   \
    3
     \
      4
       \
        5

La hauteur est alors $h = n - 1$ au lieu de $\lfloor \log_2 n \rfloor$. C’est ce problème fondamental que les arbres auto-équilibrés résolvent.

Arbre AVL

Un arbre AVL (Adelson-Velsky et Landis, 1962) est un BST auto-équilibré. Pour chaque nœud, le facteur d’équilibre est défini comme : $\text{bf}(N) = h(\text{gauche}) - h(\text{droite})$

La propriété AVL impose : $|\text{bf}(N)| \leq 1$ pour tout nœud $N$.

Lorsqu’une insertion ou suppression viole cette contrainte (facteur d’équilibre de $\pm 2$), on effectue des rotations pour rétablir l’équilibre. Il existe quatre cas :

Rotation simple droite (cas LL), le déséquilibre est causé par une insertion dans le sous-arbre gauche du fils gauche :

      z                  y
     / \               /   \
    y   T4    →       x     z
   / \               / \   / \
  x   T3            T1 T2 T3 T4
 / \
T1  T2

Rotation simple gauche (cas RR), symétrique du cas LL.

Double rotation gauche-droite (cas LR), insertion dans le sous-arbre droit du fils gauche : on effectue d’abord une rotation gauche sur le fils gauche, puis une rotation droite sur le nœud déséquilibré.

Double rotation droite-gauche (cas RL), symétrique du cas LR.

struct avl_node {
    int data;
    struct avl_node *left;
    struct avl_node *right;
    int height;
};

int height(struct avl_node *n) {
    return n ? n->height : 0;
}

int balance_factor(struct avl_node *n) {
    return n ? height(n->left) - height(n->right) : 0;
}

struct avl_node *rotate_right(struct avl_node *z) {
    struct avl_node *y = z->left;
    struct avl_node *T3 = y->right;
    y->right = z;
    z->left = T3;
    z->height = 1 + (height(z->left) > height(z->right) ? height(z->left) : height(z->right));
    y->height = 1 + (height(y->left) > height(y->right) ? height(y->left) : height(y->right));
    return y;
}

struct avl_node *rotate_left(struct avl_node *z) {
    struct avl_node *y = z->right;
    struct avl_node *T2 = y->left;
    y->left = z;
    z->right = T2;
    z->height = 1 + (height(z->left) > height(z->right) ? height(z->left) : height(z->right));
    y->height = 1 + (height(y->left) > height(y->right) ? height(y->left) : height(y->right));
    return y;
}

Après chaque insertion, on remonte la branche et on vérifie le facteur d’équilibre de chaque ancêtre. Si $|\text{bf}| = 2$, on identifie le cas (LL, RR, LR ou RL) et on applique la rotation appropriée.

Résultat : toutes les opérations (recherche, insertion, suppression) sont garanties en $O(\log n)$ dans le pire cas. La hauteur d’un arbre AVL de $n$ nœuds est bornée par $h < 1.44 \log_2(n+2)$, ce qui est très proche de l’optimum $\log_2 n$.

Le coût est une complexité d’implémentation accrue et un overhead d’un entier height par nœud. Les arbres Red-Black constituent une alternative (utilisés par std::map en C++) avec des contraintes d’équilibrage moins strictes mais des performances amorties similaires.

Tas binaire (Binary Heap)

Un tas binaire (binary heap) est un arbre binaire complet satisfaisant la propriété de tas :

• Min-heap : chaque nœud est $\leq$ ses enfants → la racine contient le minimum
• Max-heap : chaque nœud est $\geq$ ses enfants → la racine contient le maximum

La propriété fondamentale du tas est qu’il peut être stocké dans un simple tableau sans aucun pointeur, grâce à la complétude de l’arbre. Pour un nœud à l’indice $i$ (indexation à partir de 0) :

• Parent : $\lfloor (i - 1) / 2 \rfloor$
• Fils gauche : $2i + 1$
• Fils droit : $2i + 2$

Arbre :          1
               /   \
              3     5
             / \   /
            7   4 8

Tableau :   [ 1 | 3 | 5 | 7 | 4 | 8 ]
Indices :     0   1   2   3   4   5

Cette représentation en tableau est un point crucial : aucun pointeur, localité cache maximale, zéro overhead mémoire. C’est ce qui rend le tas supérieur au BST pour l’implémentation d’une file de priorité.

Insertion (sift up) : on ajoute l’élément à la fin du tableau (prochain emplacement libre dans l’arbre complet), puis on le fait “remonter” en l’échangeant avec son parent tant que la propriété de tas est violée.

void sift_up(int *heap, int i) {
    while (i > 0) {
        int parent = (i - 1) / 2;
        if (heap[i] >= heap[parent]) break; // min-heap
        int tmp = heap[i];
        heap[i] = heap[parent];
        heap[parent] = tmp;
        i = parent;
    }
}

void heap_insert(int *heap, int *size, int value) {
    heap[*size] = value;
    sift_up(heap, *size);
    (*size)++;
}

Complexité : $O(\log n)$, au plus $h$ échanges, où $h = \lfloor \log_2 n \rfloor$.

Extraction du minimum (sift down) : on remplace la racine par le dernier élément, puis on le fait “descendre” en l’échangeant avec le plus petit de ses fils tant que la propriété est violée.

void sift_down(int *heap, int size, int i) {
    while (1) {
        int smallest = i;
        int left = 2 * i + 1;
        int right = 2 * i + 2;
        if (left < size && heap[left] < heap[smallest])
            smallest = left;
        if (right < size && heap[right] < heap[smallest])
            smallest = right;
        if (smallest == i) break;
        int tmp = heap[i];
        heap[i] = heap[smallest];
        heap[smallest] = tmp;
        i = smallest;
    }
}

int heap_extract_min(int *heap, int *size) {
    int min = heap;
    heap = heap[--(*size)];
    sift_down(heap, *size, 0);
    return min;
}

Complexité : $O(\log n)$.

Construction d’un tas (heapify) : donné un tableau quelconque de $n$ éléments, on peut construire un tas en $O(n)$ (et non $O(n \log n)$) en appliquant sift_down à partir du dernier nœud non-feuille en remontant vers la racine.

void build_heap(int *arr, int n) {
    for (int i = n / 2 - 1; i >= 0; i--)
        sift_down(arr, n, i);
}

L’intuition est la suivante : les feuilles (la moitié des nœuds) n’ont pas besoin de sift_down. Les nœuds proches des feuilles descendent de très peu, tandis que seule la racine peut descendre de $\log n$. Le coût total est :

$\sum_{k=0}^{\lfloor \log n \rfloor} \left\lceil \frac{n}{2^{k+1}} \right\rceil \cdot O(k) = O\left(n \sum_{k=0}^{\infty} \frac{k}{2^k}\right) = O(n \cdot 2) = O(n)$

La série $\sum_{k=0}^{\infty} k / 2^k$ converge vers 2, d’où le résultat. C’est un résultat important et contre-intuitif.

Heap sort : on construit un max-heap en $O(n)$, puis on extrait successivement le maximum ($n$ extractions en $O(\log n)$ chacune), ce qui donne un tri en $O(n \log n)$ in-place et sans allocation supplémentaire.

B-Tree

Un B-Tree d’ordre $m$ est un arbre de recherche auto-équilibré conçu pour les systèmes de stockage à accès par blocs (disques, SSDs). Contrairement au BST qui stocke une clé par nœud, un nœud de B-Tree contient jusqu’à $m - 1$ clés et $m$ fils. Ce principe est directement lié à celui des unrolled linked lists : on regroupe plusieurs clés par nœud pour réduire les accès disque (ou cache misses).

Propriétés d’un B-Tree d’ordre $m$ :

• Chaque nœud interne contient entre $\lceil m/2 \rceil - 1$ et $m - 1$ clés.
• Chaque nœud interne (sauf la racine) a entre $\lceil m/2 \rceil$ et $m$ fils.
• Toutes les feuilles sont au même niveau, l’arbre est toujours parfaitement équilibré.
• Les clés dans chaque nœud sont triées.

B-Tree d'ordre 3 (chaque nœud contient 1 à 2 clés) :

              [10 | 20]
             /    |    \
        [3|7]  [12|15]  [25|30]

La hauteur d’un B-Tree contenant $n$ clés est : $h \leq \log_{\lceil m/2 \rceil} \frac{n+1}{2}$

Ce qui signifie que pour $m$ grand (typiquement 100-1000 dans les bases de données), l’arbre est extrêmement plat. Un B-Tree d’ordre 1000 contenant un milliard de clés n’a que 3 niveaux.

La variante B+Tree stocke toutes les données dans les feuilles (les nœuds internes ne contiennent que des clés de routage), et les feuilles sont chaînées entre elles. C’est la structure utilisée par la quasi-totalité des SGBD relationnels (PostgreSQL, MySQL/InnoDB) et des systèmes de fichiers (NTFS, ext4, Btrfs). Le chaînage des feuilles permet un parcours séquentiel efficace pour les requêtes de type WHERE x BETWEEN a AND b.

Le choix de l’ordre $m$ suit la même logique que le choix de $k$ pour les unrolled linked lists : on dimensionne le nœud pour qu’il tienne dans une page disque (typiquement 4 KB ou 8 KB) ou un multiple de la taille de ligne de cache, afin de minimiser les I/O.

Conclusion

Les structures abstraites (pile, file) sont des interfaces définies par leurs opérations, tandis que les structures concrètes (tableau, liste, tas, arbre) sont des implémentations. Le choix de l’implémentation dépend du profil d’accès et des contraintes matérielles.

L’arbre AVL garantit $O(\log n)$ strict au prix de rotations. Le tas binaire, stocké dans un tableau sans pointeur, est la structure optimale pour les files de priorité grâce à sa localité cache. Les B-Trees exploitent le même principe que les unrolled linked lists, regrouper les données par blocs, pour minimiser les accès I/O.

Le fil conducteur entre ces structures et celles du cours précédent reste le même : la localité mémoire et le ratio données/métadonnées sont souvent plus déterminants que la complexité asymptotique. Un tas binaire sur tableau (contiguïté parfaite, zéro pointeur) sera toujours plus rapide en pratique qu’un BST chaîné (fragmentation totale, 16 octets de pointeurs par nœud) malgré des complexités théoriques identiques.