Un árbol cuádruple, a veces árbol cuádruple, árbol Q o QT, es un término informático que se refiere a un método para organizar datos en cuatro cuadrantes. Las bases de datos a veces usan árboles cuádruples para almacenar y encontrar sus registros. Este tipo de estructura organizativa funciona especialmente bien para encontrar un bit o píxel en particular en una imagen bidimensional.
El árbol cuádruple sigue de alguna manera la estructura de datos de árbol que se usa comúnmente en ciencias de la computación. La estructura de datos de árbol normal se ve como un árbol al revés, donde un nodo padre en la parte superior del árbol tiene uno o más nodos hijos conectados a él. Todos los demás nodos del árbol tienen un nodo principal y pueden tener cualquier número de nodos secundarios, incluido cero.
A diferencia de una estructura de datos de árbol normal, una estructura de árbol cuádruple requiere que cada nodo interno tenga exactamente cuatro nodos secundarios. Al ilustrar la mayoría de las estructuras de árbol cuádruple, verá un nodo que tiene cuatro nodos secundarios colgando de él, con líneas que conectan el nodo principal con sus nodos secundarios. La ilustración puede continuar, con cuatro nodos secundarios más colgando de cada uno de los cuatro nodos secundarios originales.
Otras veces, la ilustración de un árbol cuádruple será una región o un cuadrado. Siempre que la región alcanza su capacidad máxima para almacenar datos, se divide en cuatro cuadrantes. Normalmente, las regiones y los cuadrantes son cuadrados, aunque también pueden ser rectángulos u otras formas.
Un árbol cuádruple es una buena estructura de datos para organizar píxeles en una foto y para organizar gráficos por computadora. La imagen se puede dividir en cuadrantes y cada cuadrante se puede dividir en cuatro más. Esto se puede repetir una y otra vez hasta que alcance el nivel de píxeles individuales. Sin embargo, si un cuadrante contiene píxeles que son todos del mismo color, no hay razón para dividir más el cuadrante.
Aunque los datos almacenados en una estructura de árbol cuádruple pueden requerir mucho espacio de almacenamiento en comparación con otros métodos de organización de datos para gráficos por computadora, la estructura de árbol cuádruple tiene varias ventajas. Primero, puede eliminar toda la fotografía o el gráfico en un solo paso borrando el nodo raíz, que también borra todos sus nodos secundarios. En segundo lugar, puede reducir rápidamente la resolución de una fotografía simplemente borrando el nivel final de los nodos secundarios. Esto reducirá así la cantidad de espacio de almacenamiento que requiere. Finalmente, encontrar un área particular de la fotografía para la manipulación de imágenes es más fácil con la estructura de árbol cuádruple.
Los árboles cuádruples también se utilizan en algunas otras situaciones, incluida la indexación espacial. Aunque los árboles cuádruples se limitan a imágenes bidimensionales, la representación de una imagen tridimensional puede seguir una estructura similar, llamada octárbol, que es la subdivisión de un cubo en ocho hijos.