Fenómeno

Orden y altas frecuentes

Un sistema de reservas necesita dos cosas a la vez: muchas altas y bajas por segundo, y responder «las reservas entre el 3 y el 10 de mayo». El array ordenado responde rangos, pero cada alta desplaza medio array. La tabla hash da de alta en O(1) esperado, pero no sabe nada de rangos.

Hace falta una estructura que mantenga el orden sin guardar las claves contiguas.

Piensa antes de seguir: en la búsqueda binaria, la primera comparación es con el valor del medio. ¿Y si ese valor fuera un nodo que apunta a «la mitad menor» y a «la mitad mayor»?