data-structures - kd tree python
¿Cuál es la diferencia entre un árbol KD y un árbol R? (3)
En realidad son bastante diferentes. Sirven para un propósito similar (consultas de región sobre datos espaciales), y ambos son árboles, pero eso es todo lo que tienen en común.
- Los árboles R están equilibrados , los árboles kd no (a menos que estén cargados a granel). Esta es la razón por la que los árboles-R son preferidos para cambiar los datos, ya que los árboles-kD pueden necesitar ser reconstruidos para volver a optimizar.
- Los R-Trees están orientados a disco . De hecho, organizan los datos en áreas que se asignan directamente a la representación en disco. Esto los hace más útiles en bases de datos reales y para el funcionamiento sin memoria. Los kd-trees están orientados a la memoria y no son triviales para poner en las páginas del disco
- R-Trees no cubren todo el espacio de datos. Las áreas vacías pueden estar descubiertas. los kd siempre cubren todo el espacio.
- Los binarios de kd dividen el espacio de datos, los r-trees dividen los datos en rectángulos . Las divisiones binarias son obviamente disjuntas; mientras que los rectángulos de un r-tree pueden superponerse (lo que a veces es bueno, aunque uno trata de minimizar la superposición)
- Los kd-trees son mucho más fáciles de implementar en la memoria, que en realidad es su beneficio clave
- Los árboles-R pueden almacenar rectángulos y polígonos , los árboles-kd solo almacenan vectores de puntos (ya que la superposición es necesaria para los polígonos)
- Los R-trees vienen con varias estrategias de optimización, diferentes splits, cargadores a granel, estrategias de inserción y reinserción, etc.
Miré la definición de KD-tree y R-tree. Me parece que son casi lo mismo.
¿Cuál es la diferencia entre un árbol KD y un árbol R?
Una diferencia importante entre los dos que no se mencionan en esta respuesta es que los árboles KD solo son eficientes en situaciones de carga masiva. Una vez construido, modificar o reequilibrar un árbol KD no es trivial. Los árboles R no sufren de esto.
R-trees kd-trees se basan en ideas similares (partición espacial basada en regiones alineadas con el eje), pero las diferencias clave son:
- Los nodos en k d-trees representan planos de separación, mientras que los nodos en R-trees representan cuadros de limitación.
- k Los dbores dividen todo el espacio en regiones, mientras que los árboles R solo dividen el subconjunto de espacio que contiene los puntos de interés.
- k Los árboles d representan una partición disjunta (los puntos pertenecen a una sola región) mientras que las regiones en un árbol R pueden superponerse.
(Hay muchos tipos similares de estructuras de árbol para el espacio de partición: quadtrees, BSP-trees, R * -trees, etc., etc.)