Árvore AVL
Origem: Wikipédia, a enciclopédia livre.
Árvore AVL (ou árvore balanceada pela altura), em Ciência da Computação, é uma árvore de busca binária auto-balanceada. Em tal árvore, a altura de dois nós folha difere no máximo em uma unidade. As operações de busca, inserção e eliminação de elementos possuem complexidade O(logn) (no qual n é o número de elementos da árvore). Inserções e eliminações podem também requerer o rebalanceamento da árvore, exigindo uma ou mais rotações.
O nome AVL vem de seus criadores Adelson Velsky e Landis, cuja primeira referência encontra-se no documento "Algoritmos para organização da informação" de 1962.
Índice |
[editar] Características
[editar] Balanceamento
Uma árvore AVL é dita balanceada quando, para cada nó da árvore, a diferença entre as alturas das suas sub-árvores (direita e esquerda) não é maior do que um. Caso a árvore não estiver balanceada é necessário seu balanceamento através da rotação simples ou rotação dupla. O balanceamento é requerido para as operações de adição e exclusão de elementos. Para definir o balanceamento é utilizado um fator específico para nós.
O fator de balanceamento de um nó é dado pelo seu peso em relação a sua sub-árvore. Um nó com fator balanceado pode conter 1, 0, ou -1 em seu fator. Um nó com fator de balanceamento -2 ou 2 é considerado um árvore não-AVL e requer um balanceamento por rotação ou dupla-rotação.
[editar] Operações
[editar] Inserção
Inserção em uma árvore AVL deve ser dada pela inserção do nodo seguida de uma verificação na propriedade do fator de balanceamento. Caso não obedeça a essa propriedade, deve-se fazer uma rotação conveniente.
[editar] Remoção
A remoção deve ser dada por uma rotação em torno do nó a ser removido, a fim de torná-lo folha para que então possa ser removido. Em alguns casos, após a remoção são necessárias rotações para ajustar o fator de balanceamento.
[editar] Pesquisa
O número de comparações para localizar um elemento em AVL é aproximadamente 1.44 log2 n no pior caso.
[editar] Rotação
A operação básica em uma árvore AVL geralmente envolve os mesmos algoritmos de uma árvore de busca binária desbalanceada. A rotação na árvore AVL ocorre devido ao seu desbalanceamento, uma rotação simples ocorre quando um nó está desbalanceado e seu filho estiver no mesmo sentido da inclinação, formando uma linha reta. Uma rotação-dupla ocorre quando um nó estiver desbalanceado e seu filho estiver inclinado no sentido inverso ao pai, formando um "joelho".
[editar] Rotação à esquerda
Em uma árvore binária, basta empurrar o nodo N para baixo e para a esquerda. O filho à direita de N o substitui, e o filho à esquerda do filho à direita vem a ser o novo filho à direita de N. Segue pseudocódigo:
Seja Y o filho à direita de XTorne X filho à esquerda de YTorne o filho à esquerda de Y o filho à direita de X.
[editar] Rotação à direita
Numa árvore binária basta empurrar o nodo N para baixo e para a direita. O filho à esquerda de N o substitui, e o filho à direita do filho à esquerda vem a ser o novo filho à esquerda de N. Segue pseudocódigo:
Seja Y o filho à esquerda de XTroque X por YTorne o filho à direita de Y o filho à esquerda de X.
É interessante observar que as rotações duplas nada mais são que duas rotações simples seguidas, independentes se à direita ou à esquerda.
[editar] Código em C
#include <stdio.h> #include <conio.h> #include <stdlib.h> struct elemento { int numero; int fator; struct elemento *fesq, *fdir; }; //------------------------------------------------------------------------------ struct elemento *rotaciona_esq(struct elemento *pai){ struct elemento *corrente; corrente = pai->fesq; pai->fesq = corrente->fdir; corrente->fdir = pai; return corrente; } //------------------------------------------------------------------------------ struct elemento *rotaciona_dir(struct elemento *pai){ struct elemento *corrente; corrente = pai->fdir; pai->fdir = corrente->fesq; corrente->fesq = pai; return corrente; } //------------------------------------------------------------------------------ struct elemento *insere(int num, struct elemento *arv){ struct elemento *novo, *aux = NULL; int fatorequi; aux = arv; if(arv == NULL){ novo = (struct elemento *)malloc(sizeof(struct elemento)); novo->numero = num; novo->fesq = NULL; novo->fdir = NULL; novo->fator = 0; printf("\nO numero foi inserido com sucesso na arvore!\n\n"); system("pause"); return novo; } else{ if(num == arv->numero){ printf("\nO numero ja existe na arvore!\n\n"); system("pause"); return aux; } else if(num > arv->numero){ if(arv->fdir != NULL) fatorequi = arv->fdir->fator; arv->fdir = insere(num,arv->fdir); if(((arv->fdir->fdir == NULL) && (arv->fdir->fesq == NULL)) || (fatorequi == 0 && arv->fdir->fator == -1) || (fatorequi == 0 && arv->fdir->fator == 1)) arv->fator++; // 1° Regra if((arv->fator == 2) && (arv->fdir->fator == 1)){ aux = rotaciona_dir(arv); aux->fator = 0; aux->fesq->fator = 0; return aux; } // 2° Regra if((arv->fator == 2) && (arv->fdir->fator == -1)){ aux = rotaciona_esq(arv->fdir); arv->fdir = aux; aux = rotaciona_dir(arv); if(aux->fator == 1){ printf("ok\n"); aux->fesq->fator = -1; aux->fdir->fator = 0; } if(aux->fator == -1){ aux->fesq->fator = 0; aux->fdir->fator = -1; } if(aux->fator == 0){ aux->fesq->fator = 0; aux->fdir->fator = 0; } aux->fator = 0; return aux; } } else if(num < arv->numero){ if(arv->fesq != NULL) fatorequi = arv->fesq->fator; arv->fesq = insere(num,arv->fesq); if(((arv->fesq->fesq == NULL) && (arv->fesq->fdir == NULL)) || (fatorequi == 0 && arv->fesq->fator == -1) || (fatorequi == 0 && arv->fesq->fator == 1)) arv->fator--; // 1° Regra if((arv->fator == -2) && (arv->fesq->fator == -1)){ aux = rotaciona_esq(arv); aux->fator = 0; aux->fdir->fator = 0; return aux; } // 2° Regra if((arv->fator == -2) && (arv->fesq->fator == 1)){ aux = rotaciona_dir(arv->fesq); arv->fesq = aux; aux = rotaciona_esq(arv); if(aux->fator == 1){ aux->fdir->fator = 0; aux->fesq->fator = -1; } if(aux->fator == -1){ aux->fdir->fator = -1; aux->fesq->fator = 0; } if(aux->fator == 0){ aux->fdir->fator = 0; aux->fesq->fator = 0; } aux->fator = 0; return aux; } } } return arv; } //------------------------------------------------------------------------------ void mostra(struct elemento *arv, int nivel){ int i; if(arv){ for(i = 0; i < nivel; i++) printf(". "); printf("%d [%d]\n",arv->numero,arv->fator); mostra(arv->fesq,nivel+1); mostra(arv->fdir,nivel+1); } } //------------------------------------------------------------------------------ main(void){ int opcao, num; struct elemento *arv = NULL; while(opcao != 0){ system("cls"); printf("-----------------------------------------------\n"); printf("|# # # # # # # # # # # # # # # # # # # # # # #|\n"); printf("|# ----------------------------------------- #|\n"); printf("|#| 1 - Inserir valor na ABP |#|\n"); printf("|#| 2 - Mostrar ABP |#|\n"); printf("|# ----------------------------------------- #|\n"); printf("|# # # # # # # # # # # # # # # # # # # # # # #|\n"); printf("-----------------------------------------------\n"); printf("Opcao: "); scanf("%d",&opcao); if(opcao == 1){ printf("\nDigite o numero a ser inserido: "); scanf("%d",&num); arv = insere(num,arv); } if(opcao == 2){ printf("\n"); mostra(arv,0); if(arv == NULL) printf("\nArvore vazia!!!\n"); printf("\n\n"); system("pause"); printf("\n"); } } getch(); }
[editar] Ver também
[editar] Bibliografia
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7.
