Árbol kd

La versión actual de la página aún no ha sido revisada por colaboradores experimentados y puede diferir significativamente de la versión revisada el 23 de julio de 2021; las comprobaciones requieren 2 ediciones .

árbol K-dimensional

Tipo de

Árbol multidimensional Árbol de búsqueda binaria

año de invención

1975

Autor

jon bentley

Complejidad en los símbolos O

	Promedio	Lo peor
Consumo de memoria	O( n )	O( n )
Búsqueda	O ( iniciar sesión )	O( n )
Insertar	O ( iniciar sesión )	O( n )
Eliminación	O ( iniciar sesión )	O( n )

Un k -d-tree ( eng. kd tree , abreviatura de k-dimensional tree ) es una estructura de datos con particiones espaciales para ordenar puntos en un espacio k - dimensional. k -d-trees se utilizan para algunas aplicaciones, como la búsqueda de espacio de claves multidimensional (búsqueda de rango y búsqueda de vecino más cercano ). k -d-trees son un tipo especial de árboles de búsqueda binarios .

Descripción matemática

Un árbol K-dimensional es un árbol de búsqueda desequilibrado para almacenar puntos de . Ofrece una capacidad similar a la de un árbol R para buscar dentro de un rango dado de claves. En detrimento de la simplicidad de las consultas, los requisitos de memoria en lugar de . ${\matemáticas {R}}^{k}$ ${\ Displaystyle O (kn)}$ $O((registro(n))^{k-1})$

Hay kd-trees homogéneos y no homogéneos. En kd-trees homogéneos, cada nodo almacena un registro . En la variante heterogénea, los nodos internos contienen solo claves, las hojas contienen enlaces a registros.

En un árbol kd no homogéneo con un hiperplano dimensional paralelo al eje en el punto . Para la raíz, debe dividir los puntos a través del hiperplano en dos conjuntos de puntos que sean lo más grandes posible y escribir en la raíz, a la izquierda de esto, todos los puntos para los que se almacenan , a la derecha, aquellos para los que . Para el subárbol izquierdo, es necesario dividir los puntos nuevamente en un nuevo "plano dividido" y se almacena en el nodo interno. A la izquierda de esto, todos los puntos para los cuales . Esto continúa recursivamente en todos los espacios. Luego todo comienza de nuevo desde el primer espacio hasta que cada punto se puede identificar claramente a través del hiperplano. $H_{i}(t)=(x_{1},x_{2},\ldots,x_{i-1},t,x_{i+1},\ldots,x_{k})$ ${\ estilo de visualización 1 \ leq i \ leq k}$ $(k-1)$ $t$ ${\ estilo de visualización H_ {1} (t)}$ $t$ $x_{1}<t$ $x_{1}>t$ ${\ estilo de visualización H_ {2} (t)}$ $t$ $x_{2}<t$

El árbol kd se puede construir en . Se puede realizar una búsqueda de rango en , por lo que denota el tamaño de la respuesta. El requisito de memoria para el árbol en sí es limitado . $O(n(k+log(n)))$ $O(n^{1-{\frac {1}{k}}}+a)$ $a$ ${\ Displaystyle O (kn)}$

Operaciones en k -d-trees

Estructura

Estructura de árbol descrita en C++ :

constexprint N = 10 ; _ // número de espacios de teclas struct Item { // estructura del elemento int key [ N ]; // matriz de claves que definen el elemento char * info ; // información del elemento }; struct Node { // estructura de nodo de árbol Item i ; // elemento Nodo * izquierda ; // subárbol izquierdo Nodo * derecho ; // subárbol derecho }

La estructura del árbol puede variar según los detalles de la implementación del algoritmo . Por ejemplo, un nodo puede contener una matriz en lugar de un solo elemento, lo que mejora la eficiencia de la búsqueda.

Análisis de búsqueda de elementos

Obviamente, el número mínimo de elementos vistos es , y el número máximo de elementos vistos es , donde es la altura del árbol. Queda por calcular el promedio de artículos vistos . $una$ $Vaya)$ $h$ $Un}$

${\ estilo de visualización [x_{0},x_{1},x_{2},...,x_{n}]}$ es el elemento dado.

Consideremos el caso . Los elementos encontrados pueden ser: ${\ estilo de visualización h = 3}$

encontrar(t_{1}):[(x_{0}=t_{1})];A=1.

encontrar(t_{2}):[(x_{0}<t_{1})\land (x_{0}=t_{2})];A=2.

encontrar(t_{3}):[(x_{0}>t_{1})\land (x_{0}=t_{3})];A=2.

encontrar(t_{4}):[(x_{0}<t_{1})\land (x_{0}<t_{2})\land (x_{0}=t_{4})] ;A=3.

