Skip List

O problema: três estruturas, três buracos

Antes de entender por que a skip list existe, vale olhar o que ela veio consertar. Três estruturas que você já conhece resolvem parte do problema de manter dados ordenados, e cada uma deixa um buraco.

O array ordenado é imbatível para ler: com o índice em mãos, nums[i] custa O(1), e a busca binária acha qualquer valor em O(log n). O buraco aparece na hora de mexer. Como o array ocupa posições contíguas na memória, remover o elemento da posição 500 de um array de 1.000 obriga os 499 seguintes a andarem uma casa para trás. Inserir é a mesma coisa ao contrário. Sempre O(n).

Um parêntese honesto, antes de seguir: aquele O(1) do array é acesso por índice. Se você tem só o valor e precisa descobrir onde ele está, o array não te dá nada de graça, é O(n) igual à lista, ou O(log n) se ele estiver ordenado. Comparar "array O(1)" com "lista O(n)" sem esse detalhe é comparar coisas diferentes. Para busca por chave em O(1) o caminho é outro, é a tabela hash, que em compensação não guarda ordem nenhuma.

A lista encadeada inverte o jogo. Como cada nó vive por conta própria na memória e só guarda um ponteiro para o vizinho, remover é trocar duas setas de lugar: O(1), sem deslocar massa nenhuma. O buraco é chegar lá. Para acessar o elemento 536 você passa pelos 535 anteriores, um por um. E, o mais importante para este tópico: não existe busca binária em lista encadeada. Busca binária precisa pular direto para o meio, e numa lista o meio só existe depois de n/2 passos. O ganho evapora.

A árvore balanceada (AVL, Red-Black) resolve os dois lados: busca, inserção e remoção em O(log n) garantido, inclusive no pior caso. O buraco dela não é de desempenho, é de complexidade de código. Manter a invariante de balanceamento exige rotações, casos de recoloração, e um punhado de situações que você precisa acertar todas. É código difícil de escrever, difícil de revisar e difícil de tornar concorrente.

A skip list, criada por William Pugh em 1989 e publicada na Communications of the ACM em 1990, é a tentativa de pegar a flexibilidade da lista encadeada, o desempenho da árvore balanceada e cobrar por isso um preço bem mais barato em linhas de código. O subtítulo do artigo original dele diz exatamente isso: uma alternativa probabilística às árvores balanceadas.

A ideia: uma pista expressa por cima da lista

Pegue uma lista encadeada ordenada e construa, por cima dela, uma segunda lista com alguns dos mesmos nós. Depois uma terceira, com alguns dos nós da segunda. E assim por diante.

Cada lista dessas é um nível. O nível 0 é a lista original e contém todos os elementos, é a garantia de que nada se perde. Cada nível acima é um índice do nível de baixo, com menos nós e, por consequência, com saltos maiores. É o mesmo desenho de um metrô com linha expressa: a linha local para em todas as estações, a expressa para em uma a cada duas, e você usa a expressa até perto do destino antes de descer para a local.

Duas consequências importantes caem direto dessa ideia:

class No:
    def __init__(self, valor, altura):
        self.valor = valor
        self.forward = [None] * altura   # um ponteiro por nível em que ele vive

Repare no que não está aí: não existe ponteiro para o nó anterior, nem ponteiro para o nível de baixo. Descer um nível é só trocar o índice de forward no mesmo nó. É a dúvida que mais rende aqui, e ela fecha quando você percebe que o i do laço é o nível, não a posição.

A busca: começa no topo e desce em escada

A regra da busca cabe em duas linhas:

1. No nível atual, avance enquanto o próximo nó existir e for menor que o alvo.
2. Quando não der mais para avançar, desça um nível e repita.

Quando você não puder mais descer (chegou ao nível 0), o único candidato possível é o vizinho imediato à direita de onde você parou. Se ele não for o alvo, o alvo não existe na lista.

Comece pelo preset "A escada completa: procurar o 73". A lista tem 12 elementos distribuídos em 4 níveis, na pirâmide exata da teoria: 12 nós no nível 0, 6 no nível 1, 3 no nível 2 e 1 no nível 3. Rode passo a passo e acompanhe a linha azul, a escada. Ela sai do head lá em cima, pula direto para o 42, tenta seguir e não consegue, desce, desce de novo, anda até o 59 e só então cai no nível 0 para conferir o 73.

