Skip to content

SkipList ​

SkipList<T> es un conjunto ordenado implementado sobre una skip list: una lista enlazada de nodos atravesada por carriles exprés aleatorios. Mantiene cada elemento en orden ascendente e ignora las inserciones duplicadas. Los niveles se sortean al azar hasta 16, por lo que cada búsqueda, inserción y eliminación es O(log n) en promedio, y el diseño de los carriles no requiere rebalanceo. El handle nativo se libera automáticamente cuando la variable sale del ámbito.

Construcción ​

SintaxisDescripción
SkipList<T>()Crea una nueva skip list vacía

T puede ser cualquier tipo entero, cualquier tipo de punto flotante, boolean o string.

Métodos ​

MétodoFirmaRetornaDescripción
insert(T) => booleanbooleanAgrega un elemento; retorna true cuando no estaba presente
remove(T) => booleanbooleanElimina un elemento; retorna true cuando estaba presente
contains(T) => booleanbooleanSi el elemento está en la lista
min() => T?T?Elemento más pequeño, o ningún valor si está vacío
max() => T?T?Elemento más grande, o ningún valor si está vacío
len() => usizeusizeNúmero de elementos
isEmpty() => booleanbooleanSi la lista está vacía
clear() => voidvoidElimina todos los elementos

Complejidad ​

OperaciónComplejidad Temporal
insertO(log n) esperado
removeO(log n) esperado
containsO(log n) esperado
minO(1)
maxO(n)
len / isEmptyO(1)
clearO(n)

Los límites logarítmicos esperados se cumplen para cualquier orden de inserción, porque los carriles exprés se construyen a partir de niveles aleatorios, no del historial de actualizaciones; los extremos de la lista se encuentran recorriendo el carril inferior, así que min lee el primer nodo y max camina hasta el último.

Ejemplos ​

Ejemplo completo ​

tyrus
import { SkipList } from "tyrus:algorithm";

const main = (): void => {
    const s = SkipList<i32>();
    s.insert(3);
    s.insert(1);
    s.insert(2);
    s.insert(2);

    print(s.len());        // 3 (duplicates are ignored)
    print(s.contains(2));  // true
    print(s.min() ?? 0);   // 1
    print(s.max() ?? 0);   // 3

    s.remove(2);
    print(s.contains(2));  // false
    print(s.isEmpty());    // false

    s.clear();
    print(s.isEmpty());    // true
    print(s.len());        // 0
};

Orden de strings ​

tyrus
import { SkipList } from "tyrus:algorithm";

const main = (): void => {
    const words = SkipList<string>();
    words.insert("banana");
    words.insert("apple");
    words.insert("cherry");

    print(words.min() ?? "none");  // "apple"
    print(words.max() ?? "none");  // "cherry"
};