Saltar al contenido
wandres.dev
Iniciar sesión

Modelo por capas

Pares ordenados por clave

Un diccionario guarda pares clave → valor: código postal → ciudad. La clave es lo que se busca; el valor, lo que se obtiene.

Un array ordenado guarda los pares en un array, ordenados por clave:

posición 0 1 2 3
clave 050001 080001 110111 760001
valor Medellín Barranquilla Bogotá Cali

En la figura, los mismos cuatro pares. El borde grueso marca los que devuelve rango(080001, 110111): quedan juntos.

Un array ordenado de pares clave y valorCuatro pares en las posiciones 0 a 3, ordenados por clave de menor a mayor: 050001 Medellín, 080001 Barranquilla, 110111 Bogotá y 760001 Cali. Los pares de las posiciones 1 y 2, con borde grueso, son los que devuelve rango(080001, 110111): están juntos.claves en orden creciente050001Medellín0080001Barranquilla1110111Bogotá2760001Cali3clavevalorposiciónrango(080001, 110111): los pares quedan contiguos
Los mismos cuatro pares de la tabla. Borde grueso: los pares que devuelve rango(080001, 110111), uno junto al otro.

Sus operaciones:

  • buscar(k): búsqueda binaria por clave.
  • insertar(k, v): buscar la posición y desplazar para abrir el hueco.
  • rango(a, b): buscar a, y recorrer hacia la derecha mientras la clave sea menor o igual que b.

El invariante: las claves están en orden creciente, siempre.

Un agente inserta 50 al principio de [20, 40, 60, 80] sin reordenar y después busca 20, que sí está, con búsqueda binaria. ¿Qué ocurre?