Skip list
- Fecha
- 1989 · fiabilidad alta
- Lugar
- College Park, Maryland, Estados Unidos
- Autoría
- William Pugh
- Ámbito
- Saber y símbolos
Qué es
El informático William Pugh presentó en 1989, en la Universidad de Maryland, la skip list, una estructura de datos probabilística que combina varias listas enlazadas jerárquicas para lograr búsquedas e inserciones con complejidad logarítmica media, como alternativa más simple a los árboles balanceados.
A qué dio paso
- Implementación de bases de datos como Redis y LevelDB
- Alternativa práctica a los árboles AVL y rojo-negro
- Estructuras de datos concurrentes sin bloqueo