Le but de ce tutoriel est de vous faire découvrir toute la puissance des arbres binaires de recherche (souvent abrégé "ABR") par le biais de l'étude et de l'implémentation d'un algorithme de tri : le tri par ABR. Ce tri est un algorithme de tri simple, original et efficace. Moins connu que ses homologues tels que le tri par tas ou le tri fusion, il reste néanmoins un tri "rapide", avec une complexité au meilleur des cas et une complexité moyenne en O(n*log n). Il se base entièrement sur les propriétés des ABR.

Durant l'implémentation de ce tri, nous allons donc découvrir les algorithmes fondamentaux pour la manipulation des ABR. Tous n'entrent pas en jeu dans le tri par ABR, c'est pourquoi certains seront présentés à part.


L'auteur