Resumo_ABB

Esta é uma pré-visualização de arquivo. Entre para ver o arquivo original

Resumo Árvore Binária de Busca (ABB):
***********************************************************************************
OBS: Essa matéria caía na P3, mas foi removida da grade desse período! (2015.1)
Então >>ANTES<< de ler esse resumo, confirme se Árvore está sendo dada no período que você estiver cursando, pois podem alterar novamente!
***********************************************************************************
- Definição: 
Exatamente idêntica a uma Árvore Binária comum, a única diferença é que essa é >>SEMPRE<< ordenada!
A grande vantagem de estar ordenada é que evitamos percorrer a árvore inteira!
Recomendo ler primeiro o meu "Resumo_Arvore", pois grande parte do que eu citei lá, também vale pra esse tipo de árvore! :)
***********************************************************************************
Regras Importantes:
- Toda árvore ABB pode ser: 
Vazia
>> OU << 
Possui uma Raíz + uma Sub Árvore na esquerda + uma Sub Árvore na direita! 
- TODOS os Nós do lado esquerdo são sempre >>MENORES<< que a raíz!
- TODOS os Nós do lado direito são sempre >>MAIORES<< OU Iguais a raíz!
OBS: Igual somente se o enunciado disser que tem valores repetidos na árvore! E o critério de ordenação pode variar! Pode ser por nota, nome, valor, etc.
 
***********************************************************************************
typedef struct noABB {
 int info;
 struct noABB *esq;
 struct noABB *dir;
}NoABB;
Exatamente idêntico a struct de uma árvore binária comum! (Com exceção do nome :D ) 
OBS: Lembrando que se for um TAD árvore, o typedef será definido no Módulo de Interface, e a definição da struct fica assim:
struct NoABB{
 int info;
 NoABB *esq;
 NoABB *dir;
};
OBS: Não vou citar as funções básicas (Criar, liberar, inserir, etc) Pois >>NUNCA<< foram cobradas em prova, então não precisa se preocupar! :) 
--------------------------------------//------------------------------------------
- Funções importantes que podem ser cobradas em Prova: (Ou parecidas!)
OBS: Precisamos >>SEMPRE<< tratar todos os casos possíveis que evitem percorrer a árvore desnecessariamente! Na maioria dessas funções, é possível resolver o que está sendo pedido sem tratar nenhum desses casos...Mas vai estar totalmente errado! :(
Exemplo: Uma ABB armazena em cada Nó um ponteiro para Aluno (Informação), além de um ponteiro para esquerda e outro para a direita. (Como sempre!)
Cada aluno possui um nome com no máximo 80 caracteres e uma média.
OBS: A ABB está ordenada de forma crescente por média!
typedef struct aluno{
 char nome[81];
 float media;
}Aluno;
typedef struct noABB{
 Aluno *info;
 struct noABB *esq;
 struct noABB *dir;
}NoABB;
-------------------------------------//-------------------------------------------
- Função que exibe os dados do aluno com maior média:
void maiorMedia(NoABB *a){
 if(!a) return;
 if(!a->dir)
	 printf("Nome: %s Media: %.2f\n",a->info->nome, a->info->media);
 maiorMedia(a->dir);
}
Sabemos que o aluno de maior média está no extremo direito da árvore, pois o lado direito sempre armazena valores maiores que o do esquerdo (A não ser que esteja em ordem decrescente!)
Então a estratégia aqui é ir "avançando" pra direita até que o ponteiro da direita de algum Nó aponte para NULL! Isso quer dizer que ele é o último Nó do extremo direito e terá o maior valor com certeza!
Precisamos usar duas "setinhas" pra acessar a média! Pois NoABB *a é um ponteiro e Aluno *info é outro ponteiro! Então quando fazemos a->info estamos acessando o ponteiro do aluno (Endereço), por isso precisamos usar mais uma setinha a->info->media pra acessar o valor da média!
OBS:Lembrando que se ao invés de Aluno *info, fosse >> Aluno info << era só usar o conector ponto pra acessar a média! a->info.media 
----------------------------------------//----------------------------------------
- Função que conta e retorna a quantidade de alunos aprovados: 
(Média maior ou igual a 5.0)
int contaAprovados(NoABB *a) {
	if(!a) return 0;
	if(a->info->media < 5.0) return contaAprovados(a->dir);
	if(a->info->media == 5.0) return 1 + contaAprovados(a->dir);
	return 1 + (contaAprovados(a->esq)) + (contaAprovados(a->dir));
}
OBS: O Caso Base principal é >>SEMPRE<< quando a árvore é vazia! (Alcançou o NULL) 
Primeiro passo é verificar se o valor do Nó é menor que 5.0, pois só queremos valores maiores ou iguais! E como a árvore está ordenada, se o valor for menor, é só procurarmos na direita! 
return contaAprovados(a->dir); 
O segundo passo é se o valor for exatamente 5.0! Nesse caso vamos contar > 1 < aluno aprovado e continuar procurando os outros na direita. 
return 1 + contaAprovados(a->dir);
E por último, se o valor não é menor, nem igual a 5.0, só sobrou a possibilidade dele ser maior! Então precisamos contar 1 nos aprovados e procurar na esquerda e direita!
OBS: Um erro fatal aqui seria tratar maior ou igual na mesma condição! É só lembrar que se o valor do Nó for exatamente 5.0 >>NÃO<< podemos mais procurar na esquerda, onde só tem valores menores!
E sobre a última condição, muito cuidado pra não confundir! Se a média for maior que 5.0, temos que procurar tanto na esquerda quanto na direita! Mas é >>SÓ<< porque nesse caso, o valor que está no Nó da esquerda com certeza total é maior que 5.0!
********************************************************************************* 
- Pra facilitar o entendimento, dê uma olhada nessa ABB da foto:
Imagem: http://dsc.ufcg.edu.br/~dalton/2002.1/edados/aula14/img5.png
Imagina que ao invés de 5, queremos valores maiores ou iguais a 12: 
if(a->info->media == 12) return 1 + contaAprovados(a->dir);
OBS: Se o valor for exatamente 12, >>NÃO<< faz sentido procurarmos mais na esquerda!
Mas para valores maiores que 12, por exemplo: se estamos no Nó que armazena o 23, vamos contar 1 aprovado e procurar na esquerda e na direita! 
É aqui que tá o erro mais comum de todos! Apesar da esquerda sempre armazenar valores menores, 17 é menor que 23...Mas continua sendo >>MAIOR<< que o 12! Por isso que precisamos procurar nos dois lados se a média do aluno for maior que 5.0! :)
 
