1. Introduction
Data structures and algorithms seem a priori foreign to geometry. Yet some of the most efficient structures in computer science — balanced trees, space-filling curves — reveal a fascinating underlying geometry, linked to rotation and recursion.
2. AVL trees and rotations
An AVL tree (Adelson-Velsky and Landis, 1962) is a self-balancing binary search tree. After each insertion or deletion, the tree checks that the height difference between the left and right subtrees of each node does not exceed 1. If not, it performs a rotation to restore balance.
An AVL rotation is a local reorganization of three nodes. It does not correspond to a spiral motion in space — it is a purely combinatorial operation. But the terminology of "rotation" reflects a real geometric intuition: a subtree is pivoted around a pivot node.
3. Hilbert curves
The Hilbert curve is a fractal curve that fills a square. It is defined recursively: at each level, the square is subdivided into four quadrants and connected by a U-shaped path. The level-n curve visits 4ⁿ points and its length is 4ⁿ − 1 times the length of an elementary side.
The key property of the Hilbert curve is its locality: two points close on the curve are generally close in space. This property is exploited in computing to improve cache locality in image processing algorithms and spatial databases.
4. Z-curve and Morton
The Z-curve (or Morton curve) is a simpler alternative to the Hilbert curve. It interleaves the bits of the x and y coordinates to produce a linear index. Its traversal resembles the letter Z repeated recursively.
The Z-curve is less local than the Hilbert curve — it has discontinuities at quadrant boundaries — but it is much simpler to compute, making it preferable in many practical applications.
5. Applications
- Spatial databases: indexing geographic coordinates
- Image processing: improving cache locality
- 3D rendering: organizing texture data
- Image compression: recursive space partitioning
- Parallel computing: balanced data partitioning
6. Conclusion
The geometry of efficient algorithms reveals a deep truth: computational efficiency and geometric elegance are often linked. Space-filling curves are not mathematical curiosities — they are practical tools that exploit the geometric structure of space to improve algorithm performance.