Lista_EDA_Arvores_B_PV_Cartesianas

Prévia do material em texto

Universidade Federal de Campina Grande 
Centro de Engenharia Elétrica e Informática 
Departamento de Sistemas e Computação 
Graduação em Ciência da Computação 
 
 
Lista de exercícios sobre Árvore-B, Árvore-PV, Cartesian Tree 
 
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. 
 
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? 
 
3. Qual a altura máxima de uma árvore PV com altura preta igual a 4? 
 
4. 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. 
 
5. Considerando a representação abaixo de árvore B, implemente um método 
(usando recursão) que retorna o maior elemento armazenado. Faça a análise 
do algoritmo. 
 
 
6. 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. 
 
7. 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. 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?