encontrar(t_{5}):[(x_{0}<X_{1})\land (x_{0}>t_{2})\land (x_{0}=t_{5})] ;A=3.

encontrar(t_{6}):[(x_{0}<t_{1})\land (x_{0}<t_{3})\land (x_{0}=t_{6})] ;A=3.

encontrar(t_{7}):[(x_{0}<t_{1})\land (x_{0}>t_{3})\land (x_{0}=t_{7})] ;A=3.

y así sucesivamente para cada espacio de claves. En este caso, la longitud de búsqueda promedio en un espacio es:

A={\frac {1+2+2+3+3+3+3}{7}}={\frac {17}{7}}\aproximadamente 2,4

El valor medio se calcula mediante la fórmula: ${\displaystyle A_{n}=\sum _{k=1}^{n}kp_{n,k))$

Queda por encontrar la probabilidad . Es igual a , donde es el número de casos, cuando y es el número total de casos. No es difícil adivinar qué . ${\ Displaystyle p_ {n, k}}$ ${\displaystyle p_{n,k}={\frac {p_{A,k}}{p_{n))))$ ${\ Displaystyle p_ {A, k}}$ ${\ estilo de visualización A = k}$ $p_{n}$ $p_{n,k}={\frac {2^{k-1}}{2^{n}-1}}$

Sustituimos esto en la fórmula para el valor promedio:

A_{n}=\sum_{k=1}^{n}kp_{n,k}=\sum_{k=1}^{n}{k{\frac {2^{k- 1}}{2^{n}-1}}}={\frac {1}{2^{n}-1}}\sum _{k=1}^{n}{k2^{k-1 }}=

={\frac {1}{2^{n}-1}}\sum_{k+1=1}^{n}{({k+1})2^{k}}={ \frac {1}{2^{n}-1}}\left(\sum _{k+1=1}^{n}{k2^{k}}+\sum _{k+1=1} ^{n}{2^{k}}\derecho)=

={\frac {1}{2^{n}-1}}\left(\sum _{k=1}^{n}{k2^{k}}+\sum _{k=1 }^{n}{2^{k}}-2^{n}-n2^{n}\right)=

={\frac {1}{2^{n}-1}}(n2^{n+2}-(n+1)2^{n+1}+2-2^{n}+ 2^{3}-1-n2^{n})={\frac{2^{n}(n-1)+1}{2^{n}-1))

es decir , donde es la altura del árbol. $A_{h}={\frac{2^{h}(h-1)+1}{2^{h}-1))$ $h$

Si pasamos de la altura del árbol al número de elementos, entonces:

A_{n}=~O\left({\frac {2^{h}(h-1)+1}{2^{h}-1}}\right)=~O\left(h {\frac {2^{h}}{2^{h}-1}}-1\right)=~O\left(log\left({\frac {n}{N}}+1\right) {\frac {2^{log\left({\frac {n}{N}}+1\right))){2^{log\left({\frac {n}{N}}+1\right )}-1}}-1\right)=~O\left(log\left({\frac {n}{N}}+1\right){\frac {n+N}{n}}-1 \derecho)=

$=~O\left(log\left({\frac {n}{N}}+1\right)^{\frac {n+N}{n}}-1\right)$ , donde es el número de elementos en el nodo. $norte$

De esto podemos concluir que cuantos más elementos contenga el nodo, más rápida será la búsqueda del árbol, ya que la altura del árbol seguirá siendo mínima, pero no debe almacenar una gran cantidad de elementos en el nodo, ya que con este método, todo el árbol puede degenerar a una matriz o lista normal.

Adición de elementos

La adición de elementos se produce exactamente igual que en un árbol de búsqueda binaria normal , con la única diferencia de que cada nivel del árbol también estará determinado por el espacio al que pertenece.

Algoritmo de progresión del árbol:

for ( int i = 0 ; tree ; i ++ ) // i es el número del espacio if ( tree -> x [ i ] < tree -> t ) // t es la mediana tree = tree -> left ; // mover al subárbol izquierdo else árbol = árbol -> derecha ; // mover al subárbol derecho

La suma se realiza después de , donde es la altura del árbol. $Vaya)$ $h$

Eliminando elementos

Al eliminar elementos del árbol, pueden surgir varias situaciones:

Eliminar una hoja de árbol es una eliminación bastante simple, cuando se elimina un nodo y el puntero del nodo antecesor simplemente se restablece a cero.

Eliminar un nodo de árbol (no una hoja) es un procedimiento muy complicado, en el que debe reconstruir todo el subárbol para este nodo.

A veces el proceso de borrar un nodo se soluciona modificando el kd-tree. Por ejemplo, si nuestro nodo contiene una matriz de elementos, cuando se elimina la matriz completa, el nodo del árbol permanece, pero ya no se escriben nuevos elementos allí.