Agora olhe os dois contadores embaixo. A skip list gastou 6 comparações. A mesma busca andando só pelo nível 0, que é exatamente o que uma lista encadeada comum faria, gastaria 10. Com 12 elementos a diferença é uma curiosidade. Troque o preset para "Lá no fim: procurar o 92" e o placar fica 6 contra 12: a skip list nem sentiu o alvo estar mais longe, e a lista comum sentiu tudo.

Agora o preset que estraga a festa: "Antes de todos: procurar o 1". O placar fica 5 contra 2, e desta vez quem perde é a skip list. Faz sentido: ela desce os quatro níveis um a um, comparando o primeiro nó de cada um, enquanto a lista comum olha o 3, vê que já passou e desiste. O atalho tem um custo fixo de descida que você paga sempre, e ele só se paga quando o alvo está longe. É a mesma lógica de pegar o metrô para andar um quarteirão. Com "Um elemento só: procurar o 42" os dois empatam em 2, pelo mesmo motivo. Esta estrutura é feita para escala, e o visualizador mostra exatamente onde ela ainda não vale a pena.

def buscar(self, alvo):
    atual = self.head
    for nivel in range(self.nivel_max, -1, -1):
        prox = atual.forward[nivel]
        while prox and prox.valor < alvo:
            atual = prox
            prox = atual.forward[nivel]
    atual = atual.forward[0]
    return atual is not None and atual.valor == alvo

Repare que o laço externo sempre desce até o nível 0, sem exceção. Não existe "achei no nível 2 e parei": o teste de igualdade acontece uma vez só, no fim, sobre o vizinho do nível 0. É o que mantém o código simples, e o custo disso é uma comparação a mais.

Isso não é busca binária, embora a intuição seja parecida. A busca binária pula para o meio exato do que sobrou; a skip list nunca sabe onde é o meio, ela só descarta blocos inteiros porque um atalho passou por cima deles. O efeito na complexidade é o mesmo, o mecanismo não é. Confundir os dois faz muita gente tentar implementar uma coisa que não existe.

A moeda: a altura de cada nó é sorteada uma vez só

Falta a pergunta que decide tudo: quem sobe para o nível 1? A resposta óbvia seria "um nó a cada dois", e a resposta óbvia é a errada.

Pense no que aconteceria com essa regra. Você insere um elemento no meio da lista e, para manter o "um a cada dois", precisa promover o vizinho da direita, o que desloca a paridade de todos os seguintes, o que obriga a rebaixar outro, e você acabou de reinventar o rebalanceamento que queria evitar. Remover é pior ainda. A estrutura perfeitinha do desenho de livro é justamente a mais cara de manter.

A skip list resolve isso jogando a decisão fora. Quando um nó é inserido, ela lança uma moeda:

• Cara, o nó sobe mais um nível. Jogue de novo.
• Coroa, o nó para por ali.

import random

MAX_NIVEL = 5   # teto de altura, para nenhum nó fugir para o infinito
P = 0.5         # a moeda

def sortear_altura():
    altura = 1
    while random.random() < P and altura < MAX_NIVEL:
        altura += 1
    return altura

São cinco linhas de corpo. Não existe caso especial, não existe invariante para conferir, não existe rotação. É esse pedaço de código que substitui todo o aparato de balanceamento de uma AVL, e é por isso que a skip list é considerada a alternativa simples às árvores.

Isso tem uma consequência que surpreende: a skip list não é determinística na forma. Rode a mesma inserção duas vezes com o mesmo conjunto de dados e você obtém dois desenhos diferentes na memória. O que é determinístico é o resultado: buscar o 73 devolve o 73 nas duas execuções, e percorrer o nível 0 devolve os mesmos elementos na mesma ordem. Volte ao visualizador da busca, clique em "Sortear alturas" três ou quatro vezes e confira: a escada muda de formato toda vez, o contador oscila, e o veredito continua o mesmo.

Inserção e remoção: o rastro de candidatos

