Skiplist

Origem: Wikipédia, a enciclopédia livre.

SkipList é uma estrutura de dados probabilística, baseada em listas 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 aglomerido de listas encadeadas com ligações adicionais, adicionadas de modo randômico 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 1990 por William Pugh, a Skiplist é uma das mais recentes dentre aquelas estruturas de dados mais importantes da Ciência da computação.

Índice

1 Descrição
2 Operações
- 2.1 Busca
- 2.2 Inserções e Remoções
3 História
4 Referências
5 Links Externos

[editar] 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

[editar] Operações

[editar] 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.

[editar] 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.

[editar] História

Skiplists foram descobertas por William Pugh. Ele descreve as mesmas 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.