Encontrar una gama de elementos

La búsqueda se basa en el descenso normal del árbol, donde cada nodo se comprueba en busca de un rango. Si las medianas de un nodo son menores o mayores que un rango dado en un espacio dado, entonces el recorrido continúa a lo largo de una de las ramas del árbol. Si la mediana del nodo está completamente dentro del rango dado, entonces se deben visitar ambos subárboles.

Algoritmo Z - nodo de árbol [( x_0_min , x_1_min , x_2_min ,..., x_n_min ),( x_0_max , x_1_max , x_2_max ,..., x_n_max )] - rango especificado Matriz de funciones ( nodo * y Z ) { Si ([ x_0_min , x_1_min , x_2_min ,..., x_n_min ] < Z ){ Z = Z -> izquierda ; // subárbol izquierdo } más Si ([ x_0_máx , x_1_máx , x_2_máx ,..., x_n_máx ] > Z ){ Z = Z -> derecha ; // subárbol derecho } Else { // ver ambos subárboles de Array ( Z -> right ); // ejecuta la función para el subárbol derecho Z = Z -> izquierda ; // ver el subárbol izquierdo } } Análisis

Obviamente, el número mínimo de elementos vistos es , donde es la altura del árbol. También es obvio que el número máximo de elementos vistos es , es decir, viendo todos los elementos del árbol. Queda por calcular el promedio de artículos vistos . $Vaya)$ $h$ ${\ estilo de visualización O (2 ^ {h} -1)}$ $Un}$

$[(x_{0_{min}},x_{1_{min}},x_{2_{min}},...,x_{n_{min}}),(x_{0_{max}} ,x_{1_{máx}},x_{2_{máx}},...,x_{n_{máx}})]$ - rango dado.

El artículo original sobre kd-trees da la siguiente característica: para un rango fijo. $A_{n}=~O(h\cdot log(h))$

Si pasamos de la altura del árbol a la cantidad de elementos, entonces esto será: $A_{n}=~O(registro(registro(n-1))^{registro(n-1)})$

Encontrar al vecino más cercano

La búsqueda del elemento más cercano se divide en dos subtareas: determinar el posible elemento más cercano y encontrar los elementos más cercanos en un rango dado.

Dado un árbol . Descendemos el árbol a sus hojas por condición y determinamos el elemento más cercano probable por condición . Después de eso, desde la raíz del árbol, se lanza el algoritmo para encontrar el elemento más cercano en el rango dado, que está determinado por el radio . ${\árbol de estilo de visualización}$ $árbol\a x[i](<,>=)árbol\a t$ $l_{min}={\sqrt {(({x_{0}-x[i]_{0)))^{2}+({x_{1}-x[i]_{1} })^{2}+...+({x_{n}-x[i]_{n}})^{2})}}$ $R=l_{min}={\sqrt {(({x_{0}-x[i]_{0)))^{2}+({x_{1}-x[i]_{ 1}})^{2}+...+({x_{n}-x[i]_{n}})^{2})}}$

El radio de búsqueda se ajusta cuando se encuentra un elemento más cercano.

Algoritmo Z es la raíz del árbol . Lista - una lista de los elementos más cercanos encontrados [ x_0 , x_1 , x_2 ..., x_n ] - coordenadas de todas las dimensiones de nuestro elemento , para las cuales el más cercano Longitud - longitud mínima NIÑOS - el número máximo de niños para cada elemento Maybe_Near function ( Node *& Z ) { // busca el elemento más cercano posible while ( Z ) { for ( i = 0 ; i < N ; i ++ ) { // comprobar elementos en el nodo len_cur = sqrt (( x_0 - x [ i ] _0 ) ^ 2 + ( x_1 - x [ i ] _1 ) ^ 2 + . .. + ( x_n - x [ i ] _n ) ^ 2 ); // longitud del elemento actual if ( Long > longitud del elemento actual ) { Len = len_cur ; // establece una nueva longitud Eliminar ( Lista ); // limpiando la lista Agregar ( Lista ); // agrega un nuevo elemento a la lista } else if ( las longitudes son iguales ) { Añadir ( Lista ); // agregar un nuevo elemento a la lista } si (( x_0 == x [ i ] _0 ) && ( x_1 == x [ i ] _1 ) && ... && ( x_n == x [ i ] _n )) { devolver 1 ; } } si ([ x_0 , x_1 , x_2 ..., x_n ] < Z ) Z = Z -> izquierda ; // subárbol izquierdo si ([ x_0 , x_1 , x_2 ..., x_n ] > Z ) Z = Z -> derecha ; // subárbol derecho } } Function Near ( Node *& Z ) { // busca recursivamente el elemento más cercano en el rango dado if ( ! Z ) { volver Lista ; } len_cur = sqrt (( x_0 - x [ i ] _0 ) ^ 2 + ( x_1 - x [ i ] _1 ) ^ 2 + ... + ( x_n - x [ i ] _n ) ^ 2 ); // distancia de nuestro punto al actual if ( len_cur < Len ) { // encontramos una longitud menor que la mínima Len = len_cur ; // establecer una nueva longitud mínima Delete ( List ); // limpiando la lista - después de todo, todos los elementos encontrados hasta ahora están más lejos que el actual Add ( List , Z ); // añade el elemento actual a la lista } else if ( len_cur == Len ) { // la longitud es igual al mínimo Add ( List , Z ); // simplemente agregue un nuevo elemento a la lista } for ( i = 0 ; i < CHILDREN ; i ++ ) { // hacer lo mismo para todos los niños Near ( Z -> children [ i ]); // ver todos los subárboles } } Análisis

Obviamente, el número mínimo de elementos vistos es , donde h es la altura del árbol. También es obvio que el número máximo de elementos vistos es , es decir, viendo todos los nodos. Queda por calcular el número promedio de elementos vistos. $Vaya)$ ${\ estilo de visualización O (2 ^ {h} -1)}$

