Arbres binaires de recherche et arbres équilibrés

Informatique de gestion · Bachelor 2

Insertion, recherche et parcours dans un ABR, dégénérescence et rééquilibrage AVL.

Introduction

Un arbre binaire de recherche (ABR) organise des clés comparables de sorte que, pour chaque noeud, toutes les clés du sous-arbre gauche sont plus petites et toutes celles du sous-arbre droit plus grandes. Cette propriété permet de rechercher, insérer et supprimer en parcourant un seul chemin de la racine vers une feuille : le coût est proportionnel à la hauteur de l'arbre.

Si les clés arrivent dans l'ordre croissant, l'arbre dégénère en liste chaînée de hauteur n et les opérations coûtent O(n). Les arbres équilibrés, comme les arbres AVL ou rouge-noir, maintiennent une hauteur en O(log n) grâce à des rotations après chaque modification. Les bases de données utilisent des variantes à plusieurs enfants par noeud, les arbres B, pour indexer des tables sur disque.

Le parcours infixe d'un ABR restitue les clés dans l'ordre croissant, ce qui en fait une structure adaptée aux listes triées dynamiques et aux recherches par intervalle, par exemple les factures dont le montant se situe entre deux bornes.

Objectifs d'apprentissage

Énoncer la propriété d'un arbre binaire de recherche
Dérouler recherche, insertion et suppression sur un exemple
Effectuer un parcours infixe, préfixe et postfixe
Expliquer la dégénérescence et le rôle de la hauteur dans la complexité
Décrire le principe d'équilibrage d'un arbre AVL par rotations

Concepts clés

Propriété d'ABR: Pour chaque noeud, clés du sous-arbre gauche < clé du noeud < clés du sous-arbre droit.
Parcours: Infixe (gauche, racine, droite) donne l'ordre croissant ; préfixe visite la racine d'abord ; postfixe visite la racine en dernier.
Hauteur et complexité: Les opérations coûtent O(h) ; h vaut environ log n si l'arbre est équilibré, jusqu'à n s'il dégénère.
Arbre AVL: Arbre dont la différence de hauteur entre sous-arbres gauche et droit de tout noeud est au plus 1 ; des rotations rétablissent l'équilibre.

Conclusion

Les arbres binaires de recherche illustrent le lien entre structure et performance : tout dépend de la hauteur. Les variantes équilibrées garantissent un comportement logarithmique quel que soit l'ordre d'arrivée des données.

Cette compréhension prépare à celle des index de bases de données, indispensables en informatique de gestion.

Cartes

Quelle est la propriété d'un ABR ?: Clés du sous-arbre gauche inférieures à la racine, clés du sous-arbre droit supérieures, pour tous les noeuds.
Comment rechercher une clé dans un ABR ?: Comparer à la racine : aller à gauche si plus petite, à droite si plus grande, jusqu'à trouver ou atteindre un vide.
Quel parcours donne les clés triées ?: Le parcours infixe : sous-arbre gauche, noeud, sous-arbre droit.
Quand un ABR dégénère-t-il ?: Quand les clés sont insérées dans l'ordre croissant ou décroissant : l'arbre devient une liste de hauteur n.
Quelle est la complexité d'une recherche dans un ABR équilibré ?: O(log n), car la hauteur est logarithmique.
Comment supprimer un noeud à deux enfants ?: Le remplacer par son successeur infixe (plus petite clé du sous-arbre droit) ou son prédécesseur, puis supprimer ce dernier.
Qu'est-ce qu'un arbre AVL ?: Un ABR auto-équilibré où, pour chaque noeud, les hauteurs des deux sous-arbres diffèrent d'au plus 1.
Que fait une rotation ?: Elle réorganise localement quelques noeuds pour réduire la hauteur tout en conservant l'ordre des clés.
Pourquoi les bases de données utilisent-elles des arbres B ?: Chaque noeud contient de nombreuses clés, ce qui réduit le nombre d'accès disque nécessaires pour atteindre une valeur.
Quand préférer un ABR équilibré à une table de hachage ?: Quand on a besoin de l'ordre : parcours trié, minimum et maximum, recherche par intervalle.

Glossaire

Noeud: Élément de l'arbre contenant une clé et des références vers ses enfants.
Feuille: Noeud sans enfant.
Hauteur: Longueur du plus long chemin de la racine à une feuille.
Parcours infixe: Visite gauche, noeud, droite, qui produit les clés dans l'ordre croissant.
Facteur d'équilibre: Différence de hauteur entre sous-arbres gauche et droit d'un noeud.
Rotation: Transformation locale qui rééquilibre un arbre en préservant l'ordre.