Soñé con una estructura de datos, ¿existe?

27

No he logrado encontrar esta estructura de datos, pero no soy un experto en el campo.

La estructura implementa un conjunto y es básicamente una matriz de elementos comparables con una invariante. La invariante es la siguiente (definida recursivamente):

Una matriz de longitud 1 es una matriz de fusión.

Una matriz de longitud 2 ^ n (para n> 0) es una matriz de combinación iff:

  • la primera mitad es una matriz de combinación y la segunda mitad está vacía o
  • la primera matriz está llena y ordenada, y la segunda mitad es una matriz de combinación.

Tenga en cuenta que si la matriz está llena, se ordena.

Para insertar un elemento, tenemos dos casos:

  • Si la primera mitad no está llena, inserte recursivamente en la primera mitad.
  • Si la primera mitad está llena, inserte recursivamente en la segunda mitad.
  • Después del paso recursivo, si toda la matriz está llena, combine las mitades (que están ordenadas) y cambie su tamaño al doble de su longitud original.

Para encontrar un elemento, recurse en ambas mitades, utilizando la búsqueda binaria cuando la matriz está llena. (Esto debería ser eficiente ya que hay como máximo fragmentos ascendentes).O(log(n))

La estructura se puede considerar como una versión estática de mergesort.

No está claro qué se debe hacer para borrar un elemento.

Editar: después de mejorar mi comprensión de la estructura.

pbaren
fuente
55
Lo definiste, por lo tanto existe. Sin embargo, creo que tienes que suavizar algunos puntos. Primero, la invariante n. ° 2 me confunde, ya que no parece aplicarse a los estados intermedios como los describe. En segundo lugar, ¿qué haces cuando se eliminan los elementos?
Raphael
77
Que soñó hasta una estructura de datos, no soñado con ella ...
Andrej Bauer
@Raphael Gracias por tus comentarios, mejoré la definición siguiendo tus pensamientos. No pensé en un algoritmo para la eliminación, solo quería verificar si esta estructura estaba en la literatura antes de dedicarle más tiempo (y no pude encontrar nada en Google). En tu primera oración, puedes definir a Dios, pero ¿existe? :)
pbaren
@Andrej Gracias, el inglés no es mi lengua materna. (Supongo que tampoco es tuyo :)
pbaren
3
@Andrej: el OP originalmente había "soñado con ", que es casi seguro que no lo estaba destinado. Lo cambié a "de" en lugar de "arriba". Ambos son correctos gramaticalmente, pero ambos también cambian el significado. "Of" fue la opción de sonido más interesante ...
András Salamon

Respuestas:

31

Está describiendo el método logarítmico clásico de Bentley-Saxe , aplicado a arreglos estáticos ordenados. La misma idea se puede usar para agregar soporte para inserciones a cualquier estructura de datos estática (sin inserciones o eliminaciones) para cualquier problema de búsqueda descomponible. (Un problema de búsqueda es descomponible si la respuesta para cualquier unión se puede calcular fácilmente a partir de las respuestas para los conjuntos A y B ). La transformación aumenta el tiempo de consulta amortizado por un factor de O ( log n ) (a menos que fuera ya más grande que algún polinomio en nUNAsiUNAsiO(Iniciar sesiónnorte)norte), pero aumenta el espacio solo en un factor constante. Sí, se puede desamortizar, gracias a Overmars y van Leeuwen, pero realmente no quieres hacerlo si no tienes que hacerlo.

Estas notas cubren los conceptos básicos.

Las matrices de búsqueda anticipada ajenas a la caché son descendientes mutantes de los árboles Bentley-Saxe y Van Emde Boas con esteroides.

Jeffε
fuente
44
Esas son notas bellamente escritas e ilustradas, y las he usado como referencia muchas veces. ¡Gracias por hacerlos disponibles!
jbapple
Veo cómo los árboles lanzadera (de la primera mitad del documento que introducen los arreglos de búsqueda anticipada ajenos al caché) están relacionados con los árboles vEB, pero ¿cuál es la relación entre los árboles COLA y los árboles vEB?
jbapple
2
Gracias, este material parece una generalización muy interesante de la idea. Siempre he pensado que las estructuras de datos son algoritmos congelados, que puedes ejecutar paso a paso, pero nunca encontré una formalización útil de esa intuición.
pbaren
¿El primer enlace funcionó para alguien más?
AL
Sí, lo acabo de probar. (Desafortunadamente, va a un paywall de Elsevier; ¡perdón!)
Jeffε
11

Esto es similar a una combinación de árboles con estructura de registro o matrices de búsqueda anticipada (o COLA) ajenas a la memoria caché .

2k-12yo0 0yo<k

20 021

O(lgnorte)O(norte)O(lg2norte)

jbapple
fuente