AEDII-aula12

Prévia do material em texto

1
Aula 12 – 
Árvores Rubro-Negras (parte 2)
Árvores Digitais/Trie
MC3305
Algoritmos e Estruturas de Dados II
Prof. Jesús P. Mena-Chalco
jesus.mena@ufabc.edu.br
2Q-2014
2
Árvores de Busca Binária
Por que ABB?
São estruturas eficientes de busca 
(se a árvore estiver balanceada).
Permitem minimizar o tempo de acesso no pior caso.
Complexidade das operações de busca, inserção, 
remoção:
Se balanceada → O(lg (n))
Senão → O(n)
3
Árvores balanceadas
As seguintes árvores são as ditas balanceadas – com altura 
O(lg(n)):
AVL
Rubro-negras / vermelho-preto / red-black tree
B
As árvores Rubro-negras
apresentam uma altura
de, no máximo, igual a
2 lg(n+1).
4
Árvore Rubro-Negra
Rudolf Bayer
Computer scientist
5
Propriedades de Árvore Rubro-Negra
As propriedades da árvore rubro-
negra são:
1- Todo nó da árvore ou é 
vermelho ou é preto
2- A raiz e as folhas (nil) são 
pretas
3- Se um nó é vermelho, então 
seus filhos são pretos
4- Para todo nó, todos os 
caminhos do nó até as folhas 
descendentes contêm o mesmo 
número de nós pretos.
6
Inserção
Inserções e remoções feitas em uma ARN podem modificar 
a sua estrutura.
Precisamos garantir que nenhuma das propriedades de 
seja violada.
Para isso podemos ter que mudar a estrutura da árvore e 
as cores de alguns dos nós da árvore
A mudança da estrutura da árvore é feita por dois tipos de 
rotações em ramos da árvore:
rotação à esquerda
rotação à direita
7
Inserção
Veja o arquivo no tidia:
AEDII-aula11-material.pdf
8
Algoritmo de inserção
struct no 
{
 int chave; // pode ser char, string, etc...
 int cor; // bastaria um bit
 no * pai;
 no * esq;
 no * dir;
}
9
Algoritmo de inserção
O algoritmo RB_fixup(T,z) re-estrutura a árvore.
Caso necessário através:
das mudanças de cores de alguns nós, e 
das operações de rotação
RB_insere(T, z): 
 … // insere z na árvore como se fosse uma ABB normal
 esq[z] <- nil[T]
 dir[z] <- nil[T]
 cor[z] <- vermelho
 RB_fixup(T, z)
10
Algoritmo de inserção
RB_fixup(T, z):
1: while cor[pai[z]] = vermelho do
2: if pai[z] = esq[pai[pai[z]]] then //pai de z é filho esquerdo?
3: y <- dir[pai[pai[z]]] // y aponta para o tio de z
4: if cor[y] = vermelho then // caso 2: tio vermelho?
5: cor[pai[y]] <- preto
6: cor[y] <- preto // tio vermelho vira preto
7: cor[pai[pai[z]]] <- vermelho // avô vira vermelho
8: z <- pai[pai[z]] // continuando o processo a partir do avô
9: else
10: if z = dir[pai[z]] then // caso 3: z é filho direito?
11: z <- pai[z]
12: rot-esq(T, z) // rotaciona à esquerda no pai de z
13: cor[pai[z]] <- preto // caso 3: z é filho esquerdo
14: cor[pai[pai[z]]] <- vermelho // avô vira vermelho
15: rot-dir(T, pai[pai[z]]) // rotaciona à direita no avô de z
16: else
17: {o mesmo do caso then (linhas 3 a 15) trocando dir por esq}
18:cor[raiz[T]] <- preto // no final a raiz sempre se torna preta
11
Complexidade do algoritmo de inserção
A altura de uma ARN de n chave é O( lg(n))
12
Complexidade do algoritmo de inserção
O algoritmo RB_insere, sem contar o RB_fixup é O(lg(n))
RB_insere(T, z): 
 … // insere z na árvore como se fosse uma ABB normal
 esq[z] <- nil[T]
 dir[z] <- nil[T]
 cor[z] <- vermelho
 RB_fixup(T, z)
