Modelagem

CENTRO FEDERAL DE EDUCAÇÃO TECNOLÓGICA DE MINAS
GERAIS
MESTRADO EM MODELAGEM MATEMÁTICA E COMPUTACIONAL
DISCIPLINA: Algoritmos e Estrutura de Dados

Lista de Exercícios no. 3

1. Considere as primeiras 15 letras do seu nome completo, desprezando letras repetidas.
Complete com outras à sua escolha se necessário.
a) Construa uma árvore binária de pesquisa com esta sequência.
b) A seguir embaralhe as letras e construa uma segunda árvore, seguindo a nova ordem das letras.
c) Finalmente, ordene as letras e construa a terceira árvore.
d) Para cada árvore, indique sua altura.
e) Conte o número de comparações necessário para encontrar as seguintes letras em cada árvore (ou indicar pesquisa sem sucesso): A, G, M, O, Z.
f) Mostre como retirar o elemento que está na raiz da segunda árvore.
g) Apresente o resultado do caminhamento central para todas as árvores.

a) Sequência:

DAYNEGOUVICLHBT

A altura da árvore é 7
Letras Número de comparações

A
G
M
O
Z

2
5
8 e pesquisa sem sucesso
4
3 e pesquisa sem sucesso

Retirar o elemento que está na raiz da segunda árvore, é retirar o elemento Y.
Retira o elemento Y que está na raiz da segunda árvore.
Em seguida ele deve ser substituído pelo registro mais a direita na subárvore a esquerda. Ou seja, ele deve ser substituído pelo elemento
V.

Após a retirada do elemento
Y, a árvore ficará:

O caminhamento central ocorre da seguinte maneira:
1 - Caminha na subárvore a esquerda na ordem central;
2 - Visita a raiz;
3 – Caminha na subárvore a direita na ordem central.
Dessa forma, temos que seguindo esses passos para percorrer a árvore da letra a, usando o caminhamento central, recuperam-se as chaves na ordem: A B C D E G H I L N O T U V Y.

b) Sequência:
LGNAUYCH
DIETOVB

A altura da árvore é 6

Letras Número de comparações

A
G
M
O
Z

3
2
3 e pesquisa sem sucesso
5
5 e pesquisa sem sucesso

Retirar o elemento que está na raiz da segunda árvore, é retirar o