Lista4

Lista de Exercícios 3
Tarefa Indiviual

Data de entrega: 01/06

Selecione 2 exercícios distintos de cada seção para resolver. Os exercícios devem ser entregues em sala de aula ao monitor. Não serão aceitas submissões eletrônicas nem entregas após o horário da aula. Seção 1 - Exercícios Árvores BST
1. Descreva vantagens e desvantagens de se implementar árvores binárias de busca usando vetores ou ponteiros.
2. Implemente 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”.
3. Mostre passo a passo a árvore binária de busca resultante das seguintes operações: Inserção de 5,
9, 7, 4, 12, 15, 11.
4. Implemente uma função que some os elementos pares de uma árvore binária de busca.
5. Duas árvores binárias são similares se elas são vazias ou se elas não são vazias e suas subarvores da esquerda são similares esuas subarvores da direita são também similares. Escreva um algorítmo para determinar se duas árvores binárias são similares.
6. Dada uma árvore binária que represente uma expressão matemática, construa um algoritmo que apresente (imprima) a versão posfixa (ou pós-ordem) da expressão.

Seção 2 - Exercícios Árvores AVL e SBB
1. Explique a busca e a inserção em Árvore AVL.
2. Faça a inserção da seguinte sequência de chaves em uma árvore AVL vazia (liste a rotação efetuada na inserção da chave quando ocorrer.): 36, 15, 24, 43, 60, 40, 10, 70, 65, 35, 42, 43.
3. Explique a remoção em Árvore AVL.
4. Remova as chaves 24, 43 e 35 da árvore resultante do exercício 2 desta seção.
5. Analise uma árvore T que armazena 100.000 itens. Quais são o pior e o melhor casos em relação à altura de T das seguintes árvores:
• T é uma árvore binária de pesquisa (ABP);
• T é uma árvore AVL.
6. Explique a busca e inserção em Árvore SBB.
7. Quais as principais diferenças entre Árvores Avl e SBB?
8. Explique a remoção em Árvore SBB

9. Faça a inserção da seguinte sequência de chaves em uma árvore SBB vazia