13
Complexidade do algoritmo de inserção
No algoritmo RB_fixup o laço while, repete uma vez no caso 
2 e mais do que 2 no caso 3.
A recoloração pode se propagar até o nó raiz.
O algoritmo de inserção é portanto O(lg(n))
14
Para pensar...
Dê um exemplo de inserção em uma árvore rubro-negra (de 
altura >=5) cuja recoloração dos nós se propaga até a raiz.
Justifique a sua resposta.
15
Remoção
O algoritmo de remoção atua de forma análoga ao 
algoritmo de remoção em uma ABB.
No final da remoção o algoritmo, caso necessário:
Muda as cores de alguns nós, e
Re-estrutura a árvore por meio de rotações.
16
Remoção
O algoritmo de remoção atua de forma análoga ao 
algoritmo de remoção em uma ABB.
No final da remoção o algoritmo, caso necessário:
Muda as cores de alguns nós, e
Re-estrutura a árvore por meio de rotações.
O algoritmo é um pouco mais complexo que o do 
algoritmo de inserção e há vários casos a considerar.
→ O algoritmo de remoção é O(log n).
17
AVL vs Rubro-Negra
18
AVL vs Rubro-Negra
AVL: 1.44 lg(n+1)
ARN: 2 lg(n+1)
Altura (pior caso)
+balanceada
19
AVL vs Rubro-Negra
Árvores AVL são mais rigidamente balanceadas que ARN:
AVL→ A inserção e remoção são mais lentas.
AVL→ A busca (recuperação) são mais rápidas.
AVL: 1.44 lg(n+1)
ARN: 2 lg(n+1)
Altura (pior caso)
20
AVL vs Rubro-Negra
Árvores AVL são mais rigidamente balanceadas que ARN:
AVL→ A inserção e remoção são mais lentas.
AVL→ A busca (recuperação) são mais rápidas.
AVL: Eficiente para árvores que mudam pouco.
ARN: Eficiente para árvores de mudam muito.
AVL: 1.44 lg(n+1)
ARN: 2 lg(n+1)
Altura (pior caso)
21
Sobre a monografia/projeto
22
Sobre a monografia/projeto
A monografia/projeto é uma componente importente na 
disciplina. Podem ser consideradas diferentes formas:
Estudo (em detalhe) de um artigo atual sobre algoritmos e 
estrura de dados (e.g. formulação de um problema teórico 
interessante).
Implementação de uma estrutura de dados, e descrição de 
um conjunto de experimentos, e/ou como melhorar os 
procedimentos em termos práticos (pode considerar estudo 
comparativo entre algoritmos/EDs).
Compilação/resumo de alguns artigos relacionados com 
algum tópico de algoritmos e estrutura de dados avançadas 
(criação/adoção de uma taxonomia).
Melhora substancial de artigos de wikipedia-BR para tópicos 
de estrutura de dados avançadas (aqui não precisa 
relatório).
A monografia não está limitada aos tópicos tratados em aula ou na ementa.
23
Sobre a monografia/projeto
Alguns tópicos interessantes de uma disciplina semestral de 
Estrutura de dados avançadas do MIT:
http://courses.csail.mit.edu/6.851/spring12/lectures/
24
Sobre a monografia/projeto
As propostas, conjuntamente com a lista de integrantes do 
grupo devem ser regristradas no seguinte formulário:
URL: 
https://docs.google.com/forms/d/1MwZqI79OB484mntUFQDdEkHWMwqroqbF_i5TGS9dlgQ/viewform
Deadline: 15/08 
Após a data não pode mudar de tópico.
Nota: A complexidade/completude do trabalho deve ser 
proporcional ao número de integrantes (~3/4 alunos)
25
Árvores Digitais (Trie)
26
ABBs
Problema de busca geral
Conjunto de chaves (S).
Elemento x a buscar em S.
27
ABBs
Problema de busca geral
Conjunto de chaves (S).
Elemento x a buscar em S.
Até agora vimos que:
As chaves são elementos 
indivisíveis.
As chaves tem mesmo 
tamanho.
28
ABBs
Problema de busca geral
Conjunto de chaves (S).
Elemento x a buscar em S.
Até agora vimos que:
As chaves são elementos 
indivisíveis.
As chaves tem mesmo 
tamanho.
E se a busca consistir em frases / texto literário?
29
Árvores digitais (Árvore de prefixos)
Palavras/Chaves:
● A
● to
● tea
● ted
● ten
● inn 
30
Árvores digitais (Árvore de prefixos)
31
Árvores digitais (Árvore de prefixos)
Todos os descendentes 
de um nó tem um prefixo 
em comum
Palavras com tamanho variável e ilimitado
32
Árvores digitais (Árvore de prefixos)
Uma árvore TRIE (ATRIE) é uma estrutura de dados do 
tipo árvore ordenada que permite a recuperação de 
informação.
A ATRIE é utilizada para armazenar um array associativo 
em que as chaves são normalmente cadeias de caracteres
33
Árvores digitais (Árvorede prefixos)
Uma árvore TRIE (ATRIE) é uma estrutura de dados do 
tipo árvore ordenada que permite a recuperação de 
informação.
A ATRIE é utilizada para armazenar um array associativo 
em que as chaves são normalmente cadeias de caracteres
A chave é uma sequencia de símbolos 
pertencentes a um alfabeto.
As chaves são armazenadas nas 
folhas da árvore, os nós internos são 
parte do caminho que direciona a busca.
Compara digitos da chave 
individualmente
34
TRIE originado de 'Information reTRIEval'
TRIE = digital tree = radix tree = prefix tree
35
Shannon + McCarthy + Fredkin + Waizenbaum
[6] Weizenbaum. Rebel at Work. A documentary by Peter Haas and Silvia Holzinger
http://www.ilmarefilm.org/W_E_4_70.htm
36
Árvores TRIE
As chaves são armazenadas nas 
folhas da árvore, os nós internos são 
parte do caminho que direciona a busca
(os nós internos também podem ser 
chaves).
Palavras/Chaves:
● A
● to
● tea
● ted
● ten
● Inn
● i
● inn 
37
Árvores TRIE
 A busca se inicia na raiz.
 As busca continua com a subárvore 
