lundi 22 juin 2009

Quadtree - partie 5

Un tout petit billet pour expliquer une petite modification possible relative aux quadtree dont les éléments sont contenus dans des feuilles. Plutôt que de contenir qu'un seul élément, une feuille pourrait contenir plusieurs éléments. Quel en serait l'avantage? Le plus évident est celui de la limitation de consommation de mémoire. En effet, si une feuille peut contenir N éléments, ce sont autant de feuilles qu'il ne faut pas créer.

Et comme souvent, il est également nécessaire de se poser la question: quel est le coût de ceci? Et bien, lors de la recherche, lorsque l'on arrive à une feuille, il faudra rechercher l'élément souhaité parmi N. Cette recherche peut être soit logarithmique (mais alors il faut maintenir le tableau trié), soit linéaire ( ce qui ne nécessite pas de garder le tableau trié lorsque l'on ajoute un élément). Toutes les opérations (consultation, ajout, suppression) s'en trouveront ralenties en fonction de N ce qui rend le choix de cette valeur assez crucial.

Aucun commentaire:

Enregistrer un commentaire