1. Introduction
Les structures de données et les algorithmes semblent a priori étrangers à la géométrie. Pourtant, certaines des structures les plus efficaces de l'informatique — les arbres équilibrés, les courbes de remplissage de l'espace — révèlent une géométrie sous-jacente fascinante, liée à la rotation et à la récursivité.
2. Arbres AVL et rotations
Un arbre AVL (Adelson-Velsky et Landis, 1962) est un arbre binaire de recherche auto-équilibrant. Après chaque insertion ou suppression, l'arbre vérifie que la différence de hauteur entre les sous-arbres gauche et droit de chaque nœud ne dépasse pas 1. Si ce n'est pas le cas, il effectue une rotation pour rétablir l'équilibre.
Une rotation AVL est une réorganisation locale de trois nœuds. Elle ne correspond pas à un mouvement spiralé dans l'espace — c'est une opération purement combinatoire. Mais la terminologie de « rotation » reflète une intuition géométrique réelle : on fait pivoter un sous-arbre autour d'un nœud pivot.
3. Courbes de Hilbert
La courbe de Hilbert est une courbe fractale qui remplit un carré. Elle est définie récursivement : à chaque niveau, on subdivise le carré en quatre quadrants et on les relie par un chemin en forme de U. La courbe de niveau n visite 4ⁿ points et sa longueur est 4ⁿ − 1 fois la longueur d'un côté élémentaire.
La propriété clé de la courbe de Hilbert est sa localité : deux points proches sur la courbe sont généralement proches dans l'espace. Cette propriété est exploitée en informatique pour améliorer la localité de cache dans les algorithmes de traitement d'images et de bases de données spatiales.
4. Courbe Z et Morton
La courbe Z (ou courbe de Morton) est une alternative plus simple à la courbe de Hilbert. Elle entrelace les bits des coordonnées x et y pour produire un index linéaire. Son parcours ressemble à la lettre Z répétée récursivement.
La courbe Z est moins locale que la courbe de Hilbert — elle présente des discontinuités aux frontières des quadrants — mais elle est beaucoup plus simple à calculer, ce qui la rend préférable dans de nombreuses applications pratiques.
5. Applications
- Bases de données spatiales : indexation des coordonnées géographiques
- Traitement d'images : amélioration de la localité de cache
- Rendu 3D : organisation des données de texture
- Compression d'images : partitionnement récursif de l'espace
- Calcul parallèle : partitionnement équilibré des données
6. Conclusion
La géométrie des algorithmes efficaces révèle une vérité profonde : l'efficacité computationnelle et l'élégance géométrique sont souvent liées. Les courbes de remplissage de l'espace ne sont pas des curiosités mathématiques — ce sont des outils pratiques qui exploitent la structure géométrique de l'espace pour améliorer les performances des algorithmes.