Até o momento criamos Árvores Binárias de Busca Balanceada (AVL) apenas com números inteiros. Nesta aula vamos aprender a criar uma Árvore Balanceada do tipo AVL com a Struct Pessoa em cada nó. Uma Árvore Binária Balanceada de Pessoas.
Vamos iniciar definindo nossa struct Pessoa. Cada Pessoa terá um nome (um vetor de caracteres de tamanho 25), uma idade (que será um número inteiro) e um cpf (que aqui também trataremos como um número inteiro). Caso queira, você pode incluir outros campos ou mesmo substituir alguns desses. A idade, por exemplo, pode ser substituída por uma struct data, com três inteiros, dia, mês e ano.
// struct Pessoa
typedef struct{
char nome[25];
int idade;
int cpf;
}Pessoa;
Agora vamos criar o nó da nossa Árvore Binária Balanceada AVL de Pessoas. Basicamente a única diferença em relação a uma Árvore AVL de números é que, no lugar de um campo inteiro temos um campo do tipo Pessoa que acabamos de criar. Esse campo é um ponteiro, por isso o asterisco ( * ). Os demais campos permanecem como já conhecemos de uma árvore balanceada, temos dois ponteiros, um para a subárvore a direita e outro para a subárvore a esquerda. Por fim, temos um campo do tipo short para guardar a altura da subárvore.
// Nó da nossa árvore binária AVL de Pessoas
typedef struct no{
Pessoa *pessoa;
struct no *esquerdo, *direito;
short altura;
}No;
Agora, vamos criar uma função que vai receber o endereço de uma Pessoa, vai alocar memória para um novo nó, vai salvar a Pessoa neste nó e retornar o endereço deste nó para quem chamou a função. Essa função irá facilitar o processo de inserção em nossa árvore. Um ponto importante aqui é não esquecer de inicializar os campos do nó com zero para a altura e NULL para os ponteiros das subárvores esquerda e direita.
// Função para criar um novo nó da nossa árvore
No* novoNo(Pessoa *x){
No *novo = malloc(sizeof(No));
if(novo){
novo->pessoa = x;
novo->esquerdo = NULL;
novo->direito = NULL;
novo->altura = 0;
}
else
printf("\nERRO ao alocar nó em novoNo!\n");
return novo;
}
Agora, precisamos de uma função auxiliar que irá nos ajudar a manter a altura de cada nó atualizada corretamente. Como cada subárvore pode ter uma altura diferente, a altura do nó raiz será a altura da maior subárvore mais 1. Esta função irá receber dois valores (a altura de duas subárvores) e retornar o maior.
// Função que retorna o maior dentre dois valores
short maior(short a, short b){
return (a > b)? a: b;
}
A função a seguir é outra função auxiliar que recebe o endereço de um nó e retorna sua altura, caso seja diferente de NULL, ou -1 se for NULL. Esta função será útil quando formos calcular o fator de balanceamento de um nó.
// Retorna a altura de um nó ou -1 caso ele seja null
short alturaDoNo(No *no){
if(no == NULL)
return -1;
else
return no->altura;
}
A função a seguir faz uso da função anterior (alturaDoNo) para calcular o fator de balanceamento de um nó, que será utilizado para definir se a árvore está balanceada ou se é necessário realizar alguma rotação.
// Calcula e retorna o fator de balanceamento de um nó
short fatorDeBalanceamento(No *no){
if(no)
return (alturaDoNo(no->esquerdo) - alturaDoNo(no->direito));
else
return 0;
}
Agora vamos iniciar as funções que farão as rotações para balancear nossa árvore. A função a seguir realiza uma rotação à esquerda. Observe alguns pontos importantes: primeiro, não verifico a necessidade da rotação dentro da função, isso é feito fora e quando a função for chamada significa que já sei que é necessário realizar uma rotação à esquerda; segundo, estude estre trecho de código sempre com papel e lápis na mão. É difícil compreender o que está acontecendo apenas olhando o código. Desenhe uma pequena árvore no papel e simule a execução de cada linha, isso ajudará na compreensão. Observe também que agora estamos fazendo uso das funções alturaDoNo, que definimos acima, para descobrir a altura das subárvores esquerda e direita, e da função maior, para descobrir qual subárvore possui a maior altura.
// função para a rotação à esquerda
No* rotacaoEsquerda(No *r){
No *y, *f;
y = r->direito;
f = y->esquerdo;
y->esquerdo = r;
r->direito = f;
r->altura = maior(alturaDoNo(r->esquerdo), alturaDoNo(r->direito)) + 1;
y->altura = maior(alturaDoNo(y->esquerdo), alturaDoNo(y->direito)) + 1;
return y;
}
A seguir temos uma função bastante similar à anterior, para realizar uma rotação à direita.
// função para a rotação à direita
No* rotacaoDireita(No *r){
No *y, *f;
y = r->esquerdo;
f = y->direito;
y->direito = r;
r->esquerdo = f;
r->altura = maior(alturaDoNo(r->esquerdo), alturaDoNo(r->direito)) + 1;
y->altura = maior(alturaDoNo(y->esquerdo), alturaDoNo(y->direito)) + 1;
return y;
}
Agora precisamos de duas rotações duplas. A seguir temos uma função para realizar uma rotação dupla Esquerda Direita. Observe que uma rotação dupla nada mais é que duas rotações simples, uma para a esquerda e outra para a direita.
// Rotação dupla Esquerda Direita
No* rotacaoEsquerdaDireita(No *r){
r->esquerdo = rotacaoEsquerda(r->esquerdo);
return rotacaoDireita(r);
}
Agora temos nossa segunda rotação dupla, Direita Esquerda. Na função anterior realizamos primeiro uma rotação a esquerda, manipulando a subárvore esquerda. Agora, realizamos primeiro uma rotação a direita, manipulando a subárvore da direita.
// Rotação dupla Direita Esquerda
No* rotacaoDireitaEsquerda(No *r){
r->direito = rotacaoDireita(r->direito);
return rotacaoEsquerda(r);
}
A seguir temos uma das funções mais importantes em uma árvore balanceada, a função que realiza o balanceamento de uma árvore balanceada. Esta função recebe o endereço do nó que está desbalanceado, verifica o tipo de rotação necessária para o balanceamento e, por fim, retorna a nova raiz da subárvore, agora balanceada.
/*
Função para realizar o balanceamento da árvore após uma inserção ou remoção
Recebe o nó que está desbalanceado e retorna a nova raiz após o balanceamento
*/
No* balancear(No *raiz){
short fb = fatorDeBalanceamento(raiz);
// Rotação à esquerda
if(fb < -1 && fatorDeBalanceamento(raiz->direito) <= 0)
raiz = rotacaoEsquerda(raiz);
// Rotação à direita
else if(fb > 1 && fatorDeBalanceamento(raiz->esquerdo) >= 0)
raiz = rotacaoDireita(raiz);
// Rotação dupla à esquerda
else if(fb > 1 && fatorDeBalanceamento(raiz->esquerdo) < 0)
raiz = rotacaoEsquerdaDireita(raiz);
// Rotação dupla à direita
else if(fb < -1 && fatorDeBalanceamento(raiz->direito) > 0)
raiz = rotacaoDireitaEsquerda(raiz);
return raiz;
}
A seguir apresentamos a função inserir. Esta função recebe a raiz de nossa árvore e a pessoa a ser inserida na árvore, realiza a inserção, verifica a necessidade de balanceamento e, por fim, retorna a raiz da árvore balanceada. Como estamos trabalhando com o tipo Pessoa e estamos usando o cpf como chave, não aceitamos cpf duplicado, ou seja, caso tente inserir uma pessoa com o cpf exatamente igual ao cpf de uma pessoa já existente na árvore, esta inserção não será feita.
/*
Insere um novo nó na árvore
raiz -> raiz da árvore
x -> valor a ser inserido
Retorno: endereço do novo nó ou nova raiz após o balanceamento
*/
No* inserir(No *raiz, Pessoa *x){
if(raiz == NULL) // árvore vazia
return novoNo(x);
else{ // inserção será à esquerda ou à direita?
if(x->cpf < raiz->pessoa->cpf)
raiz->esquerdo = inserir(raiz->esquerdo, x);
else if(x->cpf > raiz->pessoa->cpf)
raiz->direito = inserir(raiz->direito, x);
else
printf("\nInsercao nao realizada!\nO elemento %d a existe!\n", x->cpf);
}
// Recalcula a altura de todos os nós entre a raiz e o novo nó inserido
raiz->altura = maior(alturaDoNo(raiz->esquerdo), alturaDoNo(raiz->direito)) + 1;
// verifica a necessidade de rebalancear a árvore
raiz = balancear(raiz);
return raiz;
}
A seguir temos uma função para remover um nó da árvore. Assim como uma inserção, a remoção também pode desbalancear a árvore. Então, também precisamos verificar a necessidade de balanceamento da árvore após a remoção. A grande atenção aqui recai sobre as possibilidade de remoção: nó folha, nó com apenas um filho, ou nó com dois filhos.
/*
Função para remover um nó da Árvore binária
Pode ser necessário rebalancear a árvore e a raiz pode ser alterada
por isso precisamos retornar a raiz
*/
No* remover(No *raiz, int chave) {
if(raiz == NULL){
printf("Valor nao encontrado!\n");
return NULL;
} else { // procura o nó a remover
if(raiz->pessoa->cpf == chave) {
// remove nós folhas (nós sem filhos)
if(raiz->esquerdo == NULL && raiz->direito == NULL) {
free(raiz);
printf("Elemento folha removido: %d !\n", chave);
return NULL;
}
else{
// remover nós que possuem 2 filhos
if(raiz->esquerdo != NULL && raiz->direito != NULL){
No *aux = raiz->esquerdo;
while(aux->direito != NULL)
aux = aux->direito;
Pessoa *pessoaAux;
pessoaAux = raiz->pessoa;
raiz->pessoa = aux->pessoa;
aux->pessoa = pessoaAux;
printf("Elemento trocado: %d !\n", chave);
raiz->esquerdo = remover(raiz->esquerdo, chave);
return raiz;
}
else{
// remover nós que possuem apenas 1 filho
No *aux;
if(raiz->esquerdo != NULL)
aux = raiz->esquerdo;
else
aux = raiz->direito;
free(raiz);
printf("Elemento com 1 filho removido: %d !\n", chave);
return aux;
}
}
} else {
if(chave < raiz->pessoa->cpf)
raiz->esquerdo = remover(raiz->esquerdo, chave);
else
raiz->direito = remover(raiz->direito, chave);
}
raiz->altura = maior(alturaDoNo(raiz->esquerdo), alturaDoNo(raiz->direito)) + 1;
raiz = balancear(raiz);
return raiz;
}
}
Para testar se tudo está funcionando é interessante imprimir nossa árvore na tela. Para isso vamos usar dois procedimentos, um para imprimir uma Pessoa e outro que irá percorrer nossa árvore imprimindo a pessoa de cada nó.
// Imprime os dados de uma pessoa
void imprimirPessoa(Pessoa *pessoa){
printf("Nome: %s CPF: %d Idade: %d\n", pessoa->nome, pessoa->cpf, pessoa->idade);
}
// Percorre a árvore passando por todos os nós chamando a impressão da Pessoa
void imprimir(No *raiz, int nivel){
int i;
if(raiz){
imprimir(raiz->direito, nivel + 1);
printf("\n\n");
for(i = 0; i < nivel; i++)
printf("\t");
imprimirPessoa(raiz->pessoa);
imprimir(raiz->esquerdo, nivel + 1);
}
}
Bom, é isso. A seguir disponibilizo todo o código em sequência da nossa Árvore Binária Balanceada AVL de Pessoas, inclusive com a função main, para que você possa testar em seu computador. Deixo também a aula postada no canal no youtobe e conto com seu like e inscrição. Abraços e bons estudos.
Código completo da Árvore Binária Balanceada AVL de Pessoas
#include <stdio.h>
#include <stdlib.h>
typedef struct{
char nome[25];
int idade;
int cpf;
}Pessoa;
typedef struct no{
Pessoa *pessoa;
struct no *esquerdo, *direito;
short altura;
}No;
/*
Função que cria um novo nó
x -> valor a ser inserido no nó
Retorna: o endereço do nó criado
*/
No* novoNo(Pessoa *x){
No *novo = malloc(sizeof(No));
if(novo){
novo->pessoa = x;
novo->esquerdo = NULL;
novo->direito = NULL;
novo->altura = 0;
}
else
printf("\nERRO ao alocar nó em novoNo!\n");
return novo;
}
/*
Retorna o maior dentre dois valores
a, b -> altura de dois nós da árvore
*/
short maior(short a, short b){
return (a > b)? a: b;
}
// Retorna a altura de um nó ou -1 caso ele seja null
short alturaDoNo(No *no){
if(no == NULL)
return -1;
else
return no->altura;
}
// Calcula e retorna o fator de balanceamento de um nó
short fatorDeBalanceamento(No *no){
if(no)
return (alturaDoNo(no->esquerdo) - alturaDoNo(no->direito));
else
return 0;
}
// --------- ROTAÇÕES ---------------------------
// função para a rotação à esquerda
No* rotacaoEsquerda(No *r){
No *y, *f;
y = r->direito;
f = y->esquerdo;
y->esquerdo = r;
r->direito = f;
r->altura = maior(alturaDoNo(r->esquerdo), alturaDoNo(r->direito)) + 1;
y->altura = maior(alturaDoNo(y->esquerdo), alturaDoNo(y->direito)) + 1;
return y;
}
// função para a rotação à direita
No* rotacaoDireita(No *r){
No *y, *f;
y = r->esquerdo;
f = y->direito;
y->direito = r;
r->esquerdo = f;
r->altura = maior(alturaDoNo(r->esquerdo), alturaDoNo(r->direito)) + 1;
y->altura = maior(alturaDoNo(y->esquerdo), alturaDoNo(y->direito)) + 1;
return y;
}
No* rotacaoEsquerdaDireita(No *r){
r->esquerdo = rotacaoEsquerda(r->esquerdo);
return rotacaoDireita(r);
}
No* rotacaoDireitaEsquerda(No *r){
r->direito = rotacaoDireita(r->direito);
return rotacaoEsquerda(r);
}
/*
Função para realizar o balanceamento da árvore após uma inserção ou remoção
Recebe o nó que está desbanlanceado e retorna a nova raiz após o balanceamento
*/
No* balancear(No *raiz){
short fb = fatorDeBalanceamento(raiz);
// Rotação à esquerda
if(fb < -1 && fatorDeBalanceamento(raiz->direito) <= 0)
raiz = rotacaoEsquerda(raiz);
// Rotação à direita
else if(fb > 1 && fatorDeBalanceamento(raiz->esquerdo) >= 0)
raiz = rotacaoDireita(raiz);
// Rotação dupla à esquerda
else if(fb > 1 && fatorDeBalanceamento(raiz->esquerdo) < 0)
raiz = rotacaoEsquerdaDireita(raiz);
// Rotação dupla à direita
else if(fb < -1 && fatorDeBalanceamento(raiz->direito) > 0)
raiz = rotacaoDireitaEsquerda(raiz);
return raiz;
}
/*
Insere um novo nó na árvore
raiz -> raiz da árvore
x -> valor a ser inserido
Retorno: endereço do novo nó ou nova raiz após o balanceamento
*/
No* inserir(No *raiz, Pessoa *x){
if(raiz == NULL) // árvore vazia
return novoNo(x);
else{ // inserção será à esquerda ou à direita?
if(x->cpf < raiz->pessoa->cpf)
raiz->esquerdo = inserir(raiz->esquerdo, x);
else if(x->cpf > raiz->pessoa->cpf)
raiz->direito = inserir(raiz->direito, x);
else
printf("\nInsercao nao realizada!\nO elemento %d a existe!\n", x->cpf);
}
raiz->altura = maior(alturaDoNo(raiz->esquerdo), alturaDoNo(raiz->direito)) + 1;
raiz = balancear(raiz);
return raiz;
}
/*
Função para remover um nó da Árvore binária
Pode ser necessário rebalancear a árvore e a raiz pode ser alterada
por isso precisamos retornar a raiz
*/
No* remover(No *raiz, int chave) {
if(raiz == NULL){
printf("Valor nao encontrado!\n");
return NULL;
} else { // procura o nó a remover
if(raiz->pessoa->cpf == chave) {
// remove nós folhas (nós sem filhos)
if(raiz->esquerdo == NULL && raiz->direito == NULL) {
free(raiz);
printf("Elemento folha removido: %d !\n", chave);
return NULL;
}
else{
// remover nós que possuem 2 filhos
if(raiz->esquerdo != NULL && raiz->direito != NULL){
No *aux = raiz->esquerdo;
while(aux->direito != NULL)
aux = aux->direito;
Pessoa *pessoaAux;
pessoaAux = raiz->pessoa;
raiz->pessoa = aux->pessoa;
aux->pessoa = pessoaAux;
printf("Elemento trocado: %d !\n", chave);
raiz->esquerdo = remover(raiz->esquerdo, chave);
return raiz;
}
else{
// remover nós que possuem apenas 1 filho
No *aux;
if(raiz->esquerdo != NULL)
aux = raiz->esquerdo;
else
aux = raiz->direito;
free(raiz);
printf("Elemento com 1 filho removido: %d !\n", chave);
return aux;
}
}
} else {
if(chave < raiz->pessoa->cpf)
raiz->esquerdo = remover(raiz->esquerdo, chave);
else
raiz->direito = remover(raiz->direito, chave);
}
raiz->altura = maior(alturaDoNo(raiz->esquerdo), alturaDoNo(raiz->direito)) + 1;
raiz = balancear(raiz);
return raiz;
}
}
void imprimirPessoa(Pessoa *pessoa){
printf("Nome: %s CPF: %d Idade: %d\n", pessoa->nome, pessoa->cpf, pessoa->idade);
}
void imprimir(No *raiz, int nivel){
int i;
if(raiz){
imprimir(raiz->direito, nivel + 1);
printf("\n\n");
for(i = 0; i < nivel; i++)
printf("\t");
imprimirPessoa(raiz->pessoa);
imprimir(raiz->esquerdo, nivel + 1);
}
}
int main(){
int opcao, valor;
No *raiz = NULL;
Pessoa *p;
do{
printf("\n\n\t0 - Sair\n\t1 - Inserir\n\t2 - Remover\n\t3 - Imprimir\n\n");
scanf("%d", &opcao);
switch(opcao){
case 0:
printf("Saindo!!!");
break;
case 1:
p = malloc(sizeof(Pessoa));
printf("\tDigite o nome: ");
scanf("%s", p->nome);
printf("Digite o CPF e a Idade: ");
scanf("%d%d", &p->cpf, &p->idade);
raiz = inserir(raiz, p);
break;
case 2:
printf("\tDigite o CPF a ser removido: ");
scanf("%d", &valor);
raiz = remover(raiz, valor);
break;
case 3:
imprimir(raiz, 1);
break;
default:
printf("\nOcao invalida!!!\n");
}
}while(opcao != 0);
return 0;
}
