Aula de Exercícios 07 (Árvores B, PV e Cartesianas) - Slide

Prévia do material em texto

Aula de Exercícios
Estrutura de Dados e Algoritmos
20/03/2014
José Claudivan
Ramon Bezerra
Árvore Preto-Vermelha
Árvore Preto-Vermelha – Características
• Possui uma característica particular: cor do nó;
• É balanceada a partir de invariantes, restrições pelas cores dos nós;
• Uma árvore preto-vermelho com n nós internos tem no máximo a 
altura de h ≤ 2.lg(n+1).
Árvore Preto-Vermelha – Características
• Cada nó possui uma cor: ou preta ou vermelha
• Toda folha (NIL) é preta
• A raiz é preta
• Todos os filhos de um nó vermelho são pretos
• Black-Height: Todo caminho simples de um nó a uma folha 
descendente contém o mesmo número de nós (≠ NIL) pretos.
Árvore Preto-Vermelha – Exemplo
Árvore Preto-Vermelha – Casos de ajuste
Para um novo nó (Vermelho), temos:
• Caso 1: Se o novo nó é uma raiz, deve ser preto.
• Caso 2: Se o novo nó não é uma raiz, seu pai deve ser preto.
• Caso 3: Se pai do novo nó é vermelho, o pai e o tio devem ser pretos e o
avô do nó deve ser vermelho. Depois, verifica-se o Caso 1 para o avô.
• Caso 4: Se o novo nó é filho à direita e o pai é filho à esquerda, aplica-se
rotação no pai do novo nó à esquerda, e vice-versa.
• Caso 5: Se o novo nó e o pai são filhos à direita, o pai deve ser preto e o
avô vermelho. Depois, aplica-se a rotação no avô do novo nó à esquerda.
Árvore Preto-Vermelha – Exercício
1. Insira os seguintes valores em uma arvore PV inicialmente vazia e 
mostre a árvore (incluindo a cor dos nós) após cada operação: 41, 38, 
31, 12, 19, 8.
Demonstração: trees.jar
Árvore Preto-Vermelha – Exercício
2. Insira um nó com chave 8 na árvore abaixo. Se o nó for colorido de 
vermelho, a árvore obtida é PV? E se for colorido de preto?
Demonstração: trees.jar
Árvore Preto-Vermelha – Exercício
3. Se a raiz de uma árvore PV tem cor vermelha e a alteramos para 
preto, a árvore continua sendo PV? E se fossa a situação inversa?
Árvore Preto-Vermelha – Exercício
3. Se a raiz de uma árvore PV tem cor vermelha e a alteramos para 
preto, a árvore continua sendo PV? E se fossa a situação inversa?
Sim, pois obedece a propriedade de que a raiz tem que ser preta, se 
fosse o contrário e a raiz passasse a ser vermelha infringiria nessa 
mesma propriedade, logo não seria PV.
Árvore Preto-Vermelha – Exercício
4. Qual a altura máxima de uma árvore PV com altura preta igual a 4?
A altura máxima nesse caso será 7 para o BH = 4.
Árvore B
Árvore B – Características 
• Assegura todas as folhas no mesmo nível;
• Possui um número máximo de filhos para cada nó (página);
• Em cada nó é guardado uma lista de elementos (LinkedList);
Árvore B – Propriedades
Para uma árvore B de ordem m, temos:
• Cada nó tem no máximo m filhos;
• O número mínimo de filhos de um nó interno é m/2;
• O número máximo de elementos (chaves) em um nó (página) é m-1;
• A raiz pode ser folha ou ter no mínimo dois filhos;
• Todas as folhas estão no mesmo nível;
• Um nó interno com k filhos tem, no máximo, k-1 elementos;
• Os elementos (chaves) de cada nó servem como separadores dos filhos, 
de acordo com sua ordem.
• O nó raiz possui entre 1 e 2m elementos.
Árvore B – Exemplo 
• Qual a ordem da árvore B a seguir?
Árvore B – Exemplo 
• Qual a ordem da árvore B a seguir? 4
Árvore B – Exemplo 
• Qual a ordem da árvore B a seguir? 
Árvore B – Exemplo 
• Qual a ordem da árvore B a seguir? 4
Árvore B – Exercícios 
5. Qual o número máximo de elementos que podem ser armazenados em uma
árvore B de ordem 20 com altura 2? Justifique sua resposta.
Árvore B – Exercícios 
5. Qual o número máximo de elementos que podem ser armazenados em uma
árvore B de ordem 20 com altura 2? Justifique sua resposta.
Ordem da árvore = 20
Árvore B – Exercícios 
5. Qual o número máximo de elementos que podem ser armazenados em uma
árvore B de ordem 20 com altura 2? Justifique sua resposta.
Ordem da árvore = 20; Altura da árvore = 2;
Árvore B – Exercícios 
5. Qual o número máximo de elementos que podem ser armazenados em uma
árvore B de ordem 20 com altura 2? Justifique sua resposta.
Ordem da árvore = 20; Altura da árvore = 2;
Nº máximo de chaves por nó = 19.
Árvore B – Exercícios 
5. Qual o número máximo de elementos que podem ser armazenados em uma
árvore B de ordem 20 com altura 2? Justifique sua resposta.
Ordem da árvore = 20; Altura da árvore = 2;
Nº máximo de chaves por nó = 19.
Considerando que a árvore B é sempre completa, temos:
Árvore B – Exercícios 
5. Qual o número máximo de elementos que podem ser armazenados em uma
árvore B de ordem 20 com altura 2? Justifique sua resposta.
Ordem da árvore = 20; Altura da árvore = 2;
Nº máximo de chaves por nó = 19.
Considerando que a árvore B é sempre completa, temos:
1 nó
Árvore B – Exercícios 
5. Qual o número máximo de elementos que podem ser armazenados em uma
árvore B de ordem 20 com altura 2? Justifique sua resposta.
Ordem da árvore = 20; Altura da árvore = 2;
Nº máximo de chaves por nó = 19.
Considerando que a árvore B é sempre completa, temos:
1 nó
... 20 nós
Árvore B – Exercícios 
5. Qual o número máximo de elementos que podem ser armazenados em uma
árvore B de ordem 20 com altura 2? Justifique sua resposta.
Ordem da árvore = 20; Altura da árvore = 2;
Nº máximo de chaves por nó = 19.
Considerando que a árvore B é sempre completa, temos:
1 nó
... 20 nós
... 400 nós
Árvore B – Exercícios 
5. Qual o número máximo de elementos que podem ser armazenados em uma
árvore B de ordem 20 com altura 2? Justifique sua resposta.
Ordem da árvore = 20; Altura da árvore = 2;
Nº máximo de chaves por nó = 19.
Considerando que a árvore B é sempre completa, temos:
1 nó
... 20 nós
... 400 nós
Somando os nós, temos: 
1+20+400 = 421 nós
Se cada nó tem 19 chaves, 
então:
400x19 = 7999 elementos
Árvore B – Exercícios 
6. Considerando a representação abaixo de árvore B, implemente um método
(usando recursão) que retorna o maior elemento armazenado em uma árvore B.
Faça a análise do algoritmo.
Árvore B – Exercícios 
6. Considerando a representação abaixo de árvore B, implemente um método
(usando recursão) que retorna o maior elemento armazenado em uma árvore B.
Faça a análise do algoritmo.
Busca, caso seja o último nó, o 
último elemento da lista interna.
Senão, busca o último nó da árvore, 
sempre pela direita.
Árvore B – Exercícios 
6. Considerando a representação abaixo de árvore B, implemente um método
(usando recursão) que retorna o maior elemento armazenado em uma árvore B.
Faça a análise do algoritmo.
Método externo, chamando a 
busca pelo maior elemento a 
partir da raiz.
Árvore B – Exercícios 
7.Considerando a ordem alfabética, mostre o resultado da inserção dos elementos
F,S,Q,K,C,L,H,T,V,W,M,R,N,P,A,B,X,Y,D,Z,E nessa ordem. Considere a árvore B de
ordem 3.
Desenhe a árvore após a inserção de cada elemento.
Árvore B – Exercícios 
7.Considerando a ordem alfabética, mostre o resultado da inserção dos elementos
F,S,Q,K,C,L,H,T,V,W,M,R,N,P,A,B,X,Y,D,Z,E nessa ordem. Considere a árvore B de
ordem 3.
Desenhe a árvore após a inserção de cada elemento.
insert(S)
F S
insert(Q)
F Q S 
OVERFLOW!
split()
F S
Q
insert(F)
F
Árvore B – Exercícios 
7.Considerando a ordem alfabética, mostre o resultado da inserção dos elementos
F,S,Q,K,C,L,H,T,V,W,M,R,N,P,A,B,X,Y,D,Z,E nessa ordem. Considere a árvore B de
ordem 3.
Desenhe a árvore após a inserção de cada elemento.
insert(K)
S
Q
F K
insert(C)
S
Q
C F K 
OVERFLOW!
split()
S
F Q
KC
insert(L)
S
F Q
C K L
Árvore B – Exercícios 
7.Considerando a ordem alfabética, mostre o resultado da inserçãodos elementos
F,S,Q,K,C,L,H,T,V,W,M,R,N,P,A,B,X,Y,D,Z,E nessa ordem. Considere a árvore B de
ordem 3.
Desenhe a árvore após a inserção de cada elemento.
insert(H)
S
F Q
C H K L
OVERFLOW!
split()
S
F K Q
C
OVERFLOW!
H L
split()
F Q
K
C SH L
...
Cartesian Tree
Cartesian Tree – Exercícios
8. Qual o formato da cartesian tree após a inserção dos seguintes números: 12, 8, 4, 
10, 25, 30, 9, 2, 15, 17. Demonstre passo a passo as inserções de cada elemento.
12 8
insert(8)
lastElement = 12
12 8
insert(4)
lastElement = 8
12
4
8
insert(10)
lastElement = 4
12
4
10
insert(12)
lastElement = null
Cartesian Tree – Exercícios
8. Qual o formato da cartesian tree após a inserção dos seguintes números: 12, 8, 4, 
10, 25, 30, 9, 2, 15, 17. Demonstre passo a passo as inserções de cada elemento.
insert(30)
lastElement = 25
10
25
8
insert(9)
lastElement = 30
12
4
10
8
insert(25)
lastElement = 10
12
4
10
25
8
12
4
30
9
25
30
Cartesian Tree – Exercícios
8. Qual o formato da cartesian tree após a inserção dos seguintes números: 12, 8, 4, 
10, 25, 30, 9, 2, 15, 17. Demonstre passo a passo as inserções de cada elemento.
8
insert(2)
lastElement = 9
12
4
10
2
8
insert(15)
lastElement = 2
12
4
10
2
9
25
30
15
8
insert(17)
lastElement = 15
12
4
10
2
9
25
30
15
17
9
25
30
Cartesian Tree – Exercícios
8. Qual o formato da cartesian tree após a inserção dos seguintes números: 12, 8, 4, 
10, 25, 30, 9, 2, 15, 17. Demonstre passo a passo as inserções de cada elemento.
PERCURSO EM ORDEM 
= 
SEQUÊNCIA NUMÉRICA
Cartesian Tree – Exercícios
9. Ainda do exercício anterior, qual o RMQ(Range Minimum Query) da subsequência 
{12, 8, 4, 10}? e qual o LCA(Lowest Commom Ancestor) entre 30 e 15?
RMQ(12,10) = ?
Cartesian Tree – Exercícios
9. Ainda do exercício anterior, qual o RMQ(Range Minimum Query) da subsequência 
{12, 8, 4, 10}? e qual o LCA(Lowest Commom Ancestor) entre 30 e 15?
RMQ(12,10) = 4
Cartesian Tree – Exercícios
9. Ainda do exercício anterior, qual o RMQ(Range Minimum Query) da subsequência 
{12, 8, 4, 10}? e qual o LCA(Lowest Commom Ancestor) entre 30 e 15?
LCA(30,15) = ?
Cartesian Tree – Exercícios
9. Ainda do exercício anterior, qual o RMQ(Range Minimum Query) da subsequência 
{12, 8, 4, 10}? e qual o LCA(Lowest Commom Ancestor) entre 30 e 15?
LCA(30,15) = 2
Referências – Árvore Preto-Vermelha 
• https://3917994b-a-a6606a5f-s-
sites.googlegroups.com/a/computacao.ufcg.edu.br/edaufcg/cronogra
ma/Arvore%20PV.pdf?attachauth=ANoY7cpSNc1tmbr92wHf1u7TKOB
mqJWUkIWFC9v5_nzF97tkisQAC_qbN85TYbRDdKanTx2bOD22JSsQ9R
7r7-9g4BBZ-ySsAePQRy6IcTLE7HPIkIDjIrOdZ-ia-
6qy7f775cIoHTFZZ7fXNTcOXntzycWVaSv1C1Y0jUd8I8aW3HTV8i6fFrY
PTAbBcwGHCCYyAjzasTbjbCFcQaQeUsxYfE-
L4gNH_6etLYIB1ahp28hDO6Itbdo%3D&attredirects=1
• http://www.ufjf.br/jairo_souza/files/2012/11/5-
Indexa%C3%A7%C3%A3o-Arvore-Vermelho-Preta.pdf
Referências – Árvore B
• https://3917994b-a-a6606a5f-s-
sites.googlegroups.com/a/computacao.ufcg.edu.br/edaufcg/cronogra
ma/Arvore%20B.pdf?attachauth=ANoY7cqZmgKksqFtUeEJBi_YyBHgU
M5cXbKQOV3U9opI1uxJcQaUCEAFZ1yEx9R-
hfLMl1wHneZq3S9VCZtXeTe3M95OybTTnBtyGMCL-
nesuO46UWBod0VZafbfzy_sn6wtjsyruSMJhoj_QTKL2v2M5CaY8R-
9qi9TDL-
ZdzLaQZqYvqyuruLJNsRcKPAGAPyUHORzF_NsZN48QRnbd2LD_o_97A
s1pudLxsOtovdarUcHbSjzGwk%3D&attredirects=0
• http://www.ufjf.br/jairo_souza/files/2012/11/5-
Indexa%C3%A7%C3%A3o-Arvore_B.pdf
Referências – Cartesian Tree
Material Anexo (Estágio Docência)