**********************************************************************************
Nas questões que citam algum valor ou um intervalo de valores, recomendo sempre começar tratando as condições do lado esquerdo (menor que 5.0), depois tratar quando for exatamente o valor que queremos (5.0) e por último valores maiores que 5.0!
OBS: Quando é só um valor específico eu prefiro tratar da esquerda pra direita se for ordenado de forma crescente! E da direita pra esquerda se estiver ordenado de forma decrescente!
--------------------------------------//-------------------------------------------
- Função que imprime em ordem >>Decrescente<< os dados dos alunos aprovados:
void imprimeAprovados(NoABB *a){
	if(!a) return ;
	
	imprimeAprovados(a->dir);
	if(a->info->media > 5.0){
		printf("Nome: %s Media: %.2f\n",a->info->nome, a->info->media);
		imprimeAprovados(a->esq);
	}
	if(a->info->media == 5.0)
		printf("Nome: %s Media: %.2f\n",a->info->nome, a->info->media);
}
O primeiro passo é avançar pra direita, pois temos que começar a imprimir a partir da maior média de todas! Logo em seguida, testamos se a média é maior que 5.0 e se for, vamos imprimindo e andando >>Sempre<< pra esquerda! Pois o que estava na direita já imprimimos!
De tanto andar pra esquerda, uma hora ou outra podemos (ou não :D ) encontrar uma média exatamente igual a 5.0! Justamente a última que devemos imprimir!
Nesse caso, não faz mais sentido andar pra esquerda (Média menor!) nem pra direita (Já imprimimos!), por isso só temos que imprimir a informação na tela e a função já pode ser encerrada.
OBS: Isso funciona mesmo se não tiver nenhuma média igual a 5.0 na árvore! Pois se não cair em nenhuma daquelas condições
a função vai ser encerrada! 
-------------------------------------//--------------------------------------------
- Função que conta e retorna a quantidade de alunos que possuem média dentro do intervalo mínimo e máximo recebido por parâmetro: 
int contaNoIntervalo(NoABB *a, float min, float max){
	if(!a) return 0;
	if(a->info->media < min) return contaNoIntervalo(a->dir, min, max);
	if(a->info->media == min) return 1 + contaNoIntervalo(a->dir, min, max);
	if(a->info->media > max) return contaNoIntervalo(a->esq,min, max);
	if(a->info->media == max ) return 1 + contaNoIntervalo(a->esq, min, max);
	return (a->info->media > min && a->info->media < max) + contaNoIntervalo (a->esq,min, max) + contaNoIntervalo(a->dir,min, max);
}
Essa função segue o mesmo esquema da anterior, mas agora precisamos tratar mais algumas condições por causa do intervalo mínimo e máximo.
Se a média for menor que o mínimo: Vamos procurar na direita.
Se a média for igual ao mínimo: Achamos um aluno e vamos procurar os outros na direita!
Se a média for maior que o máximo: Vamos procurar na esquerda.
Se a média for igual ao máximo: Achamos um aluno e vamos procurar os outros na esquerda!
E por último verificamos se o valor está dentro do intervalo (Última condição que restou) e somamos com o total de alunos encontrados na esquerda e na direita! 
OBS: Sempre que é dado um intervalo de valores, eu prefiro tratar por último os valores que estão dentro do intervalo e todos os outros antes, mas isso é completamente opcional! :) 
----------------------------------------//-----------------------------------------
Exemplo 2: Temos uma ABB que armazena em cada Nó um ponteiro para struct Ponto (Coordenada x e y) e o enunciado pede pra criar uma função que recebe como parâmetro um Ponto e se o achar na árvore, retorna o Nível (Altura) do Nó, senão retorna -1. 
Dados do Enunciado:
typedef struct ponto{
 float x, y;
}Ponto;
typedef struct noABB{
 Ponto *p;
 struct noABB *esq;
 struct noABB *dir;
}NoABB;
Podemos usar a função ptoIgual que verifica se dois pontos são iguais: retorna 1 (Verdadeiro) ou 0 (Falso)
E a função ptoDistancia que retorna a distância de um Ponto.
OBS: A ABB está ordenada pela distância do Ponto!
int buscaPonto ( NoABB *a, Ponto *p){
	if(!a) return -1;
	return contaNivel(a, p, 0);
}
Sabemos que a altura de uma árvore vazia é -1, então esse será o nosso Caso Base na recursão.
Precisamos retornar a altura se achar o Ponto recebido por parâmetro, mas como vamos retornar algo que não temos? (Não temos um parâmetro que representa o Nível pra incrementar ou decrementar!)
Nesse caso, precisamos de uma função auxiliar pra criar justamente o parâmetro que falta! Pois se a árvore não é vazia, temos certeza absoluta total que estamos na Raíz que possui altura zero! Então é só enviar essa altura como parâmetro pra função auxiliar!
 
