Skiplist

Skiplist
Tipo	Lista
Ano	1989
Inventado por	W. Pugh
Complexidade de Tempo em Notação big O
Algoritimo Caso Médio Pior Caso Espaço O(n) O(n log n) Busca O(log n) O(n) Inserção O(log n) O(n) Remoção O(log n) O(n)

SkipList é uma estrutura de dados probabilística, baseada em listas ligadas paralelas, com eficiência comparável à de uma árvore binária (ordem de O(log n)) para a maioria das operações. Basicamente, uma skip list é um aglomerado de listas encadeadas com ligações adicionais, adicionadas de modo aleatório de acordo com a distribuição Geométrica/Negativa Binomial, os quais permitem evitar a busca em parte da lista, 'pulando' alguns valores. Inserção, busca e remoção são operadas em tempo logarítmico.

Descoberta em 1989 por William Pugh, a Skiplist é uma das mais recentes dentre aquelas estruturas de dados mais importantes da Ciência da computação.

Descrição

Uma skiplist é constituída por camadas. A camada mais inferior é uma lista encadeada. Cada camada mais alta atua como uma "via de acesso" para as listas abaixo, onde um elemento na camada i aparece na camada i+1 com probabilidade fixa p. De modo geral, cada elemento aparece em 1/(1-p) listas, onde o elemento mais alto (normalmente um elemento especial usado como cabeçalho para o começo da skiplist) aparece em O(log1/p n) listas.

1
1-----4---6
1---3-4---6-----9
1-2-3-4-5-6-7-8-9-10

Operações

Busca

Para buscar uma dada chave, deve-se começar pelo topo do cabeçalho da lista e seguir ao longo de cada lista encadeada até encontrar o elemento o qual é menor ou igual a chave. O número esperado de passos em cada lista encadeada é facilmente visto ser 1/p, bastando seguir o trajeto de busca por caminhos desde alcançar a chave até o próximo elemento maior que a mesma na lista. O custo total da busca é O(log_1/p n / p), que resulta em O(log n) quando p é uma constante. A escolha de diferentes valores para p, equilibra custo de busca com o custo de armazenamento.

Inserções e Remoções

Estas duas operações são implementadas de forma similar às operações equivalentes em listas encadeadas, excepto pelo fato de que os elementos com altura devem ser inseridos e deletados em mais de uma lista encadeada.

História

Skiplists foram descobertas por William Pugh, que as descreve em seu trabalho: Skip lists: uma alternativa probabilística à árvores balanceadas, datado de Junho de 1990

Abaixo uma citação de Pugh sobre a respectiva estrutura de dados:

Skip lists são uma estrutura de dados probabilísticas que pretendem superar as árvores balanceadas como escolha de estrutura para implementação em muitas aplicações. Os algoritmos são assintoticamente parecidos com o tipo de árvores já mencionados e são mais simples, mais rápidas e ocupam menos espaço.

Referências

• Pugh, William (June 1990). "Skip lists: a probabilistic alternative to balanced trees". Communications of the ACM 33: 668-676.

Ligações externas

• Descrição de Skip list do Dicionário de Algoritmos e Estruturas de Dados
• Implementação em C#
• Tutorial sobre Skip Lists
• Artigo Original de William Pugh
• John-Mark Gurney
• Applet Java de Skip List by Jackson Porciúncula^{[ligação inativa]} (muito bom)