respostas

Prévia do material em texto

Luca de Paula Nascimento Lima 
RA: 140427 
AULA 6: Exercício teórico métodos de pesquisa 
 
1) (0,4) Suponha que nós com chaves {50, 30, 70, 20 40, 60, 80, 15, 25, 35, 45, 36} são 
inseridos nesta ordem em uma árvore binária. 
a) Desenhe a árvore resultante. 
 
b) Em seguida, remova o nó 30 e mostre a nova árvore. 
 
 
2) (0,3) A operação de eliminação é comutativa, ie, a eliminação de x e depois y 
resulta na mesma árvore que a eliminação de y e depois x? Mostre um contra- 
exemplo. 
 
R: temos a árvore (15(5()(10()()))30()()), se removermos primeiro o 15, se o algoritmo 
buscar primeiro o nó mais à direita da subárvore da esquerda, o y vai tomar o seu lugar 
ficando (10(5)(30)), depois tirando o 10 teremos (5()(30()())) ou (30(5()())()), porém se 
buscarmos primeiro o nó mais à esquerda da subárvore à direita chegaremos no resultado 
(30(5()(10()())()) e tirando o 10 ficaremos com (30(5()())()) agora se tirarmos o 10 primeiro 
ficaremos com 
(15(5()())(30()()), e depois tirando o 15 ficaremos com (5()(30()())) ou (30)(5()())()). 
 
 
 
 
 
 
3) (0,3) No slide 16 foi apresentado um algoritmo de remoção da raiz em uma árvore 
binária de busca. Escreva um algoritmo de remoção completo em árvore binária, 
ie, para remover qualquer elemento da árvore. Explique os passos/lógica do 
algoritmo. 
 
R: 
int remove_ArvBin(ArvBin *raiz, int valor){ 
if(raiz==NULL) return 0; 
struct NO* ant = NULL 
struct NO* atual =*raiz; 
while(atual != NULL){ 
if(valor==atual->info){ 
*raiz = remove_atual(atual); 
else{ 
if(ant->dir == atual) 
ant->dir = remove_atual(atual); 
else 
ant->esq = remove_atual(atual); 
} 
return 1 
} 
ant =atual; 
if(valor > atual->info) 
atual = atual->dir; 
else 
atual = atual->esq; 
} 
 
struct NO* remove_atual(struct NO* atual){ 
struct NO *no1, *no2; 
if(atual->esq == NULL){ 
no2 = atual->dir; 
free(atual); 
return no2; 
} 
no1 = atual; 
no2 = atual->esq; 
while(no2->dir != NULL){ 
no1 = no2; 
no2 = no2->dir; 
} 
if(no1 != atual){ 
no1->dir = no2->esq; 
no2->esq = atual->esq; 
} 
no2->dir = atual->dir; 
free(atual); 
return no2; 
}