Arbre équilibré
La notion d'arbre équilibré porte sur la forme de l'arbre étudié. Toutefois, cette notion d'équilibre présente plusieurs variantes. C'est en 1962 que deux Russes, Adel'son-Vel'skii et Landis, introduisent des critères définissant un équilibre. Les arbres vérifiant ces critères sont connus sous le nom d'arbres AVL.
Contentons-nous de cette définition.
Un arbre AVL vérifie la propriété suivante : « Pour tout nœud de l'arbre, la différence entre les hauteurs de ses deux fils ne peut excéder 1. »