15_Skip List

Prévia do material em texto

1
Skip List
1
Prof. Cláudio Campelo, PhD
Departamento de Sistemas & Computação / UFCG
Estrutura de Dados e 
Algoritmos
Skip List
2
� Surgiram como uma idéia probabilística para árvores
balanceadas
� Tempo esperado das operações com alta 
probabilidade O(log(n))
� Fácil de implementar e de entender
2
Communications of the ACM, June 1990, 33(6) 668-676. 
3
Questionamentos Pertinentes
4
� Quanto tempo leva no pior caso para pesquisar em 
uma lista ordenada?
� O(n). 
3
Questionamentos Pertinentes
5
� Quanto tempo leva no pior caso para pesquisar em 
uma lista ordenada?
� O(n). 
� Como podemos melhorar a pesquisa em listas 
encadeadas?
Exemplo
6
� Linhas de ônibus podem implementar uma skip list
� Linha local (para em todos os pontos) 
� Linha expressa (poucas paradas)
1 2 3 4 5 6
4
Exemplo
7
� Como fazer para ir da estação 1 para a 5?
� Linha azul na estação 1 e desce na 4
� Depois pegar a linha vermelha e descer na 5
1 2 3 4 5 6
Skip List (Definição)
8
� Skip list é uma estrutura de dados probabilística, 
baseada em listas encadeadas, com eficiência 
comparada a das árvores binárias de pesquisa;
� Basicamente, uma skip list é uma variação de uma 
lista encadeada ordenada onde a cada nó são 
acrescentados vários ponteiros para elementos a 
frente, de modo que a pesquisa possa rapidamente 
“pular” partes da lista (daí o nome);
� Uma skip list tem a propriedade de manter seus 
itens ordenados;
5
Skip List
9
� Balancear probabilisticamente uma estrutura de 
dados é mais fácil que manter o balanceamento de 
forma explicita. 
� Para algumas aplicações, skip lists são mais 
naturais que árvore e levam a algoritmos mais 
simples e fáceis de implementar. 
� Performance melhorada por um fator constante em
relação a algoritmos de balanceamento
� Skip lists são eficientes em uso de espaço.
Skip Lists (Definições)
10
níveis
nós
forward links
nó cabeçalho nó vazio
- ∞ ∞
6
Exemplos
11
Nós sentinelas
Skip List (Definições)
12
� Nível (altura) máximo(a)
� Maior altura que um nó pode ter em uma skip list 
� Nível (altura)
� A altura da skip list é a altura do maior nó, ou seja, a 
quantidade de referências do nó com maior número de 
apontadores forward.
� Probabilidade
� Probabilidade é o valor usado no algoritmo para 
determinar aleatoriamente o nível (altura) de cada nó
hhmax
7
Exemplo
13
� Um nível possui determinado número de nós que é 
menor ou igual ao número de nós da camada 
adjacente inferior
� Todos os níveis possuem nós ordenados.
altura
nível
No de 
nivel 4
No de 
nivel 3
No de 
nivel 2
Nó de 
nivel 1
Características
14
� S0 possui todos os elementos além do -∞ e ∞
� Todos os Si possuem -∞ e ∞
� onde cada Si ⊆ S0
S0
Sh
8
Exemplo
15
� Inicialização de uma skip list com nível máximo 7 e 
probabilidade de 0,5.
� O HDR (header) guarda o início da lista (menor
valor possível). 
� O elemento NIL guarda a maior chave possível da
skip list. Ele fica no final da lista.
� Todos os níveis terminam com NIL.
-∞ ∞
-∞ ∞OU
Exemplo
16
� Inserção dos nós 9,7,5,3,6,14,8,12 com respectivas 
alturas (níveis) sendo 2,1,1,2,2,1,1,5 determinados 
aleatoriamente.
� Os nós são colocados em ordem crescente
Usando nível máximo como altura da skip list.
9
Exemplo
17
� Inserção dos nós 9,7,5,3,6,14,8,12 com respectivas 
alturas (níveis) sendo 2,1,1,2,2,1,1,5 determinados 
aleatoriamente.
� Os nós são colocados em ordem crescente
Sem usar nível máximo como altura da skip list.
Skip List
18
� Altura de uma skip list
� Não depende da distribuição das chaves
� Espera-se que cada nível tenha 50% do anterior
� Logo a altura esperada é h = log n
� A randomização é quem vai dizer isso
10
Implementação
19
� Que estruturas compõem uma skip list?
� Como implementá-las?
Implementação
20
� Como implementar as classes SkipNode e SkipList?
11
Implementação
21
� Como implementar as classes SkipNode e SkipList?
public class SkipNode<V> { 
SkipNode<V>[] forward;
int height;
int key;
V satteliteData;
public SkipNode(int key, int height, 
V satelliteData){
this.key = key;
this.height = height;
this.satteliteData = satelliteData;
this.forward = new SkipNode[height];
}
}
Implementação (Interface)
22
public interface SkipList<V> {
public void insert(int key, V newValue);
public void insert(int key, V newValue, int height);
public void remove(int key);
public int height();
public SkipNode<V> search(int key);
public int size();
public SkipNode<V>[] toArray();
}
12
Implementação
23
public class SkipListImpl<V> implements SkipList<V> {
SkipNode<V> root;
SkipNode<V> NIL;
int level; 
int maxLevel;
boolean useMaxLevelAsLevel;
double probability;
}
Exercício
24
� Como representar o nó NIL?
public class SkipNode<V> { 
SkipNode<V>[] forward;
int height;
int key;
V value;
}
public class SkipListImpl<V> implements SkipList<V> {
…
int infinito = Integer.MAX_VALUE;
NIL = new 
SkipNode<V>(infinito,maxLevel,null);
∞
13
Exercício
25
� Como criar uma skip list vazia?
public class SkipListImpl<V> {
...
boolean useMaxLevelAsLevel;
double probability = 0.5;
public SkipList (int maxLevel, boolean maxLevelAsLevel){
if(maxLevelAsLevel){
this.level = maxLevel;
} else{
this.level = 1;
}
this.maxLevel = maxLevel;
root = new SkipNode<V>(menosInfinito,maxLevel,null);
NIL = new SkipNode<V>(infinito,maxLevel,null);
connectRootAndNIL();
}
}
public class SkipListImpl<V> {
...
boolean useMaxLevelAsLevel;
double probability = 0.5;
public SkipList (int maxLevel, boolean maxLevelAsLevel){
if(maxLevelAsLevel){
this.level = maxLevel;
} else{
this.level = 1;
}
this.maxLevel = maxLevel;
root = new SkipNode<V>(menosInfinito,maxLevel,menosInfinito);
NIL = new SkipNode<V>(infinito,maxLevel,infinito);
connectRootAndNIL();
}
}
Exercício
26
� Como criar uma skip list vazia?
void connectRootAndNIL(){
for i:0 ���� level
root.forward[i] = NIL;
}
14
Skip List (Pesquisa)
27
� Como pesquisar em uma skip list?
� Como pesquisar o nó 8?
Skip List (Pesquisa)
28
� Como pesquisar em uma skip list?
� Como pesquisar o nó 8?
� Comece atravessando os apontadores forward que não levam
a um elemento menor que o procurado.
� Depois siga para o elemento menor e aplique o mesmo
raciocínio até descer ao nível 1.
� Depois é só seguir o apontador forward do nivel 1 do último nó
visitado.
15
Skip List (Pesquisa)
29
� Como pesquisar em uma skip list?
� Como pesquisar o nó 8?
Skip List (Pesquisa)
30
� Como pesquisar em uma skip list?
� Pesquise as chaves 9,15,13,17.
16
Skip List (Pesquisa)
31
� Como pesquisar em uma skip list?
� Pesquise as chaves 9,15,13,17.
Skip List (Pesquisa)
32
� Como pesquisar em uma skip list?
� Pesquise as chaves 9,15,13,17.
17
Skip List (Pesquisa)
33
� Como pesquisar em uma skip list?
� Pesquise as chaves 9,15,13,17.
Skip List (Pesquisa)
34
� Como pesquisar em uma skip list?
� Pesquise as chaves 9,15,13,17.
18
Skip List (Pesquisa)
35
� Como pesquisar em uma skip list?
� Pesquise as chaves 9,15,13,17.
Skip List (Pesquisa)
36
� Como pesquisar em uma skip list?
� Pesquise as chaves 9,15,13,17.
x
19
Skip List (Pesquisa)
37
� Como seria o algoritmo da pesquisa?
Skip List (Pesquisa)
38
� Como seria o algoritmo da pesquisa?
pesquisa(list,key)
x := list.root
for i := list.level downto 1 do
while x.forward[i].key < key do
x := x.forward[i]
x := x.forward[1]
if x.key = key then 
return x.value
else return “A chave não existe”
Para andar atéo último nó com
mesma altura
20
Skip List (Inserção)
39
� Como funciona a inserção em uma skip list?
� Como inserir o nó 10?
� O nível do nó vai ser gerado aleatoriamente
� Precisa de uma função randômica
� Vamor supor que foi nivel randômico gerado foi 1
Skip List (Inserção)
40
� Como funciona a inserção em uma skip list?
� Como inserir o nó 10?
� O nível do nó vai ser gerado aleatoriamente
� Precisa de uma função randômica
� Vamor supor que foi nivel randômico gerado foi 1
21
Skip List (Inserção)
41
� Como funciona a inserção em uma skip list?
� Como inserir o nó 10?
� O nível do nó vai ser gerado aleatoriamente
� Precisa de uma função randômica
� Supor p = 0,5; 
� random <= p (incrementa); random > p (não incrementa)
Skip List (Inserção)
42
� Como funciona a inserção em uma skip list?
� Como inserir o nó 4 e 15?
� 4: Supor que random gera 0,0,1,0,0,0,1 (nessa ordem)
� 15: Supor que random gera 0,0,0,1,0,0,1 (nessa ordem)
� Qual o nível do nó 4?
� Qual o nível do nó 15?
22
Skip List (Inserção)
43
� Como funciona a inserção em uma skip list?
� Como inserir o nó 4 e 15?
� 4: Supor que random gera 0,0,1,0,0,0,1 (nessa ordem)
� 15: Supor que random gera 0,0,0,1,0,0,1 (nessa ordem)
� Qual o nível do nó 4? (3)
� Qual o nível do nó 15? (4)
Ilustração geral
44
23
Skip List (Inserção)
45
� Como seria
o algoritmo da 
inserção?
Skip List (Inserção)
46
Inserir(SkipList list, key, newValue)
SkipNode [] update = new SkipNode [1..list.maxLevel];
x := list.root
for i := list.level downto 1 do
while x.forward[i].key < key do
x := x.forward[i]
update[i] := x
x := x.forward[1]
if x.key = key 
x.value := newValue
else 
int v := randomLevel()
if v > list.level then
for i := list.level + 1 to v do
update[i] := list.root
list.level := v
x := makeNode(key, v, newValue)
for i := 1 to v do
x.forward[i] := update[i].forward[i]
update[i].forward[i] := x
Altera
Ponteiros
Pesquisa 
o local
Guarda 
Caminho
Caso o nível 
aumente
Este algoritmo 
insere ou atualiza 
os dados
� Como seria
o algoritmo da 
inserção?
24
Ilustração geral
47
x
for i: 1..v
x.forward[i] = update[i].forward[i]
update[i].forward[i] = x
updade[1]
updade[4]
updade[3]
updade[2]
x
for i := list.level downto 1 do
while x.forward[i].key < key do
x := x.forward[i]
update[i] := x
Skip List (Remoção)
48
� Como funciona a remoção em uma skip list?
� Como remover o nó 9?
� É só procurar pelo nó e guardar os nós a terem os
apontadores forward a serem atualizados para os
apontadores forward do nó removido.
25
Skip List (Remoção)
49
� Como funciona a remoção em uma skip list?
� Como remover o nó 9?
� É só procurar pelo nó e guardar os nós a terem os
apontadores forward a serem atualizados para os
apontadores forward do nó removido.
Skip List (Remoção)
50
� Como seria 
o 
algoritmo da 
remoção?
Delete(SkipList list, key)
Node [] update = new Node[1..list.maxLevel];
x := list.root
for i := list.level downto 1 do
while x.forward[i].key < key do
x := x.forward[i]
update[i] := x
x := x.forward[1]
if x.key = key then
for i := 1 to list.level do
if update[i].forward[i] ≠ x then break
update[i].forward[i] := x.forward[i]
while list.level > 1 and
list.root.forward[list.level] = NIL do
list.level := list.level – 1
Ajeita
Altura
Ajeita
Ponteiros
Pesquisa 
o local
Guarda 
Caminho
26
Skip List (Remoção)
51
updade[2]
updade[4]
updade[3] updade[1]
x
for i := 1 to list.level do
if update[i].forward[i] ≠ x then break
update[i].forward[i] := x.forward[i]
while list.level > 1 and list.root.forward[list.level] = NIL do
list.level := list.level – 1
Skip List
52
� Applet
� http://people.ksp.sk/%7Ekuko/bak/index.html
� http://www.sccnet.com.br/jackson/SkipList/SkipListApplet/
Applet.html
27
Skip List (Análises)
53
� O tempo de pesquisa de uma skip list é proporcional 
a: 
� Pesquisa na Diagonal
� O número de passos para baixo nos níveis (vezes)
� O número de pesquisas para frente
� Por fatores probabilísticos tem grande chance de 
serem O(log n)
� As análises dos métodos inserir e remover são similares
� Em média, skip lists são mais rápidas do que 
árvores AVL e outras árvores balanceadas de 
pesquisa
Skip List (Análises)
54
� Complexidade de espaço
� Usando-se fatores probabilísticos, calcula-se que o 
espaço provavelmente usado por uma skip list com n 
itens é de O(n)
28
Referências
55
� Seção 7.5
� 1a edição
� http://www.sable.mcgill.ca/~dbelan2/cs251/skip_lists.
html