¿Qué es un Quadtree?

Significado | Concepto | Definición:

Un quadtree es una estructura en forma de árbol basada en el poder de cuatro y que se utiliza para organizar archivos en una base de datos. Cada nodo principal, o inicial, tiene cuatro nodos secundarios y cada secundario contiene una cierta cantidad de datos. Cuando el límite de datos sobrepase su límite, se crearán cuatro hijos a partir de ese nodo. Hay dos estructuras de cuatro árboles principales: la región y el árbol de puntos, cada una de ellas ligeramente diferente en diseño. Si bien un árbol cuádruple se usa con mayor frecuencia con bases de datos, también se puede usar para encontrar píxeles en imágenes bidimensionales (2D), porque los píxeles en una imagen 2D siempre se pueden separar en cuatro partes.

Mujer haciendo el pino con una computadora

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

Anuncios

Cada nodo hijo en un quadtree tiene un límite de datos. Este límite suele estar definido por el tamaño total de la base de datos. Cuando hay tanta información que sobrepasa el límite, el nodo hijo se convierte en un nodo padre esencialmente al dar a luz, creando cuatro nodos secundarios que ocupan 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 quadtrees principales: región y punto. El árbol cuádruple de región se utiliza para descomponer una región 2D completa en partes basadas en la potencia de cuatro, como cuatro, ocho o 16 partes, y a menudo se usa para representaciones. Esta estructura es la 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 verdadero árbol, porque hay un punto central desde el cual brotan todos los nodos, a diferencia de la versión de 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 suelen utilizar quadtrees, porque cada píxel de una imagen se puede separar en cuatro partes iguales. Esto hace que los quadtrees sean especialmente adecuados para buscar píxeles.

Anuncios