Bonjour,
Dans la leçon précédente, nous avons achevé notre étude des opérations fondamentales sur les Arbres Binaires de Recherche (ABR) en implémentant l'algorithme de suppression. Nous avons formellement établi que la complexité des opérations clés (recherche, insertion, suppression) est en , où est la hauteur de l'arbre. Cette dépendance à la hauteur est une épée de Damoclès : excellente si l'arbre est équilibré (), mais désastreuse s'il dégénère ().
Aujourd'hui, nous nous attaquons frontalement à cette faiblesse. L'objectif est d'expliquer la problématique du déséquilibre d'un ABR et d'introduire le principe des arbres auto-équilibrants. Cette leçon est conceptuellement cruciale. Elle jette un pont entre la structure académique de l'ABR et les structures d'arbres performantes et robustes utilisées en pratique, telles que celles que vous pourriez avoir à analyser ou à discuter lors d'une épreuve de l'Agrégation.
1. La Problématique du Déséquilibre
La propriété fondamentale d'un ABR garantit une relation d'ordre, mais n'impose aucune contrainte sur sa structure. La forme de l'arbre, et donc sa hauteur, dépend exclusivement de l'ordre dans lequel les éléments sont insérés et supprimés.
Le problème est donc que la performance d'un ABR n'est pas garantie. Pour le même ensemble de clés, nous pouvons obtenir des arbres aux performances radicalement différentes.
La vidéo suivante illustre ce point de manière très concrète.
10.1 AVL Tree - Insertion and Rotations
La chaîne Abdul Bari, une référence pour l'enseignement de l'algorithmique, démontre ici comment la création d'un ABR avec le même jeu de clés, mais dans un ordre différent, produit un arbre équilibré puis un arbre complètement dégénéré.
Regardez la section de 03:45 à 07:51. Observez la construction des deux arbres. Le premier, construit à partir d'insertions dans un ordre mixte, est relativement compact et a une hauteur logarithmique. Le second, construit à partir de clés déjà triées, devient une longue chaîne linéaire de hauteur O(n). C'est l'illustration parfaite du problème.
En résumé, la problématique du déséquilibre est la suivante :
- Les opérations sur un ABR ont une complexité en .
- La hauteur n'est pas contrôlée et peut atteindre dans le pire des cas (par exemple, lors de l'insertion d'éléments déjà triés).
- Dans ce pire cas, l'ABR perd tout son avantage et se comporte comme une simple liste chaînée, avec des opérations en .
Le document suivant, tiré d'un cours de niveau universitaire, formalise bien cette idée.
Ce document de l'EECS de l'Université de York résume de manière concise la performance des ABR.
Lisez la diapositive 14, intitulée "Performance". Elle énonce clairement que la hauteur h est O(n) dans le pire cas et O(log n) dans le meilleur cas, et conclut par la phrase clé : "It is thus worthwhile to balance the tree".
2. Le Principe des Arbres Auto-Équilibrants
Comment garantir que la hauteur d'un arbre reste toujours proche de l'optimal, c'est-à-dire en , quelles que soient les insertions et suppressions ? La solution réside dans les arbres auto-équilibrants.
Le principe est le suivant : on définit une condition d'équilibre plus stricte que la simple propriété d'ABR. Après chaque opération de modification (insertion ou suppression) qui pourrait violer cette condition, on applique des transformations locales pour la restaurer.
Les Arbres AVL : un exemple canonique
L'un des premiers et des plus célèbres arbres auto-équilibrants est l'arbre AVL, du nom de ses inventeurs, Georgy Adelson-Velsky et Evgenii Landis (1962). Son principe est d'une grande clarté.
Définition (Facteur d'Équilibre)
Pour chaque nœud d'un arbre binaire, on définit son facteur d'équilibre (ou "déséquilibre") comme suit :
Par convention, la hauteur d'un arbre vide (un fils null) est -1.
Définition (Arbre AVL)
Un arbre AVL est un ABR qui satisfait la propriété AVL : pour chaque nœud de l'arbre, son facteur d'équilibre doit être dans l'ensemble .
En d'autres termes, les hauteurs des deux sous-arbres d'un même nœud ne peuvent différer de plus de 1.
[PDF] séance 6 Arbres binaires de recherche
Ce support de cours de l'ENSIMAG (Grenoble INP) définit formellement et en français la notion de déséquilibre, qui correspond au facteur d'équilibre.
Lisez la diapositive 17, intitulée "Définitions". Elle formalise le concept de "déséquilibre" d'un arbre et définit un arbre équilibré (et donc un AVL) comme un ABR où ce déséquilibre est toujours dans {-1, 0, 1}.
La vidéo suivante vous montre comment calculer ce facteur d'équilibre en pratique.
10.1 AVL Tree - Insertion and Rotations
Reprenons la vidéo d'Abdul Bari. Après avoir posé le problème, il introduit les arbres AVL et montre comment calculer le facteur d'équilibre pour chaque nœud.
Regardez la section de 13:59 à 17:37. Concentrez-vous sur la méthode de calcul du facteur d'équilibre. Observez comment il identifie les nœuds qui violent la propriété AVL (facteur d'équilibre de 2 ou -2).
La Garantie de Performance
L'intérêt de maintenir la propriété AVL est qu'elle garantit une hauteur logarithmique. On peut démontrer que la hauteur d'un arbre AVL à nœuds est en . La démonstration (que nous ne détaillerons pas ici, mais que vous pouvez consulter dans la ressource LINK, diapositive 27) établit un lien avec les nombres de Fibonacci et montre que même dans le cas le plus "déséquilibré" autorisé par la règle AVL, la hauteur croît logarithmiquement.
Cette garantie est la pierre angulaire de ces structures de données : en payant un léger surcoût pour maintenir l'équilibre, on s'assure que toutes les opérations resteront efficaces.
Le Mécanisme de Rééquilibrage : les Rotations
Lorsqu'une insertion ou une suppression provoque la violation de la propriété AVL (un nœud a un facteur d'équilibre de 2 ou -2), l'arbre doit être rééquilibré. Ce rééquilibrage se fait via des opérations locales appelées rotations.
Une rotation est une transformation simple et en temps constant qui réorganise un petit nombre de nœuds pour restaurer l'équilibre tout en préservant la propriété d'ABR.
10.1 AVL Tree - Insertion and Rotations
Pour conclure, voyons comment Abdul Bari introduit le concept de rotation comme solution au déséquilibre.
Regardez la section de 07:51 à 12:49. L'idée principale n'est pas de comprendre les détails des rotations, mais de saisir le principe : en réarrangeant localement 3 nœuds, on peut transformer une structure haute et fine en une structure plus compacte et moins haute, ce qui a pour effet de restaurer l'équilibre.
Il existe quatre types de déséquilibre qui nécessitent des rotations pour être corrigés (un déséquilibre "gauche-gauche", "gauche-droite", "droite-droite", "droite-gauche"). Nous étudierons en détail ces quatre cas et les rotations associées (simples et doubles) dans notre prochaine leçon.
Conclusion
Aujourd'hui, nous avons formalisé une limitation critique des ABR simples et esquissé la solution élégante apportée par les arbres auto-équilibrants.
Points clés à retenir :
- La problématique : La performance d'un ABR dépend de sa hauteur, qui peut dégénérer en en fonction de l'ordre des opérations, annulant ainsi son avantage sur des structures linéaires.
- Le principe : Les arbres auto-équilibrants maintiennent une condition d'équilibre stricte pour garantir une hauteur logarithmique, et donc des opérations en .
- L'exemple de l'AVL : L'arbre AVL impose que le facteur d'équilibre (différence de hauteur des sous-arbres) de chaque nœud soit dans .
- Le mécanisme : La condition d'équilibre est maintenue grâce à des opérations de rotation, qui sont des réarrangements locaux en temps constant.
- Le compromis : On accepte un surcoût algorithmique mineur à l'insertion et à la suppression pour garantir des performances logarithmiques sur toutes les opérations.
Il est important de noter que les arbres AVL ne sont qu'un exemple. D'autres structures comme les arbres rouge-noir (utilisés dans les bibliothèques standard de C++ et Java) ou les arbres Splay résolvent le même problème avec des invariants et des compromis différents. Connaître leur existence est essentiel pour un futur agrégé.
Prochaine étape :
Maintenant que nous avons compris le "pourquoi" et le "quoi", nous allons nous plonger dans le "comment". Dans la prochaine leçon, nous étudierons en détail les mécanismes de rotation des arbres AVL. Nous apprendrons à identifier les cas de déséquilibre et à appliquer les rotations simples et doubles pour restaurer la propriété AVL, avec des exemples concrets.