Olhando os trabalhos que realizei na faculdade. Encontrei uma AVL desenvolvida para a cadeira de estutura de dados. Implementei utilizando como interface gráfica NCURSES, para mostrar a árvore.
Irei compartilhar o código. Com certeza será bastante util para quem está estudando.
Este código tem alguns conceitos interessantes como:
- Não utiliza variáveis globais
- Os dados são inseridos na árvore quando ficar desbalanceada é informado e solicitado ao usuário se deseja balancear a árvore
- Informe como a árvore esta desbalanceada em quatro casos: EE,ED,DD e DE
- Calcula a altura da árvore
- Menu em Ncurses
- Visualização da árvore com Ncurses
/*
* Nome: Marlon Luis Petry
* Description: AVL
compilacao
gcc "Avl-Marlon.c" -o "Avl-Marlon" -g -lncurses -w
Data: 20/10/2005
* This program is free software; you can redistribute it and/or modify
* it under the terms of the GNU General Public License as published by
* the Free Software Foundation; either version 2 of the License, or
* (at your option) any later version.
*
* This program is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with this program; if not, write to the Free Software
* Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
*/
#include
#include
#include
#include
#define CENTERX COLS/2
#define CENTERY LINES/2
#define DIST 5
typedef char string[50];
typedef struct t {
string info;
int alt;
struct t *pai;
struct t *left;
struct t *right;
}tree;
int tipoBal = -1;
string bal[4] = {”Caso EE”,”Caso ED”,”Caso DD”,”Caso DE”};
tree *bal_esq(tree *aux);
tree *bal_dir(tree *aux);
tree *rotacaoRR(tree *aux);
tree *rotacaoLL(tree *aux);
tree *rotacaoLR(tree *aux);
tree *rotacaoRL(tree *aux);
tree *insere(tree **root, string info, int h) {
char ch;
tree *aux;
if (*root == NULL)
{
aux = (tree *) malloc(sizeof(tree));
strcpy(aux->info,info);
aux->left = NULL;
aux->right = NULL;
aux->pai = NULL;
aux->alt = 0;
h = 1;
*root = aux;
}
else
{
if (strcmp(info,(*root)->info) < 0)
{
insere(&(*root)->left, info, h);
//Atualiza PAI do nó inserido
if ((*root)->left->pai == NULL)
(*root)->left->pai = *root;
if (h)
switch((*root)->alt)
{
//Estava mais alto à direita e inseriur mais um nó à esquerda
case -1:
(*root)->alt = 0;
h = 0; //Não propaga os ajustes nos fatores de balanceamento
break;
case 0:
(*root)->alt = 1; //o lado esquerdo fica maior e os fatores de
//balanceamento acima deverao ser ajustados
break;
case 1:
mvprintw(8,10,”Arvore Desbalaceou a esquerda A = %s Y = %s”,(*root)->info,info);
mvprintw(9,10,”Baleancear (S)im (N)nao: “);
scanw(”%c”,&ch);
if(ch == ‘S’ || ch == ’s’)
{
*root = bal_esq(*root); //FB == 2 -> retorna a sub-árvore balanceada
h = 0; //não propaga a atualização dos fatores de
} //balanceamento
break;
}
}
else
{
insere(&(*root)->right, info, h);
//Atualiza PAI do nó inserido
if ((*root)->right->pai != NULL)
(*root)->right->pai = *root;
if (h)
switch ((*root)->alt)
{
//estava mais alto à esquerda e inseriu mais um nó à direita
case 1:
(*root)->alt = 0;
h = 0; //não propaga os ajustes nos fatores de balanceamneto
break;
case 0:
(*root)->alt = -1; // o lado direito fica maior do que o esquerdo e
// o ajuste deve ser propagado
break;
case -1:
//FB == -2 -> retorna a sub-árvore balanceada
mvprintw(8,10,”Arvore Desbalaceou a direita A = %s Y = %s”,(*root)->info,info);
refresh();
mvprintw(9,10,”Baleancear (S)im (N)nao: “);
scanw(”%c”,&ch);
if(ch == ‘S’ || ch == ’s’)
{
*root = bal_dir(*root);
h = 0; //não propaga a atualização dos fatores de
} //balanceamento
break;
}
}
}
return(*root);
}
tree *bal_esq(tree *aux)
{
tree *p;
p = aux->left;
if (p->alt == 1)
{ //sinais iguais e positivo
tipoBal = 1;
aux = rotacaoLL(aux);
}
else
{
tipoBal = 2;
aux = rotacaoLR(aux); //sinais diferentes
}
aux->alt = 0;
return(aux);
}
/*
* O novo nó foi inserido à direita. Ocorreu desbalanceamento (fb == 2)
*/
tree *bal_dir(tree *aux)
{
tree *p;
p = aux->right;
if (p->alt == -1) //Sinais iguais e negativo
{
tipoBal = 3;
aux = rotacaoRR(aux);
}
else
{
tipoBal = 4;
aux = rotacaoRL(aux); //Sinais diferentes
}
aux->alt = 0;
refresh();
return(aux);
}
//rotacoes
tree *rotacaoRR(tree *aux) {
tree *p;
p = aux->right;
aux->right = p->left;
if (p->left != NULL)
p->left->pai = aux;
p->left = aux;
p->pai = aux->pai;
aux->pai = p;
aux->alt = 0;
return(p);
}
tree *rotacaoLL(tree *aux) {
tree *p;
p = aux->left;
aux->left = p->right;
if (p->right != NULL)
p->right->pai = aux;
p->right = aux;
p->pai = aux->pai;
aux->pai = p;
aux->alt = 0;
return(p);
}
tree *rotacaoLR(tree *aux) {
tree *pai; //ponteiro para depois atualizar o pai após a rotação
tree *no_left; //ponteiro para o filho esquerdo para atualizar o FB após a rotação
tree *novo_no; //ponteiro à ser retornado
int FB_fright; //fator de balanceamento do no à direita do filho esquerdo
pai = aux->pai;
no_left = aux->left;
FB_fright = no_left->right->alt;
aux->left = rotacaoRR(no_left);
novo_no = rotacaoLL(aux);
novo_no->pai = pai;
aux->alt = (FB_fright == 1)?-1:0; //Atualiza FB do nó rotacionado
no_left->alt = (FB_fright == -1)?1:0; // Atualiza FB do nó à esquerda do nó rotacionado
return(novo_no);
}
/*
* Atualização do FB e balanceamento para a raÃz esquerda
*/
tree *balanceamento_esquerdo(tree *no, int h) {
tree *f_dir;
int fb_dir;
switch (no->alt) {
case 1:
no->alt = 0;
break;
case 0:
no->alt = -1;
h = 1;
break;
case -1:
f_dir = no->right;
fb_dir = f_dir->alt;
if (fb_dir <= 0) {
f_dir = rotacaoRR(no);
if (fb_dir == 0) {
no->alt = -1;
f_dir->alt = 1;
h = 0;
}
else {
no->alt = 0;
f_dir->alt = 0;
}
no = f_dir;
}
else {
no = rotacaoRL(no);
no->alt = 0;
}
}
return(no);
}
/*
* Atualização do FB e balanceamento para a raiz direita
*/
tree *balanceamento_direito(tree *no, int h) {
tree *f_esq;
int alt_esq;
switch (no->alt) {
case -1:
no->alt = 0;
break;
case 0:
no->alt = 1;
h = 0;
break;
case 1:
f_esq = no->left;
alt_esq = f_esq->alt;
if (alt_esq >= 0) {
f_esq = rotacaoLL(no);
if (alt_esq == 0) {
no->alt = 1;
f_esq->alt = -1;
h = 0;
}
else {
no->alt = 0;
f_esq->alt = 0;
}
no = f_esq;
}
else {
no = rotacaoLR(no);
no->alt = 0;
}
}
return(no);
}
/*
* Busca nó substituto e realizada a remoção (busca o mais à direita do nó esquerdo
*/
tree *busca_remove(tree *no, tree *no_chave, int h) {
tree *no_removido;
if (no->right != NULL) {
no->right = busca_remove(no->right, no_chave, h);
if (h)
no = balanceamento_direito(no, h);
}
else {
strcpy(no_chave->info,no->info);
no_removido = no;
no = no->left;
if (no != NULL)
no->pai = no_removido->pai;
h = 1; //Deve propagar a atualização dos FB
free(no_removido);
}
return(no);
}
/*
* Remoção da Ãrvore AVL
*/
tree *removeTree(tree **raiz, int info, int h) {
if (*raiz == NULL) {
printf(”Chave não localizada !”);
h = 0;
}
else {
if (strcmp((*raiz)->info, info) > 0)
{
removeTree(&(*raiz)->left, info, h);
if (h)
*raiz = balanceamento_esquerdo(*raiz, h);
}
else if (strcmp((*raiz)->info , info) < 0)
{
removeTree(&(*raiz)->right, info, h);
if (h)
*raiz = balanceamento_direito(*raiz,h);
}
else { //Encontrou o elemento a ser removido
if ((*raiz)->right == NULL) {
if ((*raiz)->left != NULL) //Escolhe o nó à esquerda como substituto
(*raiz)->left->pai = (*raiz)->pai;
*raiz = (*raiz)->left;
h = 1;
}
else
if ((*raiz)->left == NULL) {
if ((*raiz)->right != NULL) //Escolhe o nó à direita como substituto
(*raiz)->right->pai = (*raiz)->pai;
*raiz = (*raiz)->right;
h = 1;
}
else { // Busca o elemento mais à direita do nó esquerdo
(*raiz)->left = busca_remove((*raiz)->left, *raiz, h);
//Se necessário efetua balanceamento (Esquerdo pois a função
//busca_remove foi para o nó esquerdo)
if (h)
*raiz = balanceamento_esquerdo(*raiz, h);
}
}
}
return(raiz);
}
tree *rotacaoRL(tree *aux) {
tree *pai; //ponteiro para depois atualizar o pai após a rotação
tree *no_right; //ponteiro para o filho direito para atualizar o FB após a rotação
tree *novo_no; //ponteiro à ser retornado
int FB_fleft; //fator de balanceamento do no à esquerda do filho direito
pai = aux->pai;
no_right = aux->right;
FB_fleft = no_right->left->alt;
aux->right = rotacaoLL(no_right);
novo_no = rotacaoRR(aux);
novo_no->pai = pai;
aux->alt = (FB_fleft == -1)?1:0; //Atualiza FB do nó rotacionado
no_right->alt = (FB_fleft == 1)?-1:0; // Atualiza FB do nó à direita do nó rotacionado
return(novo_no);
}
int maxDepth(tree *node) {
if (node==NULL) {
return(0);
}
else {
int lDepth = maxDepth(node->left);
int rDepth = maxDepth(node->right);
if (lDepth > rDepth) return(lDepth+1);
else return(rDepth+1);
}
}
//print
int print(tree *r,int x, int y)
{
int TotalWidth = width(r)*DIST;
int centerWidth = (x + TotalWidth/2);
int tamStr;
int d = 0;
//int centerWidthLinen= centerWidth +20;
char t;
if(r != NULL)
{
int leftWidth = width(r->left) * DIST;
int rigtWidth = width(r->right) * DIST;
tamStr = strlen(r->info);
mvprintw(y + (DIST/20),(centerWidth -1- (tamStr/2)),”%s”, r->info);
if (r->left != NULL)
{
int leftX = print(r->left, x , y + DIST);
}
if (r->right != NULL)
{
int rightX = print(r->right, x + leftWidth, y + DIST);
}
}
return centerWidth;
}
int width(tree *root)
{
if(root == NULL)
return 1;
else if(root->left == NULL && root->right == NULL)
return 1;
else
return width(root->left) + width(root->right);
}
main()
{
tree *root = NULL;
char ch;
string msg;
string info;
int opt;
int d=0;
initscr();
bkgd(COLOR_PAIR(4));
strcpy(msg,”Pressione Qualquer Tecla”);
while(1)
{
clear();
mvprintw(1,10,”%s”,”(1) - Inserir novo valor “);
mvprintw(2,10,”%s”,”(2) - Mostrar”);
mvprintw(3,10,”%s”,”(3) - Remove”);
mvprintw(4,10,”%s”,”(4) - Altura”);
mvprintw(5,10,”%s”,”(5) - Sair”);
mvprintw(6,10,”[ ]“);
move(6,11);
scanw(”%d”,&opt);
refresh();
switch(opt)
{
mvprintw(10,10,”%d”,opt);
case 1:
mvprintw(7,10,”%s”,”Informe Valor: “);
refresh();
getstr(info);
insere(&root,info,1);
break;
case 2:
clear();
print(root,CENTERX,0);
mvprintw(LINES -2,CENTERX,”%s”,bal[tipoBal]);
tipoBal = -1;
mvprintw(LINES -1,CENTERX,”%s”,msg);
getch();
break;
case 3:
mvprintw(7,10,”%s”,”Informe Valor: “);
refresh();
getstr(info);
removeTree(&root,info,1);
break;
case 4:
//mvprintw(LINES - 1,CENTERX,”%s”,”f para sair “);
mvprintw(7,10,”%s”,”Nivel”);
refresh();
d = maxDepth(root);
mvprintw(8,10,”%d”,d);
refresh();
break;
case 5:
//mvprintw(LINES - 1,CENTERX,”%s”,”f para sair “);
ch = ‘f’;
break;
}
refresh();
if(ch == ‘f’)
break;
}
endwin();
}
Não se esqueça este código é GPL pode ser usado desde que mantido os direitos autorais.
Assinem os FEEDS é de graça. Só essa semana 