associado ao símbolo/caratere 
procurado até chegar a uma folha (ou 
nó interno)
Essa estrutura permite fazer buscas 
eficiente de cadeias que 
compartilham prefixo.
38
Exemplo de árvore TRIE
39
Exemplo de árvore TRIE
40
Exemplo de árvore TRIE
41
Árvore TRIE
Uma árvore TRIE é um caso especial de um autômato finito 
determinista (máquina de estados finito) que sirve para 
armazenar/representar um conjunto de cadeias.
A máquina está em apenas um estado por vez (este estado é 
chamado estado atual).
O estado de aceitação é aquele em que a máquina relata que a 
sequência de entrada, como processada até agora, é membro do 
conjunto de cadeias aceitas.
Estado inicial
Este exemplo mostra 
um autômato que 
determina se um 
número binário tem 
um número par ou 
ímpar de 0's
42
Árvore TRIE
Definição formal da ATRIE para armazenar um conjunto 
de cadeia E:
43
Árvore TRIE
Definição formal da ATRIE para armazenar um conjunto 
de cadeia E:
 é o conjunto de estados, cada um dos quais representa 
um prefixo de E. 
 é o alfabeto sobre o qual estão definidas as cadeias.
44
Árvore TRIE
Definição formal da ATRIE para armazenar um conjunto 
de cadeia E:
 é o conjunto de estados, cada um dos quais representa 
um prefixo de E. 
 é o alfabeto sobre o qual estão definidas as cadeias.
 é a função de transição de estados.
45
Árvore TRIE
Definição formal da ATRIE para armazenar um conjunto 
de cadeia E:
 é o conjunto de estados, cada um dos quais representa 
um prefixo de E. 
 é o alfabeto sobre o qual estão definidas as cadeias.
 é a função de transição de estados.
 corresponde ao estado inicial (igua à cadei vazia).
46
Árvore TRIE
Definição formal da ATRIE para armazenar um conjunto 
de cadeia E:
 é o conjunto de estados, cada um dos quais representa 
um prefixo de E. 
 é o alfabeto sobre o qual estão definidas as cadeias.
 é a função de transição de estados.
 corresponde ao estado inicial (igua à cadei vazia).
 é o conjunto de estados de aceitação
 , A = E
