Árboles binarios de búsqueda multidimensionales usados para búsquedas asociativas

Este artículo desarrolla el árbol binario de búsqueda multidimensional (o árbol k-d, donde k es la dimensionalidad del espacio de búsqueda) como una estructura de datos para el almacenamiento de información que será recuperada mediante búsquedas asociativas. Se define el árbol k-d y se proporcionan ejemplos. Se demuestra que es bastante eficiente en sus requerimientos de almacenamiento. Una ventaja significativa de esta estructura es que una única estructura de datos puede manejar muchos tipos de consultas de manera muy eficiente. Se desarrollan varios algoritmos utilitarios; sus tiempos promedio de ejecución probados en un archivo de n registros son: inserción, O (log n); eliminación de la raíz, O (n (k-1)/k); eliminación de un nodo aleatorio, O (log n); y optimización (garantiza un rendimiento logarítmico en las búsquedas), O (n log n). Se presentan algoritmos de búsqueda para consultas de coincidencia parcial con t claves especificadas con tiempo máximo de ejecución probado de O (n (k-t)/k) y para consultas de vecino más cercano con tiempo promedio observado empíricamente de O (log n). Estos rendimientos superan ampliamente los mejores algoritmos conocidos actualmente para estas tareas. Se presenta un algoritmo para manejar cualquier consulta de intersección general. El enfoque principal de este artículo es teórico. Sin embargo, se considera que los árboles k-d podrían ser muy útiles en muchas aplicaciones, y se dan ejemplos de posibles usos.