Las estructuras ordenadas construidas como árboles equilibrados deben reequilibrarse tras cada actualización, lo que implica rotaciones, recoloreado e invariantes cuidadosos: todo ello fácil de equivocar e incómodo de paralelizar.
Las listas con saltos sustituyen esa maquinaria por una regla probabilística. A cada nodo se le asigna un nivel extraído de una distribución que decae abruptamente, de modo que la mayoría son bajos, una minoría son altos, y una búsqueda puede saltar sobre largos tramos de niveles inferiores antes de descender.
Como los niveles son aleatorios, el número esperado de nodos por nivel es geométrico y la búsqueda, inserción y eliminación quedan todas en expectativa en O(log n). El código es corto y no hay que realizar ninguna contabilidad a posteriori.
Que los lanzamientos de moneda, y no las rotaciones, mantengan el equilibrio
Los niveles aleatorios dan la cota de altura sin código de reequilibrado.
Las operaciones locales, aptas para bloqueos, facilitan la paralelización.
La simplicidad implica menos invariantes que mantener y equivocar.
Cuando el reequilibrado determinista es la parte costosa y propensa a errores, sustitúyelo por aleatoriedad honesta: operaciones locales y sencillas dan el mismo rendimiento esperado que un invariante mantenido a mano.
Las listas con saltos se convirtieron en una alternativa estándar a los árboles en bibliotecas y bases de datos, de forma más famosa en los conjuntos ordenados de Redis, donde la simplicidad favorece la concurrencia y un rendimiento predecible.
CONSULTA LAS PRUEBAS
Las fuentes
- Skip Lists: A Probabilistic Alternative to Balanced Trees William Pugh / University of Maryland · cs.umd.edu
- Skip list Wikipedia · en.wikipedia.org