Nous allons dans cet article revenir sur une structure de données très importante en informatique : les arbres binaires. Après quelques rappels sur l’ordre des algorithmes, les algorithmes de tri, les algorithmes de recherche d’éléments et le rééquilibrage des arbres, nous examinerons le code d’une implémentation en C d’une gestion d’arbres binaires équilibrés.
Parmi les algorithmes importants en informatique, on peut citer les algorithmes de tri et les algorithmes de recherche d’éléments. Ils existent tous sous différentes formes et manipulent différents types de structures de données. Certains utilisent des tableaux ou des listes, d’autres utilisent des arbres ou des tableaux de hachage. L’algorithme dont nous allons parler ici peut servir à la fois à trier des données et à rechercher des éléments, et cela, avec d’excellentes performances : il s’agit d’un algorithme de gestion d’arbre binaire équilibré. Après quelques rappels importants, nous étudierons une implémentation de cet algorithme, et nous terminerons par quelques axes d’optimisation possibles.
Le code présenté ici a été testé sur Debian 7 et Devuan ASCII. Il est disponible sur GitHub.
1. Quelques rappels
1.1 Notion d’ordre d’un algorithme
Lorsque l’on parle d’algorithmes, on parle parfois aussi d’ordre d’un...
- Accédez à tous les contenus de Connect en illimité
- Découvrez des listes de lecture et des contenus Premium
- Consultez les nouveaux articles en avant-première