Estructura de datos con búsqueda, inserción y eliminación en tiempo amortizado

¿Existe una estructura de datos para mantener una lista ordenada que admita las siguientes operaciones en tiempo amortizado?$O(1)$

• GetElement (k) : devuelve el elemento de la lista.$k$

• InsertAfter (x, y) : inserte el nuevo elemento y en la lista inmediatamente después de x.

• Eliminar (x) : Eliminar x de la lista.

Para las dos últimas operaciones, puede suponer que x se proporciona como un puntero directamente en la estructura de datos; InsertElement devuelve el puntero correspondiente para y. InsertAfter (NULL, y) inserta y al principio de la lista.

Por ejemplo, comenzando con una estructura de datos vacía, las siguientes operaciones actualizan la lista ordenada como se muestra a continuación:

• InsertAfter (NULL, a) $\implies$ [una]
• InsertAfter (NULL, b) $\implies$ [b, a]
• Insertar después (b, c) $\implies$ [b, c, a]
• Insertar después (a, d) $\implies$ [b, c, a, d]
• Eliminar (c) $\implies$ [malo]

Después de estas cinco actualizaciones, GetElement (2) debería devolver d, y GetElement (3) debería devolver un error.

NO.

Fredman y Saks demostraron que cualquier estructura de datos que soporte estas operaciones requiere al menos tiempo amortizado por operación$\Omega(\log n/\log\log n)$ . (Esta es la referencia [1] en el artículo de Dietz que usted menciona en su primer comentario). El límite inferior se mantiene en el modelo de cómputo de la sonda celular muy poderoso, que solo considera el número de direcciones de memoria distintas a las que accede la actualización y la consulta algoritmos

Sin algunos supuestos adicionales sobre las operaciones de actualización y consulta, la estructura de datos de Dietz es la mejor posible (al menos hasta factores constantes).

$\Omega(\dfrac{\log n}{\log\log n})$

$\Omega(\log n)$

[1] Patrascu, Mihai y Erik D. Demaine. "Límites inferiores logarítmicos en el modelo de sonda celular". SIAM J. Comput. 35, no. 4 (abril de 2006): 932–963. doi: 10.1137 / S0097539705447256.