Skiplist

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.

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)[1]
Busca O(log n) O(n)[1]
Inserção O(log n) O(n)
Remoção O(log n) O(n)

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(log1/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
  1. Papadakis, Thomas (1993). Skip Lists and Probabilistic Analysis of Algorithms (PDF) (Ph.D.). University of Waterloo
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.