Skip to content

SkipList ​

SkipList<T> é um conjunto ordenado implementado sobre uma skip list: uma lista encadeada de nós atravessados por pistas expressas aleatórias. Ele mantém cada elemento em ordem crescente e ignora inserções duplicadas. Os níveis são sorteados aleatoriamente até 16, então cada busca, inserção e remoção é O(log n) em média, e o layout das pistas não exige rebalanceamento. O handle nativo é liberado automaticamente quando a variável sai de escopo.

Construção ​

SintaxeDescrição
SkipList<T>()Cria uma nova skip list vazia

T pode ser qualquer tipo inteiro, qualquer tipo de ponto flutuante, boolean ou string.

Métodos ​

MétodoAssinaturaRetornaDescrição
insert(T) => booleanbooleanAdiciona um elemento; retorna true quando ele não estava presente
remove(T) => booleanbooleanRemove um elemento; retorna true quando ele estava presente
contains(T) => booleanbooleanSe o elemento está na lista
min() => T?T?Menor elemento, ou nenhum valor quando vazio
max() => T?T?Maior elemento, ou nenhum valor quando vazio
len() => usizeusizeNúmero de elementos
isEmpty() => booleanbooleanSe a lista está vazia
clear() => voidvoidRemove todos os elementos

Complexidade ​

OperaçãoComplexidade Temporal
insertO(log n) esperado
removeO(log n) esperado
containsO(log n) esperado
minO(1)
maxO(n)
len / isEmptyO(1)
clearO(n)

Os limites logarítmicos esperados valem para qualquer ordem de inserção, porque as pistas expressas são construídas a partir de níveis aleatórios, e não do histórico de atualizações; os extremos da lista são encontrados percorrendo a pista inferior, então min lê o primeiro nó e max caminha até o último.

Exemplos ​

Exemplo 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
};

Ordenação 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"
};