Listas de saltos usavam cara ou coroa em vez de rotações para se manterem balanceadas

Estruturas ordenadas construídas como árvores balanceadas precisam se reequilibrar após cada atualização, o que implica rotações, recoloração e invariantes cuidadosos — tudo isso fácil de errar e difícil de paralelizar.

As listas de saltos trocam essa maquinaria por uma regra probabilística. Cada nó recebe um nível sorteado de uma distribuição que cai abruptamente, de modo que a maioria fica nos níveis baixos, uma minoria nos altos, e uma busca pode saltar por longos trechos de níveis inferiores antes de descer.

Como os níveis são aleatórios, o número esperado de nós por nível é geométrico, e busca, inserção e remoção ficam todas, em expectativa, em O(log n). O código é curto, e nenhuma contabilidade precisa ser feita depois do fato.

Deixar que cara ou coroa, e não rotações, mantenham o balanceamento

Níveis aleatórios fornecem o limite de altura sem código de rebalanceamento.

Operações locais e favoráveis a bloqueios tornam fácil paralelizar.

A simplicidade significa menos invariantes para manter e errar.

Quando o rebalanceamento determinístico é a parte cara e propensa a erros, substitua-o por aleatoriedade honesta: operações locais e simples dão o mesmo desempenho esperado que um invariante mantido manualmente.

As listas de saltos tornaram-se uma alternativa padrão às árvores em bibliotecas e bancos de dados, mais famosamente nos conjuntos ordenados do Redis, onde a simplicidade auxilia a concorrência e o desempenho previsível.