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

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.

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 $A\cup B$$A$$B$$O(\log n)$$n$), 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.

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é .

$2^k-1$$2^i$$0 \leq i < k$

$2^0$$2^1$

$O(\lg n)$$O(n)$$O(\lg^2 n)$