O que é uma skip list e como ela obtém busca O(log n)?

Question

Accepted Answer

Uma **skip list** é uma lista encadeada ordenada aumentada com vários níveis **"express lane"**. Níveis superiores pulam muitos nós, então a busca desce e se move para a direita, alcançando **O(log n)** tempo esperado — como uma alternativa probabilística e mais simples para uma árvore balanceada. ## Estrutura ```text L3: head ------------------------> 30 -------> NIL L2: head ----------> 17 ---------> 30 -------> NIL L1: head ----> 9 --> 17 --> 25 --> 30 --> 42 -> NIL L0: head -> 3->9->12->17->25->30->39->42 ----> NIL (full list) ``` Cada nó é promovido a níveis superiores com probabilidade `p` (geralmente 0.5), então em média cada nível tem metade dos nós do que está abaixo. ## Busca ```text search(25): start top-left, move RIGHT while next <= target, else drop DOWN a level. Repeat to level 0. ``` ```python import random def random_level(p=0.5, max_level=16): lvl = 1 while random.random() < p and lvl < max_level: lvl += 1 # coin flips decide a node's height return lvl ``` ## Complexidade | Operação | Esperado | Espaço | |---|---|---| | busca | O(log n) | O(n) | | inserção / exclusão | O(log n) | — | ## Por que isso importa - **Pontos fortes:** muito mais simples de implementar do que red-black/AVL; sem rotações; versões concorrentes fáceis (usadas em Redis sorted sets, Java `ConcurrentSkipListMap`). - **Pontos fracos:** garantias probabilísticas (não pior caso); ponteiros extras por nó. ## Compensações vs árvores balanceadas Skip lists fornecem operações ordenadas O(log n) semelhantes a árvores com muito menos código e concorrência lock-free fácil, razão pela qual sistemas como Redis as escolhem. Elas são um ótimo exemplo de uso de **randomization** para substituir lógica de balanceamento determinística complexa.