Skip lists

O(log n) de árbol balanceado a partir de listas ligadas y volados. Sin rotaciones — la aleatorización hace el balanceo.

Carriles exprés

• Carril inferior: lista ligada ordenada completa (nivel 0)
• Arriba: carriles más dispersos, cada uno ~la mitad de denso
• Búsqueda: avanza por un carril a la derecha hasta que el siguiente nodo se pase, luego baja
• Cada bajada parte a la mitad el tramo restante → O(log n)

Mira la búsqueda descender

Busca 23: avanza por el carril de arriba a la derecha, baja cerca del objetivo. Lo encuentra visitando 3 nodos de 10 — una escalera, como la búsqueda binaria.

O(log n) vs O(n)

100k elementos: lista ligada 48,000 pasos, skip list 32 → 1,500× menos. Igual que un árbol balanceado.

Alturas aleatorizadas

• Inserción: tira un volado para la altura (promueve con prob ½, repite)
• La mitad en el nivel 0, un cuarto llega al nivel 1, un octavo al nivel 2 → geométrico
• Nada se mueve nunca → sin rebalanceo, sin casos de rotación
• O(log n) ESPERADO; ninguna entrada adversaria fuerza el peor caso

Para llevar

El azar sustituye a la astucia — código con una fracción del tamaño de AVL/rojo-negro, concurrencia sencilla. Sorted sets de Redis, memtables de LevelDB, ConcurrentSkipListMap de Java. Siguiente: cache LRU — hash map + lista doblemente ligada = O(1).