Inserir tem um detalhe que a busca não tem. Para religar os ponteiros, você precisa saber quem era o vizinho da esquerda do novo nó em cada nível, e não só no nível 0. A boa notícia é que a busca já passa por todos eles: toda vez que ela desce um degrau, o nó onde ela estava é exatamente o candidato daquele nível.

Basta anotar. É o vetor update, o bread crumb: um rastro com um candidato por nível, na volta.

Na aba Inserir, rode o preset "Caso comum: inserir o 33 (altura 2)" com calma e olhe o painel update[]. Ele já nasce inteiro apontando para o head, e cada descida da busca troca uma posição por um candidato de verdade. Ao fim da descida ele fica assim: update[0] = 31, update[1] = 23, update[2] = 9, update[3] = head, update[4] = head. Aí a moeda decide altura 2, e só os níveis 0 e 1 são religados: o 31 passa a apontar para o 33 no nível 0, o 23 passa a apontar para o 33 no nível 1. Quatro ponteiros mudaram de lugar. Mais nada na lista se mexeu.

def inserir(self, valor):
    atual = self.head
    update = [self.head] * MAX_NIVEL
    for nivel in range(self.nivel_max, -1, -1):
        prox = atual.forward[nivel]
        while prox and prox.valor < valor:
            atual = prox
            prox = atual.forward[nivel]
        update[nivel] = atual
    altura = self.sortear_altura()
    self.nivel_max = max(self.nivel_max, altura - 1)
    novo = No(valor, altura)
    for nivel in range(altura):
        novo.forward[nivel] = update[nivel].forward[nivel]
        update[nivel].forward[nivel] = novo

As duas últimas linhas são o velho truque de lista encadeada: o novo aponta para quem estava à frente, o anterior aponta para o novo. A skip list só repete isso uma vez por nível. Dois ponteiros por nível, então: uma inserção de altura 3 reescreve 6 ponteiros, e mais nada.

A remoção é a mesma música. Mesma busca, mesmo update, e depois um desligamento por nível:

def remover(self, valor):
    atual = self.head
    update = [self.head] * MAX_NIVEL
    for nivel in range(self.nivel_max, -1, -1):
        prox = atual.forward[nivel]
        while prox and prox.valor < valor:
            atual = prox
            prox = atual.forward[nivel]
        update[nivel] = atual
    alvo = atual.forward[0]
    if alvo is None or alvo.valor != valor:
        return False
    for nivel in range(self.nivel_max + 1):
        if update[nivel].forward[nivel] is not alvo:
            break
        update[nivel].forward[nivel] = alvo.forward[nivel]
    while self.nivel_max > 0 and self.head.forward[self.nivel_max] is None:
        self.nivel_max -= 1
    return True

Aqui o custo é um ponteiro por nível, não dois: quem sai não precisa ser religado a nada, então basta o candidato passar a apontar por cima dele. É uma assimetria pequena e que vale registrar, porque ela aparece no contador do visualizador.

O break no meio merece atenção, porque não é óbvio. Se o candidato de um nível não aponta para o nó que estamos removendo, é porque o nó nunca chegou àquele nível. E, como a altura é contínua de baixo para cima, se ele não chegou ali não chegou em nenhum acima. Nada mais a desligar. O while do fim só encolhe o topo quando o nível mais alto ficou vazio.

Troque para a aba Remover do visualizador e rode os quatro presets nesta ordem, prevendo cada um antes:

• "Caso comum: remover o 59 (altura 2)". O update fica [50, 42, 42, 42, head], e o 59 vive só nos níveis 0 e 1. Repare que o desligamento para no nível 2: ali quem vem depois do 42 é o 73, não o 59, e o break dispara. Dois ponteiros reescritos, embora o update tenha guardado um candidato nos quatro níveis: guardar é de graça, usar é que depende da altura do nó.
• "O mais alto: remover o 42". Este é o único nó do nível 3. Os quatro níveis são desligados, o laço termina sem break, e aí o while do fim entra em ação: head.forward[3] virou None, então nivel_max cai de 3 para 2 e a lista inteira ficou um andar mais baixa. Sem nenhuma rotação, sem nenhum vizinho promovido para tapar o buraco.
• "Só no nível 0: remover o 3". Todo o update é o head, e o break dispara já no nível 1.
• "Não existe: remover o 33". A busca roda inteira, o candidato do nível 0 é o 42, 42 != 33, e a função devolve False sem tocar em ponteiro nenhum. Remover o que não existe custa exatamente uma busca.

