árbol k -d

Dado que existen muchas formas posibles de elegir planos de división alineados con los ejes, existen muchas formas diferentes de construir árboles k -d. El método canónico de construcción de árboles k -d tiene las siguientes restricciones: ^{[ 4 ]}

• A medida que uno desciende por el árbol, se va recorriendo el ciclo de ejes utilizados para seleccionar los planos de división. (Por ejemplo, en un árbol tridimensional, la raíz tendría un plano alineado con el eje x , los hijos de la raíz tendrían planos alineados con el eje y , los nietos de la raíz tendrían planos alineados con el eje z , los bisnietos de la raíz tendrían planos alineados con el eje x , los tataranietos de la raíz tendrían planos alineados con el eje y , y así sucesivamente).
• Los puntos se insertan seleccionando la mediana de los puntos que se colocan en el subárbol , con respecto a sus coordenadas en el eje que se utiliza para crear el plano de división. (Tenga en cuenta que se supone que introducimos el conjunto completo de n puntos en el algoritmo de antemano).

Este método da como resultado un árbol k -d equilibrado , en el que cada nodo hoja se encuentra aproximadamente a la misma distancia de la raíz. Sin embargo, los árboles equilibrados no son necesariamente óptimos para todas las aplicaciones.

Tenga en cuenta que no es necesario seleccionar el punto medio. En caso de que no se seleccionen puntos medios, no hay garantía de que el árbol esté equilibrado. Para evitar codificar un código complejo${\displaystyle O(n)}$algoritmo de búsqueda de medianas ^{[ 5 ] [ 6 ]} o utilizando un${\displaystyle O(n\log(n))}$Para ordenar los n puntos mediante algoritmos como heapsort o mergesort , una práctica común consiste en ordenar un número fijo de puntos seleccionados aleatoriamente y usar la mediana de estos como plano de división. En la práctica, esta técnica suele generar árboles bien equilibrados.

Dado una lista de n puntos, el siguiente algoritmo utiliza una ordenación por búsqueda de la mediana para construir un árbol k -d equilibrado que contiene esos puntos.