47
Exemplos de alfabetos e chaves
Alfabetos
Chaves
A chave é determinada pela posição na árvore.
48
Árvore TRIE (árvore m-ária)
49
Busca digital
O método de busca digital é análogo à busca manual em 
dicionários:
Com a primeira letra da palavra são determinadas todas 
as páginas que contêm as palavras iniciadas por aquela 
letra e assim por diante.
50
Busca digital
O método de busca digital é análogo à busca manual em 
dicionários:
Com a primeira letra da palavra são determinadas todas 
as páginas que contêm as palavras iniciadas por aquela 
letra e assim por diante.
A busca de uma chave de 
tamanho m, no pior caso terá 
um custo de O(m)
51
Busca digital
O método de busca digital é análogo à busca manual em 
dicionários:
Com a primeira letra da palavra são determinadas todas 
as páginas que contêm as palavras iniciadas por aquela 
letra e assim por diante.
A busca de uma chave de 
tamanho m, no pior caso terá 
um custo de O(m)
Independe do número total 
de chaves.
Depende do tamanho da 
chave procurada.
52
Montando uma árvore TRIE
Considere as seguintes chaves:
53
Montando uma árvore TRIE
54
Montando uma árvore TRIE
55
Montando uma árvore TRIE
56
Montando uma árvore TRIE
57
Montando uma árvore TRIE
58
Montando uma árvore TRIE
59
Montando uma árvore TRIE
60
Montando uma árvore TRIE
Na implementação: deve se evitar inúmeros ponteiros núlos.
61
Exercício
Quais palavras/chaves estão representadas nesta TRIE?
62
Implementando uma ATRIE
Implementação mais simples: R-way
A árvore contém dois tipos de nós:
Nó de desvio, e
Nó de informação.
63
Implementando uma ATRIE
Implementação mais simples: R-way
A árvore contém dois tipos de nós:
Nó de desvio, e
Nó de informação.
Cada nó de desvio contém todos os valores do alfabeto 
mais um símbolo especial para determinar a chave.
(há desperdício de espaço)
64
Implementando uma ATRIE
Implementação mais simples: R-way
A árvore contém dois tipos de nós:
Nó de desvio, e
Nó de informação.
Cada nó de desvio contém todos os valores do alfabeto 
mais um símbolo especial para determinar a chave.
(há desperdício de espaço)
Considere uma ATRIE para armazenar chaves do alfabeto 
{a,b,c,d,...,y,z} (27 letras)
65
Implementando uma ATRIE
Implementação mais simples: R-way
A árvore contém dois tipos de nós:
Nó de desvio, e
Nó de informação.
Cada nó de desvio contém todos os valores do alfabeto 
mais um símbolo especial para determinar a chave.
(há desperdício de espaço)
Considere uma ATRIE para armazenar chaves do alfabeto 
{a,b,c,d,...,y,z} (27 letras)
66
Implementando uma ATRIE
67
Implementando uma ATRIE
68
Implementando uma ATRIE
69
Inserção em uma ATRIE
70
Inserção em uma ATRIE
71
Remoção em uma ATRIE
Busca-se o nó que representa o final da palavra a ser 
removida.
São removidos os nós que possuem apenas um filho 
pelo caminho ascendente.
A remoção é concluída quando se encontra um nó com 
mais de um filho.
72
Remoção em uma ATRIE
73
Remoção em uma ATRIE
	Slide 1
	Slide 2
	Slide 3
	Slide 4
	Slide 5
	Slide 6
	Slide 7
	Slide 8
	Slide 9
	Slide 10
	Slide 11
	Slide 12
	Slide 13
	Slide 14
	Slide 15
	Slide 16
	Slide 17
	Slide 18
	Slide 19
	Slide 20
	Slide 21
	Slide 22
	Slide 23
	Slide 24
	Slide 25
	Slide 26
	Slide 27
	Slide 28
	Slide 29
	Slide 30
	Slide 31
	Slide 32
	Slide 33
	Slide 34
	Slide 35
	Slide 36
	Slide 37
	Slide 38
	Slide 39
	Slide 40
	Slide 41
	Slide 42
	Slide 43
	Slide 44
	Slide 45
	Slide 46
	Slide 47
	Slide 48
	Slide 49
	Slide 50
	Slide 51
	Slide 52
	Slide 53
	Slide 54
	Slide 55
	Slide 56
	Slide 57
	Slide 58
	Slide 59
	Slide 60
	Slide 61
	Slide 62
	Slide 63
	Slide 64
	Slide 65
	Slide 66
	Slide 67
	Slide 68
	Slide 69
	Slide 70
	Slide 71
	Slide 72
	Slide 73