Visualiseur d'arbres BST / AVL

Insérez des valeurs et observez l'arbre grandir. Passez en mode AVL pour voir le rééquilibrage automatique.

Exemple résolu — Visualiseur d'arbres BST / AVL

Hauteur de l'arbre	7
Nombre de nœuds	7
Type	BST
Hauteur équilibrée idéale	3
Rotations AVL	désactivées

Ce sont les valeurs affichées par le calculateur à l’ouverture de la page. Modifiez une entrée ci-dessus pour les recalculer.

Chargement de la simulation interactive...

Une entrée triée est la pire des entrées 🖖

Un arbre binaire de recherche tire sa vitesse de sa forme, et cette forme découle entièrement de l’ordre d’insertion. Donnez à cet outil 10, 20, 30, 40, 50, 60, 70 dans cet ordre : chaque clé est plus grande que la précédente, donc chacune se greffe à droite de celle d’avant et l’arbre devient une chaîne droite de hauteur 7. C’est une liste chaînée qui traîne le coût des pointeurs d’arbre, et trouver 70 demande sept comparaisons au lieu de trois. Rien dans les données n’était pathologique : elles étaient simplement déjà triées, ce qui est la façon habituelle dont les données arrivent. Passez ces mêmes sept valeurs en mode AVL et les rotations ramènent la hauteur à 3. C’est tout l’argument en faveur des arbres auto-équilibrés.

Chaque étape élimine la moitié 🖖

Un arbre binaire de recherche fonctionne comme la recherche d'un mot dans un dictionnaire : à chaque nœud, vous comparez puis écartez aussitôt toute la moitié qui ne peut pas contenir votre 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 : saisissez les valeurs déjà triées (10, 20, 30, …) et regardez l'arbre s'effondrer en une seule ligne penchée, pas plus rapide qu'un parcours de liste un par un.

Le nombre d'or se cache dans les arbres AVL 🖖

Passez en mode AVL et demandez-vous : 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.

ARBRES ABR ET AVL — LES MÊMES VALEURS, QUATRE ARBRES DIFFÉRENTS

Quel arbre votre ordre d'insertion va-t-il produire ?

La forme d'un arbre binaire de recherche ne dépend pas des valeurs qu'il contient, mais de l'ordre dans lequel elles sont arrivées — et cette forme est tout le prix à payer : chaque recherche, chaque insertion, chaque suppression descend de la racine jusqu'à une feuille, donc c'est la hauteur qui coûte. Deux questions tranchent le cas dans lequel vous êtes : les valeurs sont-elles arrivées déjà triées, et quelque chose les fait-il tourner pour revenir à l'équilibre ?

ABR équilibré — l'ordre d'arrivée s'est entrelacé h = 3 = ⌈log₂(n + 1)⌉

ABR dégénéré — entrée triée, rien qui rééquilibre h = n = 7 ⇒ O(n)

Rééquilibrage AVL — la rotation est locale et peu coûteuse |hL − hR| > 1 → ↻, h = 3

AVL sur entrée triée — le cas pour lequel les rotations existent ↻ × 4 ⇒ h = 3 < 7

ABR équilibré — l'ordre d'arrivée s'est entrelacé

Ce que vous savez: Mode ABR pur, aucune rotation. Les valeurs arrivent en commençant par le milieu : chaque nouvelle clé tombe dans un sous-arbre encore bas et aucun côté ne prend de l'avance sur l'autre.

Ce que cela coûte: h = 3 = ⌈log₂(n + 1)⌉

Exemple résolu: 50, 30, 70, 20, 40, 60, 80 → racine 50, 7 nœuds, hauteur 3 — exactement l'idéal ⌈log₂(7+1)⌉ = 3, donc la recherche la plus profonde coûte 3 comparaisons

Ouvrir ce cas: Équilibré

ABR équilibré — l'ordre d'arrivée s'est entrelacé. Sept nœuds sur trois niveaux : chaque feuille à la même distance de la racine, on ne fait pas mieux. Mode ABR pur, aucune rotation. Les valeurs arrivent en commençant par le milieu : chaque nouvelle clé tombe dans un sous-arbre encore bas et aucun côté ne prend de l'avance sur l'autre. — Sept nœuds sur trois niveaux : chaque feuille à la même distance de la racine, on ne fait pas mieux.

ABR dégénéré — entrée triée, rien qui rééquilibre

Ce que vous savez: Mode ABR pur à nouveau, mais les valeurs arrivent en ordre croissant. Chacune est plus grande que tout ce qui est déjà stocké, donc elle part à droite, à chaque fois.

Ce que cela coûte: h = n = 7 ⇒ O(n)

Exemple résolu: 10, 20, 30, 40, 50, 60, 70 → racine 10, 7 nœuds, hauteur 7 au lieu de 3 ; trouver 70 coûte 7 comparaisons, et l'outil qualifie le résultat de liste chaînée

Ouvrir ce cas: Dégénéré

ABR dégénéré — entrée triée, rien qui rééquilibre. Chaque nœud n'a qu'un fils : la recherche parcourt les sept niveaux, pas plus vite qu'un balayage de tableau. Mode ABR pur à nouveau, mais les valeurs arrivent en ordre croissant. Chacune est plus grande que tout ce qui est déjà stocké, donc elle part à droite, à chaque fois. — Chaque nœud n'a qu'un fils : la recherche parcourt les sept niveaux, pas plus vite qu'un balayage de tableau.

Rééquilibrage AVL — la rotation est locale et peu coûteuse

