Suppression de Quadtree

Question

J'écris une méthode de suppression pour un quadrillage. Maintenant, lorsque vous supprimez un élément dans un nœud, vous devez vérifier ses frères et sœurs pour voir si vous devez réduire les nœuds et les fusionner en un seul.

Pour vérifier les frères et sœurs, devrais-je stocker un pointeur sur le noeud parent, ou existe-t-il un moyen de le faire récursivement et mieux?

Merci

Answer 1

Pour le retrait dans un quadtree vous devez faire essentiellement les éléments suivants:

1. Trouver la feuille de l'objet, puis retirez-le de cette liste (le nœud qui contient les feuilles)
2. Vérifiez si le retrait de la feuille quitte le noeud vide, si c'est le cas, supprimez le noeud lui-même.
3. Vérifiez que les nœuds environnants sont également vides et, si c'est le cas, réduisez ce nœud dans le parent en le "désassociant" (cela peut être difficile à faire récursivement). L'astuce consiste simplement à vérifier si les nœuds adjacents contiennent quelque chose. Sinon, vous êtes sûr de jeter le quadrant entier et de monter d'un niveau. En procédant de la sorte de manière récursive, l'arbre sera replacé à l'endroit où se trouve un nœud adjacent avec une feuille.

Après l'étape 1, vous avez terminé. Si vous voulez économiser de la mémoire et garder l'arbre efficace, alors vous devriez faire les étapes 2 et 3.

Et oui, vous devriez conserver une référence de nœud parent pour rendre la traversée efficace.