Abstract:
|
Los kd-trees y los quad-trees son estructuras de datos que sirven
para almacenar claves multidimensionales. Ambas son generalizaciones de
los más conocidos árboles binarios de búsqueda que almacenan claves unidimensionales.
Tanto los kd-trees como los quad-trees permiten acceder a las claves que
almacenan mediante distintos modelos de búsqueda como pueden ser, entre
otras:
a) las búsquedas exactas que consisten en determinar si una clave dada está
o no almacenada en la estructura o,
b) las búsquedas por proximidad que consisten en determinar qué claves de
la estructura son cercanas o próximas a una clave dada, bajo una medida de
proximidad previamente determinada.
Ambas estructuras soportan también operaciones de actualización como
son las inserciones de nuevas claves o el borrado de claves ya existentes.
En general, la eficiencia de los algoritmos tanto de búsqueda como de actualización
está directamente relacionada con la forma de los árboles en que
se realizan. Una manera de obtener un coste eficiente en promedio (esperado)
consiste en garantizar que los árboles se construyen con claves multidimensionales
generadas al azar de manera uniforme e independiente, a dichos
árboles se les conoce como árboles aleatorios.
Sin embargo, las aplicaciones que requieran de estructuras de datos multidimensionales
pueden ser muy diversas y no puede suponerse en general que
las claves cumplirán con las características de aleatoriedad mencionadas. Este
problema puede resolverse utilizando algoritmos de actualización aleatorizados,
estos algoritmos preservan y producen árboles aleatorios a pesar de que
las claves no hayan sido generadas al azar.
Desafortunadamente, en el caso de árboles para claves multidimensionales,
no se conocen algoritmos aleatorizados de inserción eficientes (de coste
promedio logarítmico respecto al número de claves en el árbol) ni para kdtrees
de dimensión mayor a dos ni para quad-trees.
En el año 2006, Nicholas Broutin, Ketan Dalal, Luc Devroye, y Erin
McLeish propusieron, en su artículo titulado “The kd-treap” [19], un algoritmo
aleatorizado de inserción de claves en kd-trees al que llamaron algoritmo
de inserción copy-based. En el mismo trabajo, los autores afirman que
el coste promedio de este algoritmo es de orden sublineal con respecto al
tamaño del árbol al que se aplica. Sin embargo, esta afirmación no ha podido
demostrarse formalmente.
En este trabajo se consigue demostrar que dicha afirmación es falsa mediante
un análisis experimental del coste promedio del algoritmo de inserción
copy-based aplicado a kd-trees y a quad-trees aleatorios. Más aún,
se muestra que el coste promedio del algoritmo de inserción copy-based en
kd-trees y quad-trees es asintóticamente el mismo que el de reconstruir totalmente
el subárbol afectado por la inserción, y por tanto es O(n log n) en
promedio, para subárboles de n claves [21].
10 |