Repare no que não aparece em nenhuma das duas operações: nenhuma rotação, nenhuma recoloração, nenhuma verificação de invariante. Toda operação é local, mexe em no máximo dois ponteiros por nível do nó afetado, e não toca em mais ninguém. É exatamente essa localidade que torna a skip list fácil de tornar concorrente, e é por isso que a JDK escolheu skip list, e não árvore, para o seu mapa ordenado thread-safe: numa árvore, uma rotação move nós que estão longe do ponto de inserção, e travar isso com segurança é difícil.

O head: o sentinela que quase ninguém desenha

Os desenhos bonitinhos de skip list escondem uma peça, e a ausência dela derruba qualquer implementação. Todo nível começa em algum lugar, e esse lugar é o head, um nó sentinela sem valor nenhum.

class SkipList:
    def __init__(self):
        self.head = No(None, MAX_NIVEL)   # sentinela: sempre com o teto de ponteiros
        self.nivel_max = 0                # o nível mais alto ocupado até agora

Esse é também o motivo de update ser inicializado com [self.head] * MAX_NIVEL em vez de ficar vazio. A busca só percorre até nivel_max, o topo atual; os níveis acima disso nunca são visitados e nunca gravam nada em update. Se o nó novo sortear uma altura que passa do topo, os níveis recém-criados já encontram o head esperando lá, que é a resposta certa: se ninguém chegou àquele andar ainda, quem aponta para o primeiro morador é o próprio head.

De onde sai o log n, e por que ele é esperado e não garantido

Com a moeda em mãos, a conta é curta. Se cada nó sobe com probabilidade p, o nível 0 tem todos os n nós, o nível 1 tem em média n × p, o nível 2 tem n × p², e o nível k tem n × p^k. Com p = 0,5 isso é a pirâmide clássica: 100%, 50%, 25%, 12,5%, 6,25%.

O nível mais alto que ainda tem alguém é o maior k em que n × p^k ≥ 1. Resolvendo, k ≤ log(n) na base 1/p. É daí, e só daí, que sai o log n da skip list. Ele não é uma garantia estrutural como na AVL, é a consequência aritmética de uma pirâmide que encolhe por um fator constante a cada andar.

O visualizador abre em n = 1.024 com p = 0,5, e mostra a pirâmide inteira: 1.024 nós no nível 0, 512 no nível 1, 256 no 2, e assim até o nível 10, que tem 1 nó esperado. São 11 níveis, porque o logaritmo de 1.024 na base 2 é exatamente 10. Arraste o n até 1.048.576 e a lista vai para 21 níveis com cerca de 42 comparações por busca. Um milhão de elementos, quarenta e poucas comparações. É o mesmo espírito da busca binária, comprado por um preço diferente.

De onde sai esse 42? O cartão "comparações na busca" não chuta, ele calcula a fórmula do artigo do Pugh:

# custo esperado de uma busca, em passos
#     log(n) na base 1/p   ...  quantos níveis a busca desce
#     dividido por p       ...  quantos nós ela visita em média por nível
#     mais 1 / (1 - p)     ...  a caminhada final no nível 0
custo = math.log(n, 1 / p) / p + 1 / (1 - p)

Com n = 1.048.576 e p = 0,5 isso dá 20 / 0,5 + 2 = 42. As duas parcelas contam histórias diferentes: a primeira é a altura, e ela é log n; a segunda é a largura, quantos passos horizontais você dá antes de cair um degrau, e ela é constante. Aumentar p faz a torre crescer (mais níveis para descer) e a caminhada encurtar (menos passos horizontais antes de cair um degrau). É esse cabo de guerra que a próxima experiência mede.

Agora faça a experiência que quase ninguém faz. Troque o p para 0,25 com n = 1.024 e compare os quatro cartões:

