¿Qué son los árboles AVL?
Árboles AVL son árboles de búsqueda binarios en los que la diferencia entre la altura del subtítulo izquierdo y derecho es -1, 0 o +1.
Los árboles AVL también se denominan árbol de búsqueda binaria autoequilibrado. Estos árboles ayudan a mantener el tiempo de búsqueda logarítmica. Lleva el nombre de sus inventores (AVL) Adelson, Velsky y Landis.
En este tutorial de algoritmos, aprenderá:
¿Cómo funciona AVL Tree?
Para comprender mejor la necesidad de árboles AVL, veamos algunas desventajas de los árboles de búsqueda binarios simples.
Considere las siguientes claves ingresadas en el orden dado en el árbol de búsqueda binaria.
La altura del árbol crece linealmente en tamaño a medida que colocamos las claves en orden creciente de su valor. Entonces O (n) toma la operación de búsqueda, en el peor de los casos.
Se necesita un tiempo lineal para buscar un elemento; por lo que no se utiliza la estructura de árbol de búsqueda binaria. Por otro lado, si la altura del árbol está equilibrada, obtenemos un mejor tiempo de búsqueda.
Ahora veamos las mismas claves pero insertadas en un orden diferente.
Aquí, las claves son las mismas, pero como se insertan en un orden diferente, asumen diferentes posiciones y la altura del árbol permanece equilibrada. Entonces, una búsqueda no tomará más de O (log n) en ningún aspecto del árbol. Ahora está claro que, si se inserta correctamente, la altura del árbol se puede mantener equilibrada.
En los mástiles AVL, controlamos la altura del mástil durante la operación. Se realizan modificaciones para mantener la altura equilibrada sin anular las propiedades subyacentes del árbol de búsqueda binaria.
Factor de equilibrio en árboles AVL
El factor de equilibrio (BF) que ayuda a monitorear la altura de los árboles es una característica fundamental de todos los nodos en los árboles AVL.
Propiedades del factor de equilibrio
- El factor de equilibrio se denomina diferencia entre la altura del título izquierdo y el título 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 hay uno extra en el subárbol izquierdo, es decir, queda el árbol pesado.
- El valor +1 indica que hay uno extra en el subárbol izquierdo, es decir, queda el árbol pesado.
- Un valor de 0 indica que el árbol tiene nodos idénticos en cada lado, es decir, el árbol está perfectamente equilibrado.
Rotación AVL
Para hacer el balance del árbol AVL en sí, cuando se inserta o elimina un nodo del árbol, se realiza la rotación.
Realizamos la siguiente rotación LL, rotación RR, rotación CD y rotación RL.
- Izquierda – Rotación izquierda
- Derecha – Girar a la derecha
- Derecha – Girar a la izquierda
- Izquierda: girar a la derecha
Izquierda – Rotación izquierda
Esta rotación se realiza cuando el hijo izquierdo del título izquierdo inserta un nuevo nodo.
Se realiza una rotación a la derecha. Este tipo de rotación se reconoce cuando un nodo tiene un factor de equilibrio como +2 y su hijo izquierdo tiene un factor de equilibrio como +1.
Derecha – Girar a la derecha
Esta rotación se realiza cuando el hijo correcto del subtítulo correcto inserta un nuevo nodo.
Se hace una rotación hacia la izquierda. Este tipo de rotación se reconoce cuando un nodo tiene un factor de equilibrio como -2, y su hijo correcto tiene un factor de equilibrio de -1.
Derecha – Girar a la izquierda
Esta rotación se realiza cuando el niño inserta un nuevo nodo a la derecha del título izquierdo.
Esta rotación se realiza cuando un nodo tiene un factor de equilibrio como –2, y su hijo tiene un factor de equilibrio a la derecha de +1.
Izquierda – Girar a la derecha
Esta rotación se realiza cuando el niño inserta un nuevo nodo a la derecha del título izquierdo.
Esta rotación se realiza cuando un nodo tiene un factor de equilibrio como +2, y su hijo derecho tiene un factor de equilibrio como -1.
Insertar en árboles AVL
La operación de entrada es casi la misma que la de los árboles de búsqueda binarios simples. Después de cada inserción, equilibraremos la altura del árbol. La operación toma O (log n) la peor complejidad de tiempo.
Paso 1: Inserte el nodo en el árbol AVL utilizando el mismo algoritmo de inserción de BST. En el ejemplo anterior, ingrese 160.
Paso 2: Cuando se agrega el nodo, se actualiza el factor de balance de cada nodo. Después de ingresar 160, se actualiza el factor de balance de cada nodo.
Paso 3: Ahora verifique si algún nodo excede el rango del factor de balance si se excede el factor de balance, luego rote usando el caso a continuación. En el ejemplo anterior, se excede el factor de equilibrio de 350 y luego se aplica el caso 1, giramos LL y el mástil se equilibra nuevamente.
- Si BF (nodo) = +2 y BF (nodo -> hijo izquierdo) = +1, gire LL.
- Si BF (nodo) = -2 y BF (nodo -> niño derecho) = 1, gire RR.
- Si BF (nodo) = -2 y BF (nodo -> niño derecho) = +1, gire RL.
- Si BF (nodo) = +2 y BF (nodo -> hijo izquierdo) = -1, gire CD.
Destruido en árboles AVL
La eliminación también es muy sencilla. Eliminamos la misma lógica utilizada en árboles de búsqueda binarios simples. Después de destruirlo, reestructuramos el árbol, si es necesario, para mantener su altura justa.
Paso 1: Encuentra el elemento en el árbol.
Paso 2: Elimine el nodo, de acuerdo con Delete BST.
Paso 3: Se pueden realizar dos casos: –
Caso 1: Eliminando del subtítulo correcto.
- 1A. Si BF (nodo) = +2 y BF (nodo -> hijo izquierdo) = +1, gire LL.
- 1B. Si BF (nodo) = +2 y BF (nodo -> hijo izquierdo) = -1, gire CD.
- 1C. Si BF (nodo) = +2 y BF (nodo -> hijo izquierdo) = 0, gire LL.
Caso 2: Eliminando del título de la izquierda.
- 2A. Si BF (nodo) = -2 y BF (nodo -> niño derecho) = -1, gire RR.
- 2B. Si BF (nodo) = -2 y BF (nodo -> niño derecho) = +1, gire RL.
- 2C. Si BF (nodo) = -2 y BF (nodo -> niño derecho) = 0, gire RR.
Ejemplo de C ++ de árboles AVL
A continuación se muestra el código 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.Deleten";
cout<<"n0.Exitn";
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 actual del código anterior:
- Copie el código anterior y pegue «avl.cpp».
- Compila 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á del hueco de N, donde N es el número total de nodos en el árbol.
- Ofrece una mayor complejidad en términos de tiempo de búsqueda en comparación con los árboles de búsqueda binaria simples.
- Los árboles AVL tienen capacidades de autoequilibrio.
Resumen:
- Los árboles AVL son árboles de búsqueda binarios autoequilibrados.
- El factor de equilibrio es la característica básica de los árboles AVL.
- Un factor de equilibrio de nodo se define como la diferencia entre la altura de los títulos 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 rotaciones después de que se excede el factor de equilibrio.
- O (log N) es la complejidad temporal de insertar, eliminar y buscar una operación.
- Los árboles AVL siguen todas las propiedades de los árboles de búsqueda binaria.
- El título de la izquierda tiene nodos que son más pequeños que el nodo raíz. El título correcto tiene nodos que siempre son más grandes que el nodo raíz.
- Los árboles AVL se utilizan cuando la operación de búsqueda es más frecuente en comparación con las operaciones de inserción y eliminación.