¿Qué es un quadtree?

Un quadtree es una estructura en forma de árbol basada en la potencia de cuatro y utilizada para organizar archivos en una base de datos. Cada nodo principal o inicial tiene cuatro nodos secundarios, y cada hijo tiene una cierta cantidad de datos. Cuando el límite de datos se extienda sobre su límite, se crearán cuatro hijos desde ese nodo. Hay dos estructuras principales de quadtree: la región y el árbol de puntos, cada uno ligeramente diferente en diseño. Si bien un quadtree se usa con mayor frecuencia con bases de datos, también se puede usar para buscar píxeles en imágenes bidimensionales (2D), porque los píxeles en una imagen 2D siempre se pueden separar en cuatro partes.

Todas las estructuras en forma de árbol están hechas con nodos primarios, o rama, nodos e hijos, u hoja. El padre es el punto de partida y contiene datos amplios basados ​​en categorías, mientras que el niño tiene archivos y documentos. En un árbol cuádruple, cada padre debe tener cuatro hijos. Si bien debe haber cuatro hijos, no todos los niños tienen que contener datos; aquellos sin se conocen como nodos nulos. Estos nodos nulos a menudo permanecen estancados y esperan datos.

Cada nodo hijo en un quadtree tiene un límite de datos. Este límite generalmente se define por el tamaño general de la base de datos. Cuando hay tanta información que supera el límite, el nodo secundario se convierte en un nodo primario esencialmente dando a luz, creando cuatro nodos secundarios que toman todos los datos adicionales. Por lo general, habrá uno o dos nodos nulos de esta creación, pero esto depende completamente de la cantidad de datos que haya en el nodo.

Hay dos cuadrantes principales: región y punto. La región quadtree se usa para descomponer una región 2D completa en partes en función de la potencia de cuatro, como cuatro, ocho o 16 partes, y a menudo se usa para representaciones. Esta estructura es mejor para imágenes o gráficos de campos de datos. La versión de puntos es como un árbol binario y se usa mejor con puntos ordenados. Esta variante también es un árbol verdadero, porque hay un punto central desde el cual todos los nodos surgen, a diferencia de la versión de la región en la que los nodos están dispersos.

El uso más común del quadtree es separar y organizar una base de datos, pero este no es su único uso. Los algoritmos creados para encontrar un píxel específico en una imagen comúnmente usan cuadrúteros, porque cada píxel en una imagen se puede separar en cuatro partes iguales. Esto hace que los quadtrees sean especialmente adecuados para buscar píxeles.