Com p = 0,25 a busca custa praticamente o mesmo e a estrutura ocupa um terço a menos de ponteiros. Não é acaso: o número médio de ponteiros por nó é 1 / (1 - p), ou seja, 2 com p = 0,5 e 1,33 com p = 0,25. O próprio Pugh sugere p = 1/4 no artigo original para a maioria dos casos. A moeda de p = 0,5 continua sendo a melhor escolha didática, porque cara ou coroa é fácil de explicar, mas em produção o 1/4 costuma ganhar.

E o pior caso? Ele existe e é O(n), exatamente a tela do preset "Azar total" lá em cima. A diferença fundamental é de onde vem o risco. Numa árvore de busca binária comum, o pior caso é uma entrada: chegue com os dados já ordenados e a árvore vira uma lista, sempre, de forma reproduzível. Numa skip list, o pior caso é azar, e não depende de quem manda os dados. Olhe o painel "E se der tudo errado?" e veja a conta com n = 1.024 e p = 0,5: a chance de os 1.024 nós tirarem coroa de primeira, todos, é de 1 em 10³⁰⁸. Para comparar, o universo observável tem cerca de 10⁸⁰ átomos. É por isso que se diz O(log n) esperado, e é por isso que dá para dormir tranquilo com essa garantia.

Em espaço, o custo médio é n / (1 - p) ponteiros, ou seja, Θ(n): linear, mas com uma constante que uma lista encadeada não paga. Com p = 0,5 são 2 ponteiros por nó em média, contra 1 da lista comum.

Juntando tudo, o quadro de complexidade da skip list fica assim:

O k da consulta por faixa é a quantidade de elementos devolvidos, e é ele que faz a skip list brilhar onde a tabela hash não entra. Nenhuma dessas linhas depende da ordem em que os dados chegaram, e essa é a diferença que interessa: uma BST comum degenera com entrada ordenada, uma skip list não tem entrada ruim, só tem dia ruim.

Skip List na vida real

O tema costuma entrar pela porta do system design, num capítulo sobre leaderboards, e não por acaso.

Pense num ranking de milhões de jogadores. Você precisa de quatro coisas ao mesmo tempo: manter tudo ordenado por pontuação, achar um jogador específico rápido, mover um jogador que acabou de pular da posição 4.756 para a terceira, e responder "quais são os 10 jogadores em volta de mim". Um array ordenado morre no terceiro requisito, porque mover um jogador desloca milhares de posições. Uma tabela hash morre no primeiro e no quarto, porque não guarda ordem. A skip list entrega os quatro, e o quarto quase de graça: depois de achar o jogador, os vizinhos são só andar para a frente no nível 0.

E "mover" um jogador, repare, não existe como operação: você remove e insere de novo com a pontuação nova. Como cada uma custa O(log n) e mexe em um punhado de ponteiros, o efeito prático é o de mover um elemento sem tocar em mais ninguém, que é exatamente o que o array ordenado não consegue fazer.

• Redis: os sorted sets são implementados como uma combinação de tabela hash e skip list. A hash guarda membro para pontuação em O(1), e a skip list mantém a ordem por pontuação e serve as consultas por faixa (ZRANGEBYSCORE). É a dupla exata dos requisitos de leaderboard acima.
• LevelDB e RocksDB: a MemTable, o buffer em memória onde as escritas caem antes de virar arquivo em disco, é uma skip list. Ela precisa aceitar escrita concorrente e ser lida em ordem, que é o cenário perfeito para a estrutura.
• Java: ConcurrentSkipListMap e ConcurrentSkipListSet são o mapa e o conjunto ordenados thread-safe da biblioteca padrão. Nada de árvore aqui, justamente porque rotação é global e ponteiro é local.
• Apache Lucene: usa skip lists dentro das posting lists para pular blocos de documentos durante a interseção de termos.

O ponteiro que falta: quantos eu pulei

Sobra um requisito que a estrutura deste artigo não resolve: "em que posição do ranking eu estou?". Buscar o jogador é O(log n), mas contar quantos vieram antes dele exigiria percorrer o nível 0, e isso é O(n).

A saída é uma extensão pequena e famosa, a indexable skip list: cada ponteiro forward passa a carregar também o span, o número de nós do nível 0 que aquele salto atravessa. Um ponteiro do nível 3 que pula por cima de 8 elementos guarda span = 8.

