Árvores Equilibradas
Sumário
 Splay
 Vermelho-Preto
 AA e BB
 Multidimensionais
 quaternárias
 k-d
 Pesquisa Lexicográfica
 tries multivia
 tries binárias
 PATRICIA
TRIE
Trie

Árvore multivia (origem do nome “info retrieval”)

Em vez de comparar chaves completas
 aplicar a ideia de consulta de tabela à pesquisa de informaçõo numa árvore
 utilizar cada letra de uma chave para fazer escolhas múltiplas sucessivas
 típico: usar só as primeiras letras porque depois a árvore expande muito (26 vias
em cada passo)
 podem omitir-se os caminhos que não vão dar a uma chave
 pode combinar-se com outro método (para o resto da chave)
 número de passos na pesquisa proporcional ao número de caracteres na chave
chave de 5 letras
localiza 26^5 = 11 881 376 posições
trie : 5 iterações
pesquisa binária: log n = 23.5 comparações de chaves
TRIE
Trie lexicográfica
...
a
b
c
...
ab
ac
TRIE
Trie binária
A
S
E
R
C
H
I
N
G
X
M
P
L
00001
10011
00101
10010
00011
01000
01001
01110
00111
11000
01101
10000
01100
b=5
A
0
1
E
S
1
0
0
C
H
1
0
G
0
R
1
0
I
1
0
N
1
0
1
0
X
1
0
1
P
1
0
1
M
0
Árvores resultam equilibradas
Pesquisa: 1 comparação de chave por nó
L
0
1
1
Caso médio: log N comparações
Pior caso: b comparações
TRIE
Trie binária com chaves em nós externos
A
S
E
R
C
H
I
N
G
X
M
P
L
00001
10011
00101
10010
00011
01000
01001
01110
00111
11000
01101
10000
01100
b=5
E
A
C
R
S
Árvore não depende da ordem de inserção
Pesquisa: 1 só comparação de chave
Caso médio: log N comparações de bits
Pior caso: b comparações de bits
TRIE
Eficiência na pesquisa em Trie

Trie fornece equilíbrio quase automático da árvore
 em chaves aleatórias, as probabilidades para 0 e 1 nos bits são iguais
 nenhum caminho na árvore tem comprimento superior ao número de bits da chave

Eficiência
 condicionada pela facilidade em realizar operações ao bit (extracção e comparação)

Altura da trie
 limitada pelo número de bits nas chaves

Chaves podem ser muito longas quando se faz pesquisa em documentos
 Solução 1: usar árvore multivia, considerando os bits em grupos
 melhorar pesquisa com factor 2m, mas espaço de links não usados aumenta
 pode usar-se híbrido: multivia no topo da árvore e método elementar no fundo
 Solução 2 (PATRICIA): encurtar caminhos que ramificam só para um lado
 de “Practical Algorithm To Retrieve Information Coded In Alphanumeric” D.R. Morrison
TRIE
PATRICIA

Para resolver caminhos que ramificam só para um lado
 em cada nó: índice do bit a testar para decidir caminho a partir do nó
 nós externos: substituídos por ligações para o nó interno onde se encontra a chave
 só há um tipo de nós
 apontadores “para cima” fáceis de identificar: são para nós com índice superior
 pesquisa e inserção
 descida na árvore não usa as chaves do nó, apenas o seu índice
 quando se atinge um nó externo o apontador “para cima” dá o nó para recuperar a chave
 Chave a pesquisar existe: se é a chave do nó referido pelo primeiro apontador “para cima”
TRIE
PATRICIA
A
S
E
R
C
H
I
N
G
X
M
P
L
4
00001
10011
00101
10010
00011
01000
01001
01110
00111
11000
01101
10000
01100
S
1
3
H
X
2
2
1
E
N
P
1
C
3
G
0
1
I
M
0
R
0
0
A
L
Chave R corresponde a padrão 10*10
1 comparação de chave completa por pesquisa
TRIE
PATRICIA - Inserção externa
4
S
1
3
H
X
2
2
1
1
E
N
P
Z
1
C
3
G
0
1
I
M
0
R
0
0
A
L
X = 11000
Z = 11010
TRIE
PATRICIA - Inserção interna
4
S
1
3
H
X
2
2
2
1
E
N
T
Z
1
C
3
G
0
I
0
0
A
L
1
1
M
P
0
R
P = 10000
T = 10100
TRIE