Qu'est-ce qu'un quadtree?

Un quadtree est une structure en forme d'arbre basée sur la puissance de quatre et utilisée pour organiser des fichiers dans une base de données.Chaque parent, ou nœud 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éborde sur sa frontière, quatre enfants seront fabriqués à partir de ce nœud.Il existe deux principales structures de quadtree: la région et l'arbre de point, chacun légèrement différent dans la conception.Bien qu'un quadtree soit le plus souvent utilisé avec des bases de données, il peut également être utilisé pour trouver 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'arbre sontFabriqué avec des nœuds de parent ou de branche, de nœuds d'enfants ou de feuilles.Le parent est le point de départ et contient de larges données basées sur des catégories, tandis que l'enfant détient des fichiers et des documents.Dans un quadtree, chaque parent doit avoir quatre enfants.Bien qu'il doit y avoir quatre enfants, tous les enfants ne doivent pas contenir de données;Ceux sans sont appelés nœuds nuls.Ces nœuds nuls restent souvent stagnant et attendent les données.

Chaque nœud enfant dans 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'elle pousse au-delà de la limite, le nœud enfant devient un nœud parent en donnant essentiellement naissance mdash;Création de quatre nœuds enfants qui absorbent 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 dans le nœud.

Il y a deux quadrets principaux: région et point.Le quadtree de la région est utilisé pour décomposer une région 2D entière en parties en fonction de la puissance de quatre mdash;tels que quatre, huit ou 16 parties mdash;et souvent utilisé pour les représentations.Cette structure est la meilleure pour les images ou les graphiques de champ de données.La version ponctuelle est comme un arbre binaire et est mieux utilisée avec des points ordonnés.Cette variante est également un véritable arbre, car il y a un point central à partir duquel tous les nœuds ressortent, contrairement à la version régionale 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, maisCe n'est pas sa seule utilisation.Les algorithmes conçus pour trouver un pixel spécifique dans une image utilisent couramment des quadtrees, car chaque pixel d'une image peut être séparé en quatre parties égales.Cela rend les Quadtrees de manière unique pour rechercher des pixels.