Árvores AVL: Rotações, Inserção, Exclusão com C++ Exemplo
Sarah Chen
O que são árvores AVL?
Árvores AVL são árvores de pesquisa binária nas quais a diferença entre a altura da subárvore esquerda e direita é -1, 0 ou +1.
As árvores AVL também são chamadas de árvore de pesquisa binária com autoequilíbrio. Essas árvores ajudam a manter o tempo de busca logarítmico. É nomeado após seus inventores (AVL) Adelson, Velsky e Landis.
Como funciona a árvore AVL?
Para entender melhor a necessidade de árvores AVL, vejamos algumas desvantagens das árvores de pesquisa binária simples.
Considere as seguintes chaves inseridas na ordem especificada na árvore de pesquisa binária.
A altura da árvore aumenta linearmente quando inserimos as chaves em ordem crescente de valor. Assim, a operação de busca, na pior das hipóteses, leva O(n).
Leva tempo linear para procurar um elemento; portanto, não adianta usar o Árvore de pesquisa binária estrutura. Por outro lado, se a altura da árvore estiver equilibrada, conseguimos um melhor tempo de busca.
Vejamos agora as mesmas chaves, mas inseridas em uma ordem diferente.
Aqui as chaves são iguais, mas como são inseridas em uma ordem diferente, assumem posições diferentes e a altura da árvore permanece equilibrada. Portanto, a pesquisa não levará mais do que O(log n) para qualquer elemento da árvore. Agora é evidente que se a inserção for feita corretamente, a altura da árvore pode ser mantida equilibrada.
Nas árvores AVL, verificamos a altura da árvore durante a operação de inserção. Modificações são feitas para manter a altura equilibrada sem violar as propriedades fundamentais da Árvore de Pesquisa Binária.
Fator de equilíbrio em árvores AVL
O fator de equilíbrio (BF) é um atributo fundamental de cada nó nas árvores AVL que ajuda a monitorar a altura da árvore.
Propriedades do fator de equilíbrio
- O fator de equilíbrio é conhecido como a diferença entre a altura da subárvore esquerda e da subárvore direita.
- Fator de equilíbrio (nó) = altura (nó-> esquerda) – altura (nó-> direita)
- Os valores permitidos de BF são –1, 0 e +1.
- O valor –1 indica que a subárvore direita contém um extra, ou seja, a árvore é pesada para a direita.
- O valor +1 indica que a subárvore esquerda contém um extra, ou seja, a árvore fica pesada.
- O valor 0 mostra que a árvore inclui nós iguais em cada lado, ou seja, a árvore está perfeitamente balanceada.
Rotações AVL
Para fazer com que a árvore AVL se equilibre, ao inserir ou excluir um nó da árvore, são realizadas rotações.
Realizamos a seguinte rotação LL, rotação RR, rotação LR e rotação RL.
- Esquerda – Rotação Esquerda
- Direita – Rotação Direita
- Direita – Rotação Esquerda
- Esquerda – Rotação Direita
Esquerda – Rotação Esquerda
Esta rotação é realizada quando um novo nó é inserido no filho esquerdo da subárvore esquerda.
Uma única rotação para a direita é executada. Este tipo de rotação é identificado quando um nó tem um fator de equilíbrio igual a +2, e seu filho esquerdo tem um fator de equilíbrio igual a +1.
Direita – Rotação Direita
Esta rotação é realizada quando um novo nó é inserido no filho direito da subárvore direita.
Uma única rotação para a esquerda é executada. Este tipo de rotação é identificado quando um nó possui um fator de equilíbrio como -2, e seu filho direito possui um fator de equilíbrio como -1.
Direita – Rotação Esquerda
Esta rotação é realizada quando um novo nó é inserido no filho direito da subárvore esquerda.
Esta rotação é realizada quando um nó tem um fator de equilíbrio como –2 e seu filho direito tem um fator de equilíbrio como +1.
Esquerda – Rotação Direita
Esta rotação é realizada quando um novo nó é inserido no filho esquerdo da subárvore direita.
Essa rotação é realizada quando um nó tem um fator de equilíbrio igual a +2 e seu filho esquerdo tem um fator de equilíbrio igual a -1.
Inserção em árvores AVL
A operação de inserção é quase a mesma que nas árvores de pesquisa binária simples. Após cada inserção, equilibramos a altura da árvore. A operação de inserção leva O (log n) a pior complexidade de tempo.
Etapa 1: Insira o nó na árvore AVL usando o mesmo algoritmo de inserção do BST. No exemplo acima, insira 160.
Etapa 2: depois que o nó é adicionado, o fator de equilíbrio de cada nó é atualizado. Após a inserção de 160, o fator de equilíbrio de cada nó é atualizado.
Etapa 3: Agora verifique se algum nó viola o intervalo do fator de equilíbrio se o fator de equilíbrio for violado e, em seguida, execute rotações usando o caso abaixo. No exemplo acima, o fator de equilíbrio 350 é violado e o caso 1 passa a ser aplicável ali, realizamos a rotação LL e a árvore é balanceada novamente.
- Se BF(nó) = +2 e BF(nó -> filho esquerdo) = +1, execute a rotação LL.
- Se BF(nó) = -2 e BF(nó -> filho direito) = 1, execute a rotação RR.
- Se BF(nó) = -2 e BF(nó -> filho direito) = +1, execute a rotação RL.
- Se BF(nó) = +2 e BF(nó -> filho esquerdo) = -1, execute a rotação LR.
Exclusão em árvores AVL
A exclusão também é muito simples. Excluímos usando a mesma lógica das árvores de pesquisa binária simples. Após a exclusão, reestruturamos a árvore, se necessário, para manter sua altura equilibrada.
- Encontre o elemento na árvore.
- Exclua o nó, conforme a exclusão do BST.
- Dois casos são possíveis: -
Caso 1: Excluindo da subárvore direita.
- 1A. Se BF(nó) = +2 e BF(nó -> filho esquerdo) = +1, execute a rotação LL.
- 1B. Se BF(nó) = +2 e BF(nó -> filho esquerdo) = -1, execute a rotação LR.
- 1C. Se BF(nó) = +2 e BF(nó -> filho esquerdo) = 0, execute a rotação LL.
Caso 2: Excluindo da subárvore esquerda.
- 2A. Se BF(nó) = -2 e BF(nó -> filho direito) = -1, execute a rotação RR.
- 2B. Se BF(nó) = -2 e BF(nó -> filho direito) = +1, execute a rotação RL.
- 2C. Se BF(nó) = -2 e BF(nó -> filho direito) = 0, execute a rotação RR.
C++ Exemplo de árvores AVL
Abaixo está o C++ que implementa árvores AVL:
#include <iostream>
#include <queue>
#include <unordered_map>
using namespace std;
struct node {
struct node *left;
int data;
int height;
struct node *right;
};
class AVL
{
private:
public:
struct node * root;
AVL(){
this->root = NULL;
}
int calheight(struct node *p){
if(p->left && p->right){
if (p->left->height < p->right->height)
return p->right->height + 1;
else return p->left->height + 1;
}
else if(p->left && p->right == NULL){
return p->left->height + 1;
}
else if(p->left ==NULL && p->right){
return p->right->height + 1;
}
return 0;
}
int bf(struct node *n){
if(n->left && n->right){
return n->left->height - n->right->height;
}
else if(n->left && n->right == NULL){
return n->left->height;
}
else if(n->left== NULL && n->right ){
return -n->right->height;
}
}
struct node * llrotation(struct node *n){
struct node *p;
struct node *tp;
p = n;
tp = p->left;
p->left = tp->right;
tp->right = p;
return tp;
}
struct node * rrrotation(struct node *n){
struct node *p;
struct node *tp;
p = n;
tp = p->right;
p->right = tp->left;
tp->left = p;
return tp;
}
struct node * rlrotation(struct node *n){
struct node *p;
struct node *tp;
struct node *tp2;
p = n;
tp = p->right;
tp2 =p->right->left;
p -> right = tp2->left;
tp ->left = tp2->right;
tp2 ->left = p;
tp2->right = tp;
return tp2;
}
struct node * lrrotation(struct node *n){
struct node *p;
struct node *tp;
struct node *tp2;
p = n;
tp = p->left;
tp2 =p->left->right;
p -> left = tp2->right;
tp ->right = tp2->left;
tp2 ->right = p;
tp2->left = tp;
return tp2;
}
struct node* insert(struct node *r,int data){
if(r==NULL){
struct node *n;
n = new struct node;
n->data = data;
r = n;
r->left = r->right = NULL;
r->height = 1;
return r;
}
else{
if(data < r->data)
r->left = insert(r->left,data);
else
r->right = insert(r->right,data);
}
r->height = calheight(r);
if(bf(r)==2 && bf(r->left)==1){
r = llrotation(r);
}
else if(bf(r)==-2 && bf(r->right)==-1){
r = rrrotation(r);
}
else if(bf(r)==-2 && bf(r->right)==1){
r = rlrotation(r);
}
else if(bf(r)==2 && bf(r->left)==-1){
r = lrrotation(r);
}
return r;
}
void levelorder_newline(){
if (this->root == NULL){
cout<<"\n"<<"Empty tree"<<"\n";
return;
}
levelorder_newline(this->root);
}
void levelorder_newline(struct node *v){
queue <struct node *> q;
struct node *cur;
q.push(v);
q.push(NULL);
while(!q.empty()){
cur = q.front();
q.pop();
if(cur == NULL && q.size()!=0){
cout<<"\n";
q.push(NULL);
continue;
}
if(cur!=NULL){
cout<<" "<<cur->data;
if (cur->left!=NULL){
q.push(cur->left);
}
if (cur->right!=NULL){
q.push(cur->right);
}
}
}
}
struct node * deleteNode(struct node *p,int data){
if(p->left == NULL && p->right == NULL){
if(p==this->root)
this->root = NULL;
delete p;
return NULL;
}
struct node *t;
struct node *q;
if(p->data < data){
p->right = deleteNode(p->right,data);
}
else if(p->data > data){
p->left = deleteNode(p->left,data);
}
else{
if(p->left != NULL){
q = inpre(p->left);
p->data = q->data;
p->left=deleteNode(p->left,q->data);
}
else{
q = insuc(p->right);
p->data = q->data;
p->right = deleteNode(p->right,q->data);
}
}
if(bf(p)==2 && bf(p->left)==1){ p = llrotation(p); }
else if(bf(p)==2 && bf(p->left)==-1){ p = lrrotation(p); }
else if(bf(p)==2 && bf(p->left)==0){ p = llrotation(p); }
else if(bf(p)==-2 && bf(p->right)==-1){ p = rrrotation(p); }
else if(bf(p)==-2 && bf(p->right)==1){ p = rlrotation(p); }
else if(bf(p)==-2 && bf(p->right)==0){ p = llrotation(p); }
return p;
}
struct node* inpre(struct node* p){
while(p->right!=NULL)
p = p->right;
return p;
}
struct node* insuc(struct node* p){
while(p->left!=NULL)
p = p->left;
return p;
}
~AVL(){
}
};
int main(){
AVL b;
int c,x;
do{
cout<<"\n1.Display levelorder on newline";
cout<<"\n2.Insert";
cout<<"\n3.Delete\n";
cout<<"\n0.Exit\n";
cout<<"\nChoice: ";
cin>>c;
switch (c)
{
case 1:
b.levelorder_newline();
// to print the tree in level order
break;
case 2:
cout<<"\nEnter no. ";
cin>>x;
b.root = b.insert(b.root,x);
break;
case 3:
cout<<"\nWhat to delete? ";
cin>>x;
b.root = b.deleteNode(b.root,x);
break;
case 0:
break;
}
} while(c!=0);
}
Exemplo de execução do código acima:
- Copie o código acima e cole “avl.cpp”.
- Compile o código:
g++ avl.cpp -o run
- Execute o código.
./run
Vantagens das árvores AVL
- A altura da árvore AVL está sempre equilibrada. A altura nunca ultrapassa o log N, onde N é o número total de nós na árvore.
- Oferece melhor complexidade de tempo de pesquisa quando comparado a árvores de pesquisa binária simples.
- As árvores AVL possuem recursos de autoequilíbrio.
Resumo
- As árvores AVL são árvores de pesquisa binária com autoequilíbrio.
- O fator de equilíbrio é o atributo fundamental das árvores AVL
- O fator de equilíbrio de um nó é definido como a diferença entre a altura das subárvores esquerda e direita desse nó.
- Os valores válidos do fator de equilíbrio são -1, 0 e +1.
- A operação de inserção e exclusão exige que as rotações sejam executadas após a violação do fator de equilíbrio.
- A complexidade de tempo da operação de inserção, exclusão e pesquisa é O (log N).
- As árvores AVL seguem todas as propriedades das árvores de pesquisa binária.
- A subárvore esquerda possui nós menores que o nó raiz. A subárvore direita possui nós que são sempre maiores que o nó raiz.
- As árvores AVL são usadas onde a operação de pesquisa é mais frequente em comparação com as operações de inserção e exclusão.
