Visualiseur d'arbres BST / AVL

Les arbres de recherche binaires imposent une organisation hiérarchique stricte, garantissant que les nœuds enfants de gauche détiennent des valeurs moindres. Les arbres AVL améliorent cela en appliquant algorithmiquement une différence de hauteur maximale de un entre les sous-arbres. Cet auto-équilibrage mathématique nécessite des transformations de rotation précises lors de l'insertion ou de la suppression. De telles contraintes structurelles garantissent que les opérations de recherche, d'insertion et de suppression restent limitées par une complexité temporelle O(log n), optimisant ainsi la récupération rapide des données.

Un arbre binaire de recherche fonctionne comme la recherche d'un mot dans un dictionnaire : à chaque nœud, tu compares puis écartes aussitôt toute la moitié qui ne peut pas contenir ta valeur. C'est pourquoi un arbre bien formé retrouve n'importe quelle valeur parmi un million d'entrées en environ 20 comparaisons. Mais la forme dépend entièrement de l'ordre d'insertion : saisis les valeurs déjà triées (10, 20, 30, …) et regarde l'arbre s'effondrer en une seule ligne penchée, pas plus rapide qu'un parcours de liste un par un.

Passe en mode AVL et demande-toi : quelle hauteur maximale un arbre équilibré peut-il atteindre pour un nombre donné de nœuds ? La réponse cache le nombre d'or. L'arbre AVL valide le plus clairsemé de chaque hauteur est un arbre de Fibonacci, construit à partir de deux arbres de Fibonacci plus petits, si bien que ses nombres de nœuds suivent la suite de Fibonacci. Voilà pourquoi la borne de hauteur porte la constante 1.44 : elle vaut exactement 1 / log₂(φ), avec φ ≈ 1.618, le nombre d'or.