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
| Sintaxis | Descripció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étodo | Firma | Retorna | Descripción |
|---|---|---|---|
insert | (T) => boolean | boolean | Agrega un elemento; retorna true cuando no estaba presente |
remove | (T) => boolean | boolean | Elimina un elemento; retorna true cuando estaba presente |
contains | (T) => boolean | boolean | Si 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 | () => usize | usize | Número de elementos |
isEmpty | () => boolean | boolean | Si la lista está vacía |
clear | () => void | void | Elimina todos los elementos |
Complejidad
| Operación | Complejidad Temporal |
|---|---|
insert | O(log n) esperado |
remove | O(log n) esperado |
contains | O(log n) esperado |
min | O(1) |
max | O(n) |
len / isEmpty | O(1) |
clear | O(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
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
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"
};