Árboles AVL: rotaciones, inserción, eliminación con C++ Ejemplo
sarah chen
¿Qué son los árboles AVL?
Árboles AVL son árboles de búsqueda binarios en los que la diferencia entre la altura del subárbol izquierdo y derecho es -1, 0 o +1.
Los árboles AVL también se denominan árboles de búsqueda binarios autoequilibrados. Estos árboles ayudan a mantener el tiempo de búsqueda logarítmico. Lleva el nombre de sus inventores (AVL) Adelson, Velsky y Landis.
¿Cómo funciona el árbol AVL?
Para comprender mejor la necesidad de los árboles AVL, veamos algunas desventajas de los árboles de búsqueda binarios simples.
Considere las siguientes claves insertadas en el orden dado en el árbol de búsqueda binaria.
La altura del árbol crece linealmente a medida que introducimos las claves en orden creciente de valor. Por lo tanto, la operación de búsqueda, en el peor de los casos, tarda O(n).
Se necesita tiempo lineal para buscar un elemento; por lo tanto, no sirve de nada utilizar el Árbol de búsqueda binaria Estructura. Por otro lado, si la altura del árbol está equilibrada, obtenemos un mejor tiempo de búsqueda.
Veamos ahora las mismas claves pero insertadas en un orden diferente.
Aquí las llaves son las mismas, pero como se insertan en diferente orden, toman posiciones diferentes y la altura del árbol permanece equilibrada. Por lo tanto, la búsqueda no tomará más de O(log n) para ningún elemento del árbol. Ahora es evidente que si la inserción se realiza correctamente, la altura del árbol se puede mantener equilibrada.
En los árboles AVL, controlamos la altura del árbol durante la operación de inserción. Se realizan modificaciones para mantener la altura equilibrada sin violar las propiedades fundamentales del árbol de búsqueda binaria.
Factor de equilibrio en árboles AVL
El factor de equilibrio (BF) es un atributo fundamental de cada nodo en los árboles AVL que ayuda a monitorear la altura del árbol.
Propiedades del factor de equilibrio
- El factor de equilibrio se conoce como la diferencia entre la altura del subárbol izquierdo y el subárbol derecho.
- Factor de equilibrio (nodo) = altura (nodo->izquierda) – altura (nodo->derecha)
- Los valores permitidos de BF son –1, 0 y +1.
- El valor –1 indica que el subárbol derecho contiene uno adicional, es decir, el árbol tiene el peso correcto.
- El valor +1 indica que el subárbol izquierdo contiene uno adicional, es decir, el árbol queda pesado.
- El valor 0 muestra que el árbol incluye nodos iguales en cada lado, es decir, el árbol está perfectamente equilibrado.
Rotaciones AVL
Para que el árbol AVL se equilibre, al insertar o eliminar un nodo del árbol, se realizan rotaciones.
Realizamos la siguiente rotación LL, rotación RR, rotación LR y rotación RL.
- Izquierda – Rotación izquierda
- Derecha – Rotación a la derecha
- Rotación derecha – izquierda
- Rotación izquierda – derecha
Izquierda – Rotación izquierda
Esta rotación se realiza cuando se inserta un nuevo nodo en el hijo izquierdo del subárbol izquierdo.
Se realiza una única rotación hacia la derecha. Este tipo de rotación se identifica cuando un nodo tiene un factor de equilibrio de +2 y su hijo izquierdo tiene un factor de equilibrio de +1.
Derecha – Rotación a la derecha
Esta rotación se realiza cuando se inserta un nuevo nodo en el hijo derecho del subárbol derecho.
Se realiza una única rotación hacia la izquierda. Este tipo de rotación se identifica cuando un nodo tiene un factor de equilibrio de -2 y su hijo derecho tiene un factor de equilibrio de -1.
Rotación derecha – izquierda
Esta rotación se realiza cuando se inserta un nuevo nodo en el hijo derecho del subárbol izquierdo.
Esta rotación se realiza cuando un nodo tiene un factor de equilibrio de –2 y su hijo derecho tiene un factor de equilibrio de +1.
Rotación izquierda – derecha
Esta rotación se realiza cuando se inserta un nuevo nodo en el hijo izquierdo del subárbol derecho.
Esta rotación se realiza cuando un nodo tiene un factor de equilibrio de +2 y su hijo izquierdo tiene un factor de equilibrio de -1.
Inserción en árboles AVL
La operación de inserción es casi la misma que en los árboles de búsqueda binarios simples. Después de cada inserción, equilibramos la altura del árbol. La operación de inserción tiene una complejidad de tiempo de O(log n) en el peor de los casos.
Paso 1: Inserte el nodo en el árbol AVL usando el mismo algoritmo de inserción de BST. En el ejemplo anterior, inserte 160.
Paso 2: Una vez que se agrega el nodo, se actualiza el factor de equilibrio de cada nodo. Después de insertar 160, se actualiza el factor de equilibrio de cada nodo.
Paso 3: Ahora verifique si algún nodo viola el rango del factor de equilibrio, luego realice rotaciones usando el siguiente caso. En el ejemplo anterior, se viola el factor de equilibrio de 350 y el caso 1 se vuelve aplicable allí, realizamos la rotación LL y el árbol se equilibra nuevamente.
- Si BF (nodo) = +2 y BF (nodo -> hijo izquierdo) = +1, realice la rotación LL.
- Si BF (nodo) = -2 y BF (nodo -> hijo derecho) = 1, realice la rotación RR.
- Si BF (nodo) = -2 y BF (nodo -> hijo derecho) = +1, realice la rotación RL.
- Si BF (nodo) = +2 y BF (nodo -> hijo izquierdo) = -1, realice la rotación LR.
Eliminación en árboles AVL
La eliminación también es muy sencilla. Eliminamos usando la misma lógica que en los árboles de búsqueda binarios simples. Después de la eliminación, reestructuramos el árbol, si es necesario, para mantener su altura equilibrada.
Paso 1: Encuentra el elemento en el árbol.
Paso 2: Elimine el nodo, según la eliminación de BST.
Paso 3: Son posibles dos casos: -
Caso 1: Eliminando del subárbol derecho.
- 1A. Si BF (nodo) = +2 y BF (nodo -> hijo izquierdo) = +1, realice la rotación LL.
- 1B. Si BF (nodo) = +2 y BF (nodo -> hijo izquierdo) = -1, realice la rotación LR.
- 1C. Si BF (nodo) = +2 y BF (nodo -> hijo izquierdo) = 0, realice la rotación LL.
Caso 2: Eliminando del subárbol izquierdo.
- 2A. Si BF (nodo) = -2 y BF (nodo -> hijo derecho) = -1, realice la rotación RR.
- 2B. Si BF (nodo) = -2 y BF (nodo -> hijo derecho) = +1, realice la rotación RL.
- 2C. Si BF (nodo) = -2 y BF (nodo -> hijo derecho) = 0, realice la rotación RR.
C++ Ejemplo de árboles AVL
abajo esta el C++ que implementa árboles 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);
}
Ejemplo de ejecución del código anterior:
- Copie el código anterior y péguelo en "avl.cpp".
- Compilar el código:
g++ avl.cpp -o run
- Ejecute el código.
./run
Ventajas de los árboles AVL
- La altura del árbol AVL siempre está equilibrada. La altura nunca crece más allá de log N, donde N es el número total de nodos del árbol.
- Proporciona una mejor complejidad de tiempo de búsqueda en comparación con los árboles de búsqueda binaria simples.
- Los árboles AVL tienen capacidades de autoequilibrio.
Resum
- Los árboles AVL son árboles de búsqueda binarios autoequilibrados.
- El factor de equilibrio es el atributo fundamental de los árboles AVL.
- El factor de equilibrio de un nodo se define como la diferencia entre la altura del subárbol izquierdo y derecho de ese nodo.
- Los valores válidos del factor de equilibrio son -1, 0 y +1.
- La operación de inserción y eliminación requiere que se realicen rotaciones después de violar el factor de equilibrio.
- La complejidad temporal de las operaciones de inserción, eliminación y búsqueda es O(log N).
- Los árboles AVL siguen todas las propiedades de los árboles de búsqueda binaria.
- El subárbol izquierdo tiene nodos que son menores que el nodo raíz. El subárbol derecho tiene nodos que siempre son mayores que el nodo raíz.
- Los árboles AVL se utilizan donde la operación de búsqueda es más frecuente en comparación con las operaciones de inserción y eliminación.
