¿Alguien sabe de una estructura de datos que soporte las dos operaciones de manera eficiente?

Inserte un valor en la estructura de datos.Reduzca y devuelva una entrada de la estructura de datos con probabilidad aleatoria uniforme.

Esto es algo así como la "bolsa de canicas" canónica que siempre aparece en las clases introductorias de probabilidad. Puede colocar canicas arbitrarias en la bolsa, y luego puede eliminar las canicas de manera eficiente al azar.

La mejor solución que tengo es la siguiente: use un árbol de búsqueda binaria con equilibrio automático (AVL, AA, rojo / negro, etc.) para almacenar los elementos. Esto da tiempo de inserción de O (lg n). Para eliminar un elemento aleatorio, elija un índice aleatorio i, luego ubique y elimine el elemento i-ésimo del árbol. Si ha aumentado la estructura de manera adecuada, también se puede hacer que se ejecute en tiempo O (lg n).

Este tiempo de ejecución ciertamente no es malo, pero tengo curiosidad por saber si es posible hacerlo mejor, ¿tal vez O (1) para inserción y O (lg n) para dequeues? O tal vez algo que corre enesperado O (1) insertar y eliminar usando funciones hash? ¿O tal vez un límite amortizado más fuerte?

¿Alguien tiene alguna idea sobre cómo hacer esto asintóticamente más rápido?