Datastructure + Algorithme pour stocker les intervalles qui ne se chevauchent pas

Question

Je me demandais si l'un d'entre vous connaissait un moyen efficace de stocker des intervalles qui ne se chevauchent pas. Mon but final est d'utiliser ceci pour allouer de l'espace d'adressage virtuel (j'écris un système d'exploitation pour le fun) et je voulais savoir si on pouvait stocker les régions d'espace libre dans une complexité O (n) et O (n) complexité.

Une structure de données probabiliste pourrait fonctionner car je peux toujours parcourir la table des pages pour savoir si l'espace d'adressage est disponible.

Merci.

Answer 1

R-Trees peut être utilisé pour cela. Ils sont également utilisés pour les structures 2D (et probablement N-dimensionnelles), mais peuvent également gérer les éléments 1D tels que vous en avez besoin.

Answer 2

Jetez un oeil à R Trees.