1) Represente a árvore binária de busca abaixo usando a notação com parênteses aninhados
——————– 20
——————- / \
—————- 10 30
————————- / \
———————– 25 35
——————— / \
——————– 21 27
2) Defina uma estrutura de dados para representar uma árvore binária de busca, armazenando um conteúdo (character) e uma chave (inteira).
3) Descreva vantagens e desvantagens de implementar árvores binárias de busca usando vetores ou ponteiros.
4) Implementar uma função para inserção em árvore binária de busca, usando o método iterativo (i.e., sem recursão). Não é necessário ter ponteiro “pai”.
5) Implemente uma função que calcule a altura de uma árvore binária de busca. Qual é o tipo de percurso usado na implementação?
6) Mostre passo a passo a árvore binária de busca resultante das seguintes operações:
a) Inserção de 5, 9, 7, 4, 12, 15, 11
b) A árvore resultante pode ser considerada uma árvore AVL? Justifique:
c) Remoção do 9.
7) Dada a árvore 2-3-4 abaixo, insira a chave 25. A árvore resultante deve ser uma árvore 2-3-4.
———20
——-/ \
—–17 22 – 24 – 29
7) Explique uma vantagem de incluir elementos na raiz de uma arvore binária de busca.
8) Crie uma árvore rubro-negra (RN), incluíndo as chaves 20, 7, 12, 30, 22, nesta ordem, e mostre a árvore RN resultante após cada inserção. Usar as regras de ajuste aprendidas em aula.
9) Usando a árvore rubro negra acima, crie uma arvore 2-3-4 correspondente.
10) Dada a árvore B abaixo, de grau mínimo (t) igual a 2.
a) inclua as chaves, 20, 21, 28 e 31, nesta ordem, e mostre a árvore B resultante após cada inserção. A árvore poderá ser dividida antes da inclusão, para que os nós abriguem as chaves corretas.
———————————– 26
————————–/ \
———12 – 17 – 22 29
—— / | | \ / \
7-9 13 18-19 23-24 27 30-34-35
b) Porque não podemos incluir o elemento 25 direto na raiz, mesmo que o nó possua espaços livres?
11) Considere a estrutura abaixo para representar uma árvore binária de busca.
typedef struct tNo {
int chave;
tNo *esq, *dir, *pai;
} tNo;
Escreva um algoritmo em C ou em pseudocódigo semelhante a C que insira uma nova chave na raiz de uma árvore. Seu algoritmo deve receber como entrada um apontador para o nó raíz de uma árvore e uma chave, e após incluir esta chave na raiz da árvore de binária de busca, o algoritmo deve retornar um ponteiro para o nova raiz da árvore.
As funções abaixo podem ser utilizadas em seu algorimo:
tNo* rotacaoDir(tNo *no)
tNo* rotacaoEsq(tNo *no)
estas funções recebem como parâmetro um ponteiro para um nó, raiz de uma subárvore, e retornam um ponteiro para a nova raiz da subárvore após a rotação para direita ou para a esquerda, respectivamente.
12) Considere uma árvore binária de busca onde os nós contém um campo informando a cor do nó (preto ou vermelho). Implemente uma função de validação que receba uma árvore binária com estas características e verifique se esta árvore é ou não uma árvore rubro-negra.
Fonte: os exercícios são fonte própria, e adaptações de exercícios dos livros da bibliografia do curso, como Cormen et. al, Ziviani et.atl.