Les arbres binaires équilibrés en C

Magazine
Marque
GNU/Linux Magazine
Numéro
235
Mois de parution
mars 2020
Domaines


Résumé

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...

Cet article est réservé aux abonnés. Il vous reste 98% à découvrir.
à partir de 21,65€ HT/mois/lecteur pour un accès 5 lecteurs à toute la plateforme
J'en profite


Articles qui pourraient vous intéresser...

Réinvention de la roue... des temporisations

Magazine
Marque
GNU/Linux Magazine
HS n°
Numéro
112
Mois de parution
janvier 2021
Domaines
Résumé

Les temporisations sont essentielles au sein des systèmes d'exploitation et dans certaines applications, pour déclencher des actions à l'échéance d'un délai. Il existe différents algorithmes pour les gérer de manière efficace. Cet article présente la fusion de deux d'entre eux, pour en tirer le meilleur.

Mesure fine de déplacement par RADAR interférométrique à synthèse d’ouverture (InSAR) par radio logicielle

Magazine
Marque
GNU/Linux Magazine
Numéro
244
Mois de parution
janvier 2021
Domaines
Résumé

Nous avons démontré dans le premier article de la série la capacité à mesurer la distance à une cible (range compression), puis dans un deuxième temps à détecter l’angle d’arrivée du signal (azimuth compression). Fort de cette capacité de cartographier des cibles, nous allons conclure cette série sur la conception de RADAR à base de radio logicielle, et le traitement des signaux associé, par la mesure fine de déplacement des cibles par analyse de la phase (interférométrie) du signal, lors de la répétition des mesures.

Utilisation de l’IDE Visual Studio Code

Magazine
Marque
GNU/Linux Magazine
HS n°
Numéro
112
Mois de parution
janvier 2021
Domaines
Résumé

Visual Studio Code, un outil dont Microsoft est à l’origine, est Open Source et gratuit, multiplateforme et ouvert grâce à son architecture d’extensions. Mis à jour mensuellement, il est écrit par des développeurs pour des développeurs.

La surcharge ou overloading en Python

Magazine
Marque
GNU/Linux Magazine
HS n°
Numéro
112
Mois de parution
janvier 2021
Domaines
Résumé

On vous l’a dit et répété : Python est un langage à typage dynamique ! Ah... donc, on ne peut pas réaliser de surcharge de fonctions ou de méthodes ? Pour les débutants, on dira non, pour les autres, on peut toujours s’arranger avec Python...

Accélérez vos traitements en développant votre propre solution de parallélisation

Magazine
Marque
GNU/Linux Magazine
Numéro
244
Mois de parution
janvier 2021
Domaines
Résumé

Certains de vos traitements lancés par des scripts shell s'exécutent bien trop lentement à votre goût, alors que certaines tâches séquentielles pourraient en fait s'exécuter simultanément : cet article va vous montrer de façon détaillée comment les accélérer en les parallélisant.