class No:
    def __init__(self, valor, altura):
        self.valor = valor
        self.forward = [None] * altura
        self.span = [0] * altura      # quantos nós do nível 0 cada salto cobre

Com isso, a mesma descida em escada da busca vira uma contagem: some o span de cada salto que você der e, ao chegar no alvo, a soma é a posição dele. Sem varrer nada, em O(log n). O caminho de volta também funciona: para achar o k-ésimo elemento, desça somando spans enquanto a soma não passar de k. É assim que o Redis implementa ZRANK e ZRANGE por índice, e é por isso que a zskiplistNode dele tem um campo span ao lado do forward.

O preço é honesto: toda inserção e toda remoção precisam corrigir os spans dos candidatos guardados no update, somando ou subtraindo 1 nos níveis por onde o nó passou. É mais contabilidade, não é mais complexidade, e continua sem nenhuma rotação. Se você for implementar uma skip list "de verdade", é aqui que o código cresce.

As armadilhas que pegam todo mundo

Não dá para adiar a reorganização. É tentador pensar em inserir tudo primeiro e "reindexar depois", como um índice de banco de dados faz. Não funciona: a busca depende de a lista estar ordenada em todo momento. A boa notícia é que você não precisa, porque não existe reindexação a fazer. Cada inserção já deixa a estrutura pronta.

Não tente rebalancear. Se em algum momento você pensar "esse nó ficou baixo demais, vou promovê-lo", pare. Isso reintroduz exatamente o custo que a moeda comprou. O ganho da skip list não é ela ser mais rápida que uma AVL, é ela ser muito mais simples com desempenho equivalente na média.

O sorteio precisa ser um sorteio de verdade. A garantia de O(log n) depende da qualidade da fonte de aleatoriedade. Com um gerador ruim, ou previsível, a distribuição das alturas deixa de ser geométrica e a estrutura degrada. Em serviço exposto ao público, um gerador previsível ainda abre a porta para alguém forçar o pior caso de propósito, o mesmo raciocínio do hash flooding em tabela hash.

Com dataset pequeno, não compensa. Uma skip list de 12 elementos gasta o dobro de ponteiros de uma lista comum para economizar quatro comparações. Ordenar ou varrer um punhado de itens é instantâneo com qualquer coisa. Esta estrutura faz sentido em escala, quando o log n de fato separa você do n.

O i do laço é o nível, não a posição. É a dúvida que mais toma tempo, e ela derruba quem lê o código rápido demais. for nivel in range(self.nivel_max, -1, -1) não percorre elementos, percorre andares, e o while de dentro é que anda para os lados. Quem lê atual.forward[nivel] como "o elemento na posição nivel" trava e não desatola.

Não pare no nível em que encontrou. É tentador testar a igualdade dentro do laço e sair correndo quando o valor bate num nível alto. Funciona, mas dobra o número de comparações no caminho todo para economizar num caso raro, e enche o código de saídas. O buscar deste artigo desce sempre até o nível 0 e testa a igualdade uma vez só, no fim. Simplicidade é o produto que a skip list vende.

Cuidado com os duplicados. O inserir deste artigo aceita repetidos: como o while anda só enquanto prox.valor < valor, um valor igual entra logo antes dos seus iguais, e a busca continua correta. Se você quiser recusar, é uma linha depois da descida:

    if update[0].forward[0] and update[0].forward[0].valor == valor:
        return False        # já existe, não insere

O visualizador de inserção faz exatamente isso, para o desenho não ficar com dois nós do mesmo valor colados. Em uso real a saída costuma ser outra, compor a chave: o Redis ordena por (score, membro), o que devolve a ordem total mesmo quando dois jogadores empatam na pontuação.

Os casos de borda que quebram a implementação na primeira submissão. Vale ter esta lista ao lado do editor:

A memória não é de graça. Θ(n) esconde uma constante: 2n ponteiros com p = 0,5, contra n de uma lista encadeada. Se o seu gargalo é memória e não latência, essa conta importa.

Como praticar