Ce que vous savez: Mode AVL. Après chaque insertion, l'arbre remonte vers la racine, et le premier nœud dont les deux hauteurs de sous-arbre diffèrent de plus de 1 est mis en rotation. Les badges près de chaque nœud affichent la hauteur gauche moins la hauteur droite.

Ce que cela coûte: |hL − hR| > 1 → ↻, h = 3

Exemple résolu: 30, 20, 10, 25, 35, 40 en mode AVL → insérer 10 fait basculer le nœud 30 à +2, et une rotation à droite hisse 20 à sa place ; plus tard, 40 fait basculer un nœud à −2 et une rotation à gauche corrige. 2 rotations, 6 nœuds, hauteur 3.

Ouvrir ce cas: Rééquilibrage AVL

Les nœuds cerclés ont été hissés par une rotation ; chaque badge est de nouveau dans ±1.

AVL sur entrée triée — le cas pour lequel les rotations existent

Ce que vous savez: Mode AVL, alimenté exactement avec les valeurs qui ont produit la chaîne deux cas plus haut. Chaque insertion atterrit à l'extrémité droite et pousse l'équilibre d'un ancêtre à −2, donc presque chaque insertion déclenche une correction.

Ce que cela coûte: ↻ × 4 ⇒ h = 3 < 7

Exemple résolu: 10, 20, 30, 40, 50, 60, 70 en mode AVL → 4 rotations à gauche, et la racine finit à 40 plutôt qu'à 10. Hauteur 3, pas 7 — la même entrée, les mêmes sept nœuds, moins de la moitié de la profondeur.

Ouvrir ce cas: Trié dans un AVL

AVL sur entrée triée — le cas pour lequel les rotations existent. Les mêmes valeurs triées qu'au cas 2, ramenées à trois niveaux par rotation au fil des arrivées. Mode AVL, alimenté exactement avec les valeurs qui ont produit la chaîne deux cas plus haut. Chaque insertion atterrit à l'extrémité droite et pousse l'équilibre d'un ancêtre à −2, donc presque chaque insertion déclenche une correction. — Les mêmes valeurs triées qu'au cas 2, ramenées à trois niveaux par rotation au fil des arrivées.

Références (1)

Insight block 3 — the Fibonacci tree that sets the AVL height bound: D. E. Knuth, The Art of Computer Programming, Volume 3: Sorting and Searching, 2nd edition, §6.2.3. Addison-Wesley, 1998. ISBN 978-0-201-89685-5 — the sparsest legal AVL tree of each height, and the logφ bound that follows.

Problème entièrement résolu

Un arbre de hauteur sept avec sept nœuds 5 étapes
Sept nœuds et un arbre de hauteur sept. Un arbre équilibré aurait une hauteur de 3. Déterminez ce qu'a fait l'entrée — et ce que cela coûte à grande échelle.
1. Les clés par défaut sont 10, 20, 30, … — déjà triées. En suivant la règle d'insertion, chaque nouvelle clé est plus grande que tout ce qui se trouve dans l'arbre, elle va donc à droite, à chaque fois.
  
  $insert 10, 20, 30, 40, 50, 60, 70 in order$
2. Le résultat n'a aucune ramification. Chaque nœud a un seul enfant, de sorte que la structure est une liste chaînée qui se trouve être dessinée sous la forme d'un arbre, et la hauteur est égale au nombre de nœuds.
  
  $each new key > every key present ⟹ always the right child$
3. La meilleure hauteur possible pour sept nœuds est 3, car un arbre de hauteur h contient au plus 2ʰ − 1 nœuds et 2³ − 1 = 7 exactement. Cette entrée atteint le pire des cas alors que le cas équilibré était disponible.
  
  $h = n = 7 (a linked list wearing a tree’s name)$
4. La recherche parcourt l'arbre depuis la racine, le coût est donc la hauteur : 7 comparaisons ici contre 3.
  
  $h_{m i n} = ⌈ lo g_{2} (n + 1)⌉ = ⌈ lo g_{2} 8 ⌉ = 3$
5. C'est le rapport qui importe, et il augmente. À un million de nœuds, la hauteur équilibrée est de 20 et la hauteur avec une entrée triée est d'un million.
  
  $n = 1 0^{6} : h_{m i n} = 20 but sorted input gives h = 1 0^{6}$
Réponse

L'outil affiche une hauteur de 7 pour 7 nœuds contre un idéal de 3. La leçon est que O(log n) n'a jamais été une propriété de l'arbre binaire de recherche — c'est une propriété de l'ordre d'insertion, et l'ordre le plus naturel qu'un programmeur puisse lui fournir, des données triées, est précisément celui qui la détruit. C'est la raison d'être des arbres AVL et rouge-noir : ils coûtent une rotation ou deux par insertion pour rendre la garantie inconditionnelle. Passez le mode sur AVL et observez les mêmes sept clés se stabiliser à une hauteur de 3.

$O (lo g n) is a claim about the INPUT ORDER, not about the structure$

Par l’équipe 42Math · Mis à jour 2026-07-28

Vérifié sur des sources publiées. Corrections bienvenues. Politique éditoriale · Corrections

Toutes les leçons : Informatique →

Exemples de problèmes

Équilibré - ABR équilibré : 7 nœuds, hauteur 3
Dégénéré - Entrée triée : l'ABR s'étire jusqu'à la hauteur 7
Rééquilibrage AVL - L'AVL se rééquilibre avec 2 rotations
Trié dans un AVL - Les mêmes valeurs triées dans un AVL : hauteur 3 après 4 rotations