Librairie AVL
Description
Je n'ai pas la prétention de donner un cours d'informatique, certains d'entre vous connaissent déjà les arbres binaires de recherche et il existe une foule de tuto très bien écrits sur ce sujet.
Ce petit "tuto" s'adresse surtout à ceux qui n'en on jamais entendu parlé et qui ont la flemme de faire des recherches, peut être que cela éveillera la curiosité de certains... 
A la fin (pour ceux qui sont pressés), se trouve ma petite librairie .
Un arbre binaire ?.... Kesako ?
Un enregistrement est composé de trois champs :
- une clé,
- un fils gauche,
- un fils droit.
Le fils gauche correspond à l'indice d'un élément inférieur à la clé.
Le fils droit correspond à l'indice d'un élément supérieur à la clé.
Exemple
Nous allons réaliser une liste de caractères.
Au départ je n'ai pas d'enregistrement. J'insère un élément contenant la valeur "D". Cette valeur (clé) pourrait être un prénom, un n°de tel, le nom d'un animal,etc...
Je me retrouve avec ceci:
"D" est le premier élément de notre arbre, il possède l'indice 1.
Par définition cet enregistrement est la racine de notre arbre.
Comme il n'y a pas d'autres éléments en dessous, les fils gauche et droit sont à zéro.
Insertion d'une nouvelle lettre : "B" (indice 2).
Donc je compare "B" avec "D" : c'est inférieur donc j'indique que "B" se trouve à gauche de "D" (dans le fils gauche de "D" je met l'indice de "B" soit 2)
L'enregistrement "B" est ce que l'on appelle une feuille
Faisons maintenant la même chose avec la lettre "F" (indice 3): "F" est supérieur à "D" donc on crée le lien sur le fils droit de "D"
Jusque là tout va bien...
Insertion de la lettre "C" (indice 4)
On compare "C" avec "D" c'est inférieur, mais l'emplacement à gauche n'est pas libre, donc on va comparer avec la lettre qui suit : "B"
"C" est supérieur à "B" et son fils droit est libre donc on crée le lien entre "B"->Filsdroit et la nouvelle lettre "C" :
On répète l'opération autant de fois que l'on veut...
Quel est l’intérêt d'un tel système ?
Imaginons cette arborescence :
Si je dois chercher par exemple "Eric", je vais d'abord comparer avec "Denis" -> c'est supérieur, donc tout ce qui se trouve à gauche de "Denis" ne sera pas testé !
On compare ensuite avec "Fabrice" -> c'est inférieur, donc tout ce qui se trouve à droite de "Fabrice" ne sera pas testé !
On regarde à gauche, on compare et on a trouvé !!!
Dans cet exemple, au pire, on aura 3 comparaisons maxi pour une liste de 7 prénoms.
Imaginez maintenant que vous avez une liste de 1000 éléments. A la première comparaison, vous éliminez 500 enregistrements d'un coup ! et ainsi de suite...
L'avantage d'un tel système: c'est la rapidité pour faire des recherches d'un élément dans une liste. Par exemple, dans mon programme de démo, j'ai calculé qu'il me faut 7.5ms pour faire une comparaison d'un nom par rapport à un autre.
Admettons que mon PC rame, je compte le double soit 15ms/comp.
En 0.5s j'ai réalisé 33 comparaisons ce qui revient à dire que j'ai parcouru 33 noeuds de mon arbre...
Puisque je descend d'un niveau à chaque comparaison → j'ai un arbre de 33 niveaux .
Un arbre de 33 niveaux contient : 233 - 1 éléments soit : 8 589 934 591 éléments !
En clair: je mets 0.5s pour retrouver 1 élément parmi les 8 589 934 591 autres....
Cela reste de la théorie car il y a d'autres facteurs qui ralentissent le système. Sans compter que dans mon programme de démo tout ce passe en RAM : Je vous dis pas la taille de la RAM nécessaire pour stocker les 8 milliards et quelques poussières éléments ! 
Mais cela vous donne quand même un ordre d'idée... 
L'exemple ci-dessus est le cas idéal, c'est à dire que votre arborescence est équilibrée : il y a autant de fils à droite qu'à gauche de la racine et chaque nœud (enregistrement intermédiaire) est complet.
Suivant l'ordre d'insertion vous pouvez très bien obtenir une liste d'éléments chaîné tous à gauche ou à droite... dans le cas ci-dessous, le système n'offre plus aucun intérêt...
Heureusement qu'il existe des mécanismes d'auto-équilibrage de l'arborescence qui font en sorte que la hauteur de deux sous-arbres d'un même noeud diffèrent au plus de un. Le principe est basé sur la rotation des éléments au moment de l'insertion.
Par exemple :
Le parcours infixe
Terme désigné pour parcourir un arbre de son élément le plus petit vers le plus grand.
En rouge: les appels à la procédure - en bleu les sorties de la procédure
Pour ma librairie, je me suis basé sur les arbres auto-équilibrés de type AVL. La dénomination "arbre AVL" provient des noms de ses deux inventeurs, Georgii Adelson-Velsky et Evguenii Landis qui l'ont publié en 1962 (c'est pas tout jeune! 
) sous le titre An algorithm for the organization of information. Vous trouverez des informations supplémentaires ici.