Saltar para o conteúdo

Skiplist

Origem: Wikipédia, a enciclopédia livre.
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)

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.

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

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

[editar | editar código-fonte]

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.

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.
  • Pugh, William (June 1990). "Skip lists: a probabilistic alternative to balanced trees". Communications of the ACM 33: 668-676.

Ligações externas

[editar | editar código-fonte]
  1. a b Papadakis, Thomas (1993). Skip Lists and Probabilistic Analysis of Algorithms (PDF) (Ph.D.). University of Waterloo