¿Qué es una skip list y cómo logra búsqueda O(log n)?

Question

Accepted Answer

Una **skip list** es una lista enlazada ordenada aumentada con múltiples niveles de **"carriles expreso"**. Los niveles superiores saltan sobre muchos nodos, por lo que la búsqueda desciende y se mueve hacia la derecha, logrando tiempo esperado **O(log n)** — como una alternativa probabilística más simple a un árbol balanceado. ## Estructura ```text L3: head ------------------------> 30 -------> NIL L2: head ----------> 17 ---------> 30 -------> NIL L1: head ----> 9 --> 17 --> 25 --> 30 --> 42 -> NIL L0: head -> 3->9->12->17->25->30->39->42 ----> NIL (full list) ``` Cada nodo se promueve a niveles superiores con probabilidad `p` (a menudo 0,5), por lo que en promedio cada nivel tiene la mitad de nodos que el de abajo. ## Búsqueda ```text search(25): start top-left, move RIGHT while next <= target, else drop DOWN a level. Repeat to level 0. ``` ```python import random def random_level(p=0.5, max_level=16): lvl = 1 while random.random() < p and lvl < max_level: lvl += 1 # coin flips decide a node's height return lvl ``` ## Complejidad | Operación | Esperada | Espacio | |---|---|---| | search | O(log n) | O(n) | | insert / delete | O(log n) | — | ## Compensaciones vs árboles balanceados - **Fortalezas:** mucho más simple de implementar que red-black/AVL; sin rotaciones; versiones concurrentes fáciles (usadas en Redis sorted sets, `ConcurrentSkipListMap` de Java). - **Debilidades:** garantías probabilísticas (no peor caso); punteros adicionales por nodo. ## Por qué es importante Las skip lists proporcionan operaciones ordenadas O(log n) similares a árboles con mucho menos código y concurrencia lock-free fácil, razón por la cual sistemas reales como Redis las eligen. Son un excelente ejemplo de usar **aleatorización** para reemplazar lógica de balanceo determinista compleja.