Introduction

Un arbre binaire de recherche maintient les valeurs ordonnées : le sous-arbre gauche de chaque nœud contient des valeurs plus petites et son sous-arbre droit contient des valeurs plus grandes. Cet ordonnancement rend la recherche rapide, mais seulement si l'arbre reste approximativement équilibré. Si vous insérez des valeurs dans un ordre trié dans un arbre binaire de recherche classique, il se dégrade en une ligne droite, transformant chaque recherche en un balayage linéaire lent.

Un arbre AVL corrige cela en s'équilibrant automatiquement. Après chaque insertion ou suppression, il vérifie si un nœud est devenu déséquilibré et, si c'est le cas, effectue une petite correction locale appelée une rotation pour rétablir l'équilibre. Peu importe la façon dont vous le construisez, un arbre AVL ne se dégrade jamais en une ligne.

Dans ce cours, vous allez construire un arbre AVL à partir de zéro dans votre langage préféré : des nœuds avec une hauteur suivie, des vérifications d'équilibre, les quatre cas de rotation, ainsi qu'une insertion et une suppression auto-équilibrées. Ensuite, vous utiliserez votre classe terminée pour résoudre une série de défis pratiques.