o problema
Árvore binária de busca funciona bem quando os elementos chegam em ordem aleatória. Chegando em ordem crescente, ela degenera numa lista ligada e a busca vira linear. Se desse para permutar a entrada antes de inserir, o problema sumiria com alta probabilidade para qualquer sequência — mas consultas quase sempre são respondidas online, então permutar é impraticável. A resposta clássica é a árvore balanceada: AVL, 2-3, splay. Todas reorganizam a estrutura a cada operação para manter uma invariante e assim garantir desempenho.
O preço não aparece na notação assintótica, aparece no código. Pugh observa que implementar árvore balanceada é uma tarefa exigente e que, na prática, essas estruturas raramente são implementadas fora de exercício de disciplina de estrutura de dados. Pior: a complexidade desencoraja otimização. Insert e delete de árvore balanceada são normalmente descritos de forma recursiva porque é assim que ficam inteligíveis; a versão não recursiva, que elimina o overhead de chamada, é intimidante o bastante para que quase ninguém escreva. O algoritmo fica mais lento porque é difícil demais para ser mexido.
a ideia
Numa lista ligada ordenada, a busca examina até n nós. Se cada segundo nó também tiver um ponteiro apontando dois adiante, bastam n/2 + 1. Com ponteiro quatro adiante em cada quarto nó, n/4 + 2. Levando ao limite — cada (2^i)-ésimo nó com um ponteiro 2^i adiante —, a busca cai para log2 n dobrando apenas o número de ponteiros. Ótimo para procurar, inútil para escrever: inserir no meio obriga a reetiquetar meia estrutura.
O movimento de Pugh é olhar para a distribuição em vez do padrão. Naquele arranjo rígido, 50% dos nós são nível 1, 25% são nível 2, 12,5% são nível 3. E se os níveis fossem sorteados nessas mesmas proporções, sem exigir posição? O i-ésimo ponteiro de um nó deixa de apontar 2^(i-1) nós adiante e passa a apontar para o próximo nó de nível i ou maior. A estrutura resultante não depende da ordem em que os elementos chegaram: depende só de quantos são e do gerador de números aleatórios.
como funciona
O sorteio é uma moeda viciada em p:
randomLevel()
lvl := 1
while random() < p and lvl < MaxLevel do
lvl := lvl + 1
return lvlA busca começa no nível mais alto presente na lista e desce:
Search(list, searchKey)
x := list→header
for i := list→level downto 1 do
while x→forward[i]→key < searchKey do
x := x→forward[i]
x := x→forward[1]Insert e delete usam exatamente essa varredura, guardando num vetor update[i] o nó mais à direita de nível i ou maior que fica à esquerda do ponto de operação. Depois é só splice. O nível não precisa ser guardado no nó, e não existe informação de balanceamento ou prioridade a manter. O loop interno da deleção compila para seis instruções no 68020.
MaxLevel é fixado em L(N) = log_{1/p} N, com N sendo um limite superior de elementos: para p = 1/2 e até 2^16 elementos, 16 basta. O custo esperado da busca é limitado por L(n)/p + 1/(1-p), ou seja, O(log n), e o número de comparações é o comprimento do caminho mais um. Há uma variante tentadora — se o sorteio devolve nível maior que o máximo atual mais um, use máximo mais um — que funciona bem na prática e destrói a análise, porque o nível deixa de ser aleatório.
o que isso custou
O pior caso continua ruim; o que muda é que nenhuma sequência de entrada o produz consistentemente. Isso é bom o suficiente para tempo real com margem de segurança, mas não é um bound de pior caso, e Pugh escreve isso na conclusão: do ponto de vista teórico não há necessidade de skip lists, porque árvores balanceadas fazem tudo e com garantia mais forte.
Três limites concretos. Primeiro, a proteção depende de o usuário não ver os níveis dos nós — quem os vê apaga os que não são nível 1 e reconstrói o pior caso. Segundo, a variância não se dilui com repetição: duas buscas pelo mesmo elemento custam o mesmo tempo, e buscar sempre o mesmo item maximiza a variância do total. Terceiro, a skip list faz mais comparações que os outros métodos, L(n)/p + 1/(1-p) + 1 em média; com chaves de ponto flutuante ela ficou um pouco mais lenta que a AVL não recursiva na busca, e a busca em árvore 2-3 também foi mais rápida. Nas medições em 2^16 elementos com chaves inteiras, a busca da skip list custou 0,051 ms contra 0,046 ms da AVL. O que ganha é escrita: 0,065 ms contra 0,10 ms na inserção.
Consulta enviesada também é um ponto fraco. Árvore auto-ajustável se adapta a distribuições muito assimétricas; skip list não, e a saída sugerida é combiná-la com um cache.
onde isso aparece hoje
A consequência prática maior não está no tempo de busca, está na ausência de rotação. Como toda escrita é local, dá para atualizar a estrutura concorrentemente com pouca contenção — Pugh já reporta no artigo um algoritmo de manutenção concorrente que admite leitores ilimitados e n escritores ativos numa lista de n elementos, e que é muito mais simples que o equivalente para árvore balanceada. É esse atributo, mais que a simplicidade do código, que fez a skip list virar o padrão para a estrutura em memória de motores de armazenamento: a memtable padrão do RocksDB é uma skip list, e é ela que absorve escrita concorrente antes do flush em The Log-Structured Merge-Tree (LSM-Tree), documentado em uso de produção em Evolution of Development Priorities in Key-value Stores.
A ideia de balanceamento por sorteio também subiu de escala: Skip Graphs leva a mesma construção para uma rede distribuída, onde não existe nó central para manter invariante nenhuma e o sorteio é a única coordenação disponível. E o próprio artigo aponta a variante que substitui o gerador aleatório por uma função de hash do elemento: aí cada conjunto tem uma representação única e, com alta probabilidade, aproximadamente balanceada.