Função Auxiliar:
int contaNivel(NoABB* a, Ponto *p, int nivel){
	if(!a) return -1;
	if(ptoIgual(a->info, p)) return nivel; 
	if(ptoDistancia(p) < ptoDistancia(a->info))
		return contaNivel(a->esq, p, nivel+1);
	return contaNivel(a->dir, p, nivel+1);
}
OBS: Percebeu que essa questão é quase idêntica a função número 8 do "Resumo_Arvore"? :)
(Recomendo dar uma olhada na função 8, só pra observar as diferenças!)
Tudo idêntico, exceto por um mini detalhezinho na função auxiliar! Quando a árvore >NÃO< é ordenada precisamos criar uma variável auxiliar pra armazenar a altura quando vamos procurar no lado esquerdo!
h = contaNivel(a->esq, x, nivel+1); lembra? 
Temos que fazer isso porque o valor que queremos achar pode estar no lado esquerdo ou no direito! Mas quando a árvore está ordenada >>NÃO<< precisa de variável auxiliar!
Pois dependendo se o que procuramos é maior ou menor que a raíz, já sabemos se ele está no lado esquerdo ou direito da árvore! Ou seja, vamos fazer exatamente um >>ÚNICO<< percurso até chegar no valor que queremos encontrar! 
Por isso que compensa mil vezes mais usar ABB do que uma árvore Binária simples! Mas não se esqueça que ambas podem ser cobradas na P3! 
-------------------------------------//-------------------------------------------
OBS: Recomendo que você entenda e/ou decore a maior quantidade de funções desse resumo! :D