Estructura de datos para almacenar Rangos

Question

Me pregunto si alguien sabe de una estructura de datos que manejar eficientemente la siguiente situación:

La estructura de datos debe almacenar varios, posiblemente superposición de longitud variable varía en alguna escala de tiempo continuo.

• Por ejemplo, puede agregar los rangos a:[0,3], b:[4,7], c:[0,9].

• El tiempo de inserción no necesita ser particularmente eficiente.

Retrievals tomarían un rango como un parámetro, y devolver todos los rangos en el conjunto que se solapa con el intervalo, por ejemplo:

• Get(1,2) volverían a y c. Get(6,7) devolvería b y c. Get(2,6) devolvería los tres.

• Las recuperaciones deben ser lo más eficientes posible.

Answer 1

Puede ir por un árbol binario, que almacena los rangos en una jerarquía. Comenzando por el nodo raíz, que representa un rango que lo abarca todo dividido en su centro, prueba si su rango que está tratando de insertar pertenece al subintervalo izquierdo, subintervalo derecho, o ambos, y continúa recursivamente en los subnodos coincidentes hasta que alcanzar una cierta profundidad, en la que se guarda el rango real.

Para la búsqueda, prueba tu rango de entrada contra los subintervalos izquierdo y derecho del nodo superior, y bucea en los que se superponen, repitiéndolo hasta que alcances los rangos reales que guardas.

De esta manera, la recuperación tiene una complejidad logarítmica. Aún necesitaría administrar duplicados en su recuperación, ya que algunos rangos pertenecerán a varios nodos.

Answer 2

Una estructura de datos que puede utilizar es unidimensional R-tree. Estos están diseñados para tratar rangos y para proporcionar una recuperación eficiente. También aprenderá sobre Allen's Operators; hay una docena de otras relaciones entre intervalos de tiempo que solo 'superposiciones'.

Hay otras preguntas sobre SO que inciden en esta área, incluyendo:

• SO 325933
• SO 210729