SkipList é uma estrutura descrita em 1989 por William Pugh que se baseia em balancear de forma probabilística atalhos de um item a outro com objetivo de alcançar complexidade O(log(n)), sendo assim um substituto para árvores AVL. O objetivo deste projeto é de implementar uma Skip List em Rust, e dada a complexidade de desenvolvimento devido o gerenciamento de memória, foi decidido a implementação de estruturas intermediárias.
Artigo: Skip Lists: A Probabilistic Alternative to Balanced Trees
Esse estudo teve o intuito de unir o aprofundamento de Rust e de estruturas de dados. O desenvolvimento foi separado em 3 níveis:
- Stack: Entender o processo de substituição de um item por outro na cabeça da pilha (link)
- Linked List: Inserir um item entre outros dois itens de uma lista simplesmente ligada (link)
- SkipList: Em inserir um item entre dois itens respeitando as referências de atalhos (link)
Iniciando em uma lista simples ordenada a complexidade temporal média de busca é O(n)
Vamos então incluir acima uma lista com atalhos a cada dois itens.
A complexidade temporal pode ser calculada por:
E para temos que
Incluindo mais um nível a complexidade se torna
Para k níveis temos uma complexidade . O que aconteceria se tivessemos log(n) níveis? O resultado final, incrivelmente, é O(log(n))
Manter uma estrutura onde o nível acima é sempre a metade do nível anterior é muito custoso. Como solução temos a randomização dos níveis. Quando um novo nó é inserido na skiplist seu nível é randomizado, tendo uma probabilidade P de obter uma promoção de nível e probabilidade P^k de obter o nível máximo.
Em estruturas de dados onde o objeto de dado guardado precisar ser alocado independentemente do objeto original foi escolhido a alocaçao em Heap via Box. Dessa forma é possível referenciar e derreferenciar sem muita verbosidade de código (nem lifetimes)
O objeto do topo é obtido via std::mem::take, no lugar é deixado valores default do tipo.
Chamada função que verifica se a estrutura está vazia e em seguida o primeiro item é dado como cursor para uma função recursiva.
- SkipList