Antes de escrever qualquer código, use os visualizadores para prever o resultado e só depois conferir. Errar a previsão é o momento em que se aprende de verdade.

No visualizador da busca, tente adivinhar antes de rodar:

• "Antes de todos: procurar o 1". Em quantos níveis a busca vai avançar? Nenhum, ela só desce. E ainda assim gasta 5 comparações contra 2 da lista comum: o único caso em que a skip list perde.
• Procurar um valor maior que todos (digite 100). Onde a escada termina, e o que aparece no lugar do candidato? Placar: 4 contra 12.
• "Um elemento só: procurar o 42". Empate em 2. Com n = 1 não existe nada para pular.
• Clicar em "Sortear alturas" até cair uma estrutura de 2 níveis só, e comparar o contador com o da estrutura de 4 níveis. O veredito nunca muda, o custo sempre muda.

No visualizador da inserção, na aba Inserir, mude a altura no controle deslizante e responda antes de rodar: quantos ponteiros mudam de lugar para uma altura 1, para uma altura 3 e para uma altura 5? A resposta é sempre 2 × altura, e ver isso confirmado é o que fixa a ideia de que inserção é local. Depois vá para a aba Remover e responda a mesma pergunta: agora é 1 × altura, e o break decide onde parar.

No visualizador dos níveis, mexa no n e confira que os números batem com a conta na mão: para n = 4.096 e p = 0,5, o logaritmo de 4.096 na base 2 é 12, então a pirâmide deve ter 13 níveis. Depois sorteie as moedas e veja o quanto os níveis altos oscilam.

A implementação inteira, para copiar e quebrar

Quando a estrutura estiver clara, escreva a sua. A ordem que funciona é buscar, depois inserir, depois remover, testando cada uma antes de seguir. Repare que as três compartilham a mesma descida, então vale extraí-la para um método só: é o _caminho, que devolve o update e resolve o resto. E repare que o MAX_NIVEL subiu de 5 para 16: cinco níveis são ótimos para um desenho de doze nós, mas param de ajudar por volta de 32 elementos, porque a regra é log(n) na base 1/p.

import random

MAX_NIVEL = 16   # teto de altura. A regra do Pugh é log(n) na base 1/p,
                 # e log2(65.536) = 16: dá conta de dezenas de milhares de itens.
P = 0.5


class No:
    __slots__ = ("valor", "forward")

    def __init__(self, valor, altura):
        self.valor = valor
        self.forward = [None] * altura


class SkipList:
    def __init__(self):
        self.head = No(None, MAX_NIVEL)   # sentinela: sempre com o teto de ponteiros
        self.nivel_max = 0                # o nível mais alto ocupado hoje
        self.tamanho = 0

    def _sortear_altura(self):
        altura = 1
        while random.random() < P and altura < MAX_NIVEL:
            altura += 1
        return altura

    def _caminho(self, valor):
        """A descida que as três operações compartilham: devolve o rastro de
        candidatos, um por nível."""
        update = [self.head] * MAX_NIVEL
        atual = self.head
        for nivel in range(self.nivel_max, -1, -1):
            prox = atual.forward[nivel]
            while prox and prox.valor < valor:
                atual = prox
                prox = atual.forward[nivel]
            update[nivel] = atual
        return update

    def buscar(self, valor):
        alvo = self._caminho(valor)[0].forward[0]
        return alvo is not None and alvo.valor == valor

    def inserir(self, valor):
        update = self._caminho(valor)
        seguinte = update[0].forward[0]
        if seguinte is not None and seguinte.valor == valor:
            return False                       # sem duplicados
        altura = self._sortear_altura()
        self.nivel_max = max(self.nivel_max, altura - 1)
        novo = No(valor, altura)
        for nivel in range(altura):
            novo.forward[nivel] = update[nivel].forward[nivel]
            update[nivel].forward[nivel] = novo
        self.tamanho += 1
        return True

    def remover(self, valor):
        update = self._caminho(valor)
        alvo = update[0].forward[0]
        if alvo is None or alvo.valor != valor:
            return False
        for nivel in range(self.nivel_max + 1):
            if update[nivel].forward[nivel] is not alvo:
                break
            update[nivel].forward[nivel] = alvo.forward[nivel]
        while self.nivel_max > 0 and self.head.forward[self.nivel_max] is None:
            self.nivel_max -= 1
        self.tamanho -= 1
        return True

    def faixa(self, a, b):
        """Todos os valores em [a, b], em ordem: O(log n + k)."""
        no = self._caminho(a)[0].forward[0]
        while no is not None and no.valor <= b:
            yield no.valor
            no = no.forward[0]

    def __iter__(self):
        no = self.head.forward[0]
        while no is not None:
            yield no.valor
            no = no.forward[0]