${\ estilo de visualización [(x_{0},x_{1},x_{2},...,x_{n})]}$ es un elemento dado con respecto al cual desea encontrar el más cercano. Esta tarea se divide en dos subtareas: encontrar el elemento más cercano en un nodo y encontrar el elemento más cercano en un rango dado. Para resolver el primer subproblema, se requiere un descenso a lo largo del árbol, es decir, . $Vaya)$

Para la segunda subtarea, como ya hemos calculado, la búsqueda de elementos en un rango dado toma . Para encontrar el promedio, simplemente suma estos dos valores: $O(h\cdot log(h))$

$=~O(h)+~O(h\cdot log(h))=~O(h)\cdot ({~O(log(h))+1}))$ .

Véase también

Notas

Enlaces

libkdtree++ , una implementación similar a STL de código abierto de árboles k -d en C++.
Un tutorial sobre árboles KD
FLANN y su bifurcación nanoflann , implementaciones C++ eficientes de algoritmos de árbol k -d.
kdtree Una biblioteca C simple para trabajar con KD-Trees
Demostración de KD Tree, applet de Java . Archivado el 29 de junio de 2020 en Wayback Machine .
libANN La biblioteca vecina más cercana aproximada incluye una implementación de árbol k -d
Caja de herramientas de búsqueda de imágenes a gran escala de Caltech : una caja de herramientas de Matlab que implementa un árbol k -d aleatorio para una búsqueda rápida aproximada del vecino más cercano, además de los algoritmos de búsqueda LSH , Hierarchical K-Means y Archivo invertido .
Algoritmos de disparo de rayos heurísticos , págs. 11 y después
Into contiene implementaciones de código abierto de métodos de búsqueda (k)NN exactos y aproximados utilizando k -d árboles en C++.

Árbol (estructura de datos)
Árbol de búsqueda binario Árbol (teoría de grafos) estructura de árbol
Árboles binarios	árbol binario árbol en T
Árboles binarios autoequilibrados	árbol AA árbol AVL árbol rojo-negro árbol de juego árbol con multas árbol cartesiano árbol de fibonacci árbol B árbol en T
árboles B	2-3-árbol árbol B⁺ árbol B* B x -árbol árbol de la UB 2-3-4 árbol (a,b)-árbol arbol bailando
árboles de prefijo	árbol de sufijos Árbol de prefijos comprimido Árbol de búsqueda ternario
Partición binaria del espacio	árbol k-dimensional árbol de vicepresidentes
Árboles no binarios	Árbol cuádruple octárbol Octree voxel disperso árbol exponencial árbol PQ
Rompiendo el espacio	R-árbol Árbol R de Hilbert R+-árbol R*-árbol árbol X M-árbol árbol de fenwick Árbol de segmentos
Otros árboles	montón árbol de hachís árbol de los dedos árbol métrico árbol de revestimiento árbol BK Árbol de doble cadena iDistancia Árbol de corte de enlace árbol LSM
Algoritmos	Primera búsqueda en amplitud Primera búsqueda en profundidad algoritmo DSW protocolo de árbol de expansión

Estructuras de datos
Liza	formación lista enlazada simple lista doblemente enlazada lista de pases
Árboles	árbol B Árbol de búsqueda binario árbol AVL árbol rojo-negro montón
cuenta	Gráfico dirigido Gráfico Acíclico Dirigido Diagrama de decisión binaria Hipergrafo
Otro	Tabla de picadillo Pila