Qu'est-ce qu'un quadtree?
Un quadtree est une structure arborescente basée sur la puissance de quatre et utilisée pour organiser des fichiers dans une base de données. Chaque nœud parent ou de départ a quatre nœuds enfants et chaque enfant contient une certaine quantité de données. Lorsque la limite de données dépasse sa limite, quatre enfants sont créés à partir de ce nœud. Il existe deux structures principales de quadtree: la région et l’arbre de points, de conception légèrement différente. Bien qu'un quadtree soit le plus souvent utilisé avec des bases de données, il peut également être utilisé pour rechercher des pixels dans des images bidimensionnelles (2D), car les pixels d'une image 2D peuvent toujours être séparés en quatre parties.
Toutes les structures en forme d'arborescence sont créées avec des nœuds parent ou branche, et des nœuds enfant ou feuille. Le parent est le point de départ et contient des données générales basées sur des catégories, tandis que l’enfant contient des fichiers et des documents. Dans un arbre quadrilatère, chaque parent doit avoir quatre enfants. Il doit y avoir quatre enfants, mais tous ne doivent pas contenir de données; ceux qui n'en ont pas sont appelés noeuds nuls. Ces nœuds nuls restent souvent stagnants et attendent des données.
Chaque nœud enfant d'un quadtree a une limite de données. Cette limite est généralement définie par la taille globale de la base de données. Lorsqu'il y a tellement d'informations qu'il dépasse la limite, le nœud enfant devient un nœud parent en donnant essentiellement naissance: il crée quatre nœuds enfants qui prennent en charge toutes les données supplémentaires. Il y aura généralement un ou deux nœuds nuls de cette création, mais cela dépend entièrement de la quantité de données contenue dans le nœud.
Il y a deux quadtrees principaux: région et point. La région quadtree est utilisée pour décomposer une région 2D entière en parties basées sur la puissance de quatre - telles que quatre, huit ou 16 parties - et est souvent utilisée pour les représentations. Cette structure est idéale pour les images ou les graphiques de champs de données. La version ponctuelle ressemble à un arbre binaire et est mieux utilisée avec des points ordonnés. Cette variante est également un véritable arbre, car il existe un point central duquel jaillissent tous les nœuds, contrairement à la version de région dans laquelle les nœuds sont dispersés.
L’utilisation la plus courante du quadtree est de séparer et d’organiser une base de données, mais ce n’est pas sa seule utilisation. Les algorithmes conçus pour rechercher un pixel spécifique dans une image utilisent généralement des arbres à quatre arbres, car chaque pixel d'une image peut être séparé en quatre parties égales. Cela rend les arbres quadrilatéraux particulièrement bien adaptés à la recherche de pixels.