función kdtree ( lista de puntos pointList, int depth) { // Seleccionar el eje en función de la profundidad para que el eje recorra todos los valores válidos var int axis := depth mod k; // Ordenar la lista de puntos y elegir la mediana como elemento pivote seleccionar la mediana por eje de pointList; // Crear nodo y construir subárbol nodo.ubicación := mediana; nodo.hijoizquierdo := kdtree(puntos en pointList antes de la mediana, profundidad+1); nodo.hijoderecho := kdtree(puntos en pointList después de la mediana, profundidad+1); return nodo; }

Es común que los puntos posteriores a la mediana incluyan únicamente aquellos que son estrictamente mayores que la mediana en la dimensión actual. Para los puntos que se encuentran sobre la mediana en la dimensión actual, es posible definir una función que los compare en todas las dimensiones. En algunos casos, es aceptable que los puntos iguales a la mediana se sitúen a un lado de ella, por ejemplo, dividiendo los puntos en un subconjunto de "menores que" y otro de "mayores o iguales que".

Este algoritmo crea la invariante de que, para cualquier nodo, todos los nodos del subárbol izquierdo se encuentran a un lado de un plano de división , y todos los nodos del subárbol derecho se encuentran al otro lado. Los puntos que se encuentran en el plano de división pueden aparecer a cualquiera de los dos lados. El plano de división de un nodo pasa por el punto asociado a dicho nodo (denominado en el código como node.location ).

Los algoritmos alternativos para construir un árbol k -d equilibrado preordenan los datos antes de construir el árbol. Luego, mantienen el orden de la preordenación durante la construcción del árbol y, por lo tanto, eliminan el costoso paso de encontrar la mediana en cada nivel de subdivisión. Dos de estos algoritmos construyen un árbol k -d equilibrado para ordenar triángulos con el fin de mejorar el tiempo de ejecución del trazado de rayos para gráficos por computadora tridimensionales . Estos algoritmos preordenan n triángulos antes de construir el árbol k -d , luego construyen el árbol en${\displaystyle O(n\log n)}$tiempo en el mejor de los casos. ^{[ 7 ] [ 8 ]} Un algoritmo que construye un árbol k -d equilibrado para ordenar puntos tiene una complejidad en el peor de los casos de${\displaystyle O(kn\log(n))}$. ^{[ 9 ] [ 10 ]} Este algoritmo preordena n puntos en cada una de las k dimensiones utilizando un${\displaystyle O(n\log(n))}$Se realiza una ordenación previa mediante algoritmos como Heapsort o Mergesort . De esta forma, se mantiene el orden de estas k preordenaciones durante la construcción del árbol, evitando así encontrar la mediana en cada nivel de subdivisión.

Se añade un nuevo punto a un árbol k -d de la misma manera que se añade un elemento a cualquier otro árbol de búsqueda . Primero, se recorre el árbol, comenzando desde la raíz y avanzando hacia el hijo izquierdo o derecho, según si el punto que se va a insertar se encuentra en el lado izquierdo o derecho del plano de división. Una vez que se llega al nodo bajo el cual debe ubicarse el hijo, se añade el nuevo punto como hijo izquierdo o derecho del nodo hoja, dependiendo de qué lado del plano de división del nodo contenga el nuevo nodo.

Agregar puntos de esta manera puede provocar un desequilibrio en el árbol, lo que reduce su rendimiento. La velocidad de degradación del rendimiento depende de la distribución espacial de los puntos agregados y de la cantidad de puntos en relación con el tamaño del árbol. Si un árbol se desequilibra demasiado, puede ser necesario reequilibrarlo para restaurar el rendimiento de las consultas que dependen de dicho equilibrio, como la búsqueda del vecino más cercano.

Para eliminar un punto de un árbol k -d existente sin romper la invariante, la forma más sencilla es formar el conjunto de todos los nodos y hojas a partir de los hijos del nodo objetivo y recrear esa parte del árbol. ^{[ 2 ]}

Otro enfoque es encontrar un reemplazo para el punto eliminado. ^{[ 11 ]} Primero, encontrar el nodo${\displaystyle R}$que contiene el punto que se va a eliminar. Para el caso base, donde R es un nodo hoja, no se requiere reemplazo. Para el caso general, encuentre un punto de reemplazo, por ejemplo${\displaystyle p}$, del subárbol con raíz en${\displaystyle R}$. Reemplazar el punto almacenado en${\displaystyle R}$con${\displaystyle p}$Luego, elimine recursivamente${\displaystyle p}$.

Para encontrar un punto de reemplazo, si${\displaystyle R}$discrimina en${\displaystyle x}$(decir) y${\displaystyle R}$tiene un hijo derecho, encuentra el punto con el mínimo${\displaystyle x}$valor del subárbol enraizado en el hijo derecho. De lo contrario, encuentre el punto con el máximo${\displaystyle x}$valor del subárbol con raíz en el hijo izquierdo.

El balanceo de un árbol k -d requiere cuidado porque los árboles k -d están ordenados en múltiples dimensiones, por lo que la técnica de rotación de árboles no se puede utilizar para balancearlos, ya que esto podría romper la invariante.

Existen varias variantes de árboles k -d equilibrados. Entre ellas se incluyen el árbol k -d dividido, el árbol k -d pseudo, el árbol KDB , el árbol hB y el árbol Bkd . Muchas de estas variantes son árboles kd adaptativos .

El algoritmo de búsqueda del vecino más cercano (NN) busca el punto en el árbol que esté más próximo a un punto de entrada dado. Esta búsqueda se puede realizar de manera eficiente utilizando las propiedades del árbol para eliminar rápidamente grandes porciones del espacio de búsqueda.

La búsqueda del vecino más cercano en un árbol k -d se realiza de la siguiente manera:

1. Partiendo del nodo raíz, el algoritmo desciende por el árbol de forma recursiva, del mismo modo que lo haría si se estuviera insertando el punto de búsqueda (es decir, se mueve a la izquierda o a la derecha dependiendo de si el punto es menor o mayor que el nodo actual en la dimensión dividida).
2. Una vez que el algoritmo llega a un nodo hoja, comprueba el punto del nodo y, si la distancia es mejor que la "mejor actual", ese punto del nodo se guarda como la "mejor actual".
3. El algoritmo deshace la recursión del árbol, realizando los siguientes pasos en cada nodo:
   1. Si el nodo actual está más cerca que el mejor nodo actual, entonces se convierte en el mejor nodo actual.
   2. El algoritmo comprueba si existen puntos al otro lado del plano de división que estén más cerca del punto de búsqueda que el mejor punto actual. En teoría, esto se logra intersectando el hiperplano de división con una hiperesfera alrededor del punto de búsqueda cuyo radio sea igual a la distancia más cercana actual. Dado que todos los hiperplanos están alineados con los ejes, esto se implementa como una simple comparación para determinar si la distancia entre la coordenada de división del punto de búsqueda y el nodo actual es menor que la distancia (coordenadas generales) desde el punto de búsqueda hasta el mejor punto actual.
      1. Si la hiperesfera cruza el plano, podría haber puntos más cercanos al otro lado del plano, por lo que el algoritmo debe descender por la otra rama del árbol desde el nodo actual buscando puntos más cercanos, siguiendo el mismo proceso recursivo que toda la búsqueda.
      2. Si la hiperesfera no interseca el plano de división, el algoritmo continúa avanzando por el árbol y se elimina toda la rama que se encuentra al otro lado de ese nodo.
4. Cuando el algoritmo finaliza este proceso para el nodo raíz, la búsqueda se considera completa.

Generalmente, el algoritmo utiliza distancias al cuadrado para la comparación, evitando así el cálculo de raíces cuadradas. Además, puede ahorrar tiempo de cálculo almacenando en una variable la distancia al cuadrado óptima para su posterior comparación.

El algoritmo puede ampliarse de diversas maneras mediante modificaciones sencillas. Puede proporcionar los k vecinos más cercanos a un punto manteniendo k de los mejores resultados actuales en lugar de solo uno. Una rama se elimina únicamente cuando se han encontrado k puntos y no puede tener puntos más cercanos que ninguno de los k mejores resultados actuales.

También se puede convertir en un algoritmo de aproximación para que se ejecute más rápido. Por ejemplo, la búsqueda aproximada del vecino más cercano se puede lograr simplemente estableciendo un límite superior en el número de puntos a examinar en el árbol o interrumpiendo el proceso de búsqueda en función de un reloj en tiempo real (lo que puede ser más apropiado en implementaciones de hardware). El vecino más cercano para los puntos que ya están en el árbol se puede lograr no actualizando el refinamiento para los nodos que dan una distancia cero. Como resultado, esto tiene la desventaja de descartar puntos que no son únicos pero que están ubicados en la misma posición que el punto de búsqueda original.

El método del vecino más cercano aproximado es útil en aplicaciones en tiempo real, como la robótica, debido al aumento significativo de velocidad que se obtiene al no buscar exhaustivamente el mejor punto. Una de sus implementaciones es la búsqueda primero del mejor contenedor .

Una búsqueda de rango busca rangos de parámetros. Por ejemplo, si un árbol almacena valores correspondientes a ingresos y edad, una búsqueda de rango podría consistir en buscar todos los miembros del árbol cuya edad esté entre 20 y 50 años y cuyos ingresos estén entre 50 000 y 80 000. Dado que los árboles kd dividen el rango de un dominio por la mitad en cada nivel del árbol, son útiles para realizar búsquedas de rango.

Los análisis de árboles de búsqueda binaria han encontrado que el tiempo en el peor caso para la búsqueda de rango en un árbol k -dimensional k -d que contiene n nodos viene dado por la siguiente ecuación. ^{[ 12 ]}

${\displaystyle t_{\text{peor}}=O\left(k\cdot n^{1-{\frac {1}{k}}}\right)}$

En lugar de puntos, un árbol k -d también puede contener rectángulos o hiperrectángulos . ^{[ 15 ] [ 16 ]} Por lo tanto, la búsqueda de rango se convierte en el problema de devolver todos los rectángulos que intersecan el rectángulo de búsqueda. El árbol se construye de la forma habitual con todos los rectángulos en las hojas. En una búsqueda de rango ortogonal , se utiliza la coordenada opuesta al comparar con la mediana. Por ejemplo, si el nivel actual se divide a lo largo de x _alto , comprobamos la coordenada x _bajo del rectángulo de búsqueda. Si la mediana es menor que la coordenada x _bajo del rectángulo de búsqueda, entonces ningún rectángulo en la rama izquierda puede intersecar con el rectángulo de búsqueda y, por lo tanto, se puede podar. De lo contrario, se deben recorrer ambas ramas. Véase también árbol de intervalo , que es un caso especial unidimensional.

También es posible definir un árbol k -d con puntos almacenados únicamente en las hojas. ^{[ 4 ]} Esta forma de árbol k -d permite una variedad de mecanismos de división distintos de la división mediana estándar. La regla de división del punto medio ^{[ 17 ]} selecciona en el medio del eje más largo del espacio que se está buscando, independientemente de la distribución de los puntos. Esto garantiza que la relación de aspecto será como máximo 2:1, pero la profundidad depende de la distribución de los puntos. Una variación, llamada punto medio deslizante, solo divide en el medio si hay puntos a ambos lados de la división. De lo contrario, divide en el punto más cercano al medio. Maneewongvatana y Mount muestran que esto ofrece un rendimiento "suficientemente bueno" en conjuntos de datos comunes.

Utilizando el punto medio deslizante, se puede responder a una consulta aproximada del vecino más cercano en${\displaystyle O\left({\tfrac {1}{{\epsilon \ }^{d}}}\log n\right)}$. El conteo de rango aproximado se puede responder en${\displaystyle O\left(\log n+{\left({\tfrac {1}{\epsilon \ }}\right)}^{d}\right)}$con este método.