Agora quebre. O teste que mais acha bug numa estrutura probabilística não é o de mesa, é o aleatório com espelho: rode milhares de operações sorteadas contra um set do Python e compare a lista inteira a cada passo. Se a sua skip list sobrevive a isto, ela está certa.

import random

random.seed(7)
ref, sl = set(), SkipList()
for _ in range(5000):
    v, dado = random.randrange(200), random.random()
    if dado < 0.45:
        assert sl.inserir(v) == (v not in ref); ref.add(v)
    elif dado < 0.90:
        assert sl.remover(v) == (v in ref);     ref.discard(v)
    else:
        assert sl.buscar(v) == (v in ref)
    assert list(sl) == sorted(ref)      # a invariante que importa: o nível 0 é a verdade
    assert sl.tamanho == len(ref)

vazia = SkipList()                      # e os casos de borda, na mão
assert vazia.buscar(1) is False and vazia.remover(1) is False and list(vazia) == []
assert vazia.inserir(1) and list(vazia) == [1] and vazia.remover(1) and list(vazia) == []
assert vazia.nivel_max == 0             # o topo encolheu de volta

Note o assert list(sl) == sorted(ref) dentro do laço: ele testa o nível 0, que é onde mora a verdade. Se algum ponteiro de nível alto ficar errado, o defeito vaza para a ordem do nível 0 em poucas operações, e o assert pega. Testar só buscar esconde bug de religação por muito tempo.

Os problemas, do mais direto ao mais difícil

1. 707. Design Linked List. Aquecimento: religar ponteiros sem níveis. Se o add/delete daqui já dói, a skip list vai doer o dobro.
2. 981. Time Based Key-Value Store. Coleção ordenada por tempo com consulta "o maior que não passa de t", que é exatamente a pergunta que o update[0] responde. A solução aceita usa busca binária num array, e comparar as duas é o ponto.
3. 1206. Design Skiplist. A implementação inteira, search, add e erase, em uma sentada. Atenção: aqui os duplicados são permitidos, então tire o return False do inserir e lembre que erase remove uma ocorrência só.
4. 220. Contains Duplicate III. Precisa de um conjunto ordenado com consulta por faixa dentro de uma janela deslizante: basta perguntar se faixa(v - t, v + t) devolve alguma coisa antes de inserir o v. Dá para resolver com baldes também, e vale escrever as duas para comparar.
5. 295. Find Median from Data Stream. A solução canônica são dois heaps, e é ela que você deve escrever. O exercício aqui é justificar por que o heap ganha: a mediana é uma consulta por índice fixo, e para isso você precisaria dos spans da seção anterior.

Um lembrete honesto para entrevista: quase nunca a resposta certa é "implemento uma skip list". A resposta certa é reconhecer que o problema pede uma coleção ordenada dinâmica e dizer qual estrutura pronta entrega isso na sua linguagem, com skip list ou árvore por baixo. Saber implementar serve para você entender o que está escolhendo.

Para fechar o quadro, vale ver as duas estruturas que a skip list está substituindo em cada ponta: a Busca Binária, de onde vem a intuição do descarte em bloco, e a Árvore de Busca Binária, que resolve o mesmo problema com garantia no pior caso e um código muito maior. E, se a parte dos ponteiros ainda estiver escorregadia, o caminho de volta é a Lista Encadeada: o nível 0 de uma skip list não é nada além dela.

Vídeo da aula

Direto do canal da comunidade Craft & Code Club · 1:58:55.

▶

Problemas para praticar

Na ordem em que recomendamos resolver. Marque os que você já fez, fica salvo aqui.

Referências

Artigos e materiais externos para se aprofundar.