My IT Utilities

Árbol AVL

Parte de un árbol AVL aleatorio e inserta, busca o borra valores paso a paso: verás el factor de equilibrio de cada nodo, las rotaciones LL, RR, LR y RL, su forma en array y el código C++ resaltado.

Todo se simula en este navegador; no se envía nada a ningún servidor.

Sin pasos

Sin pasos

Árbol AVL

Índice en el array · Factor de equilibrio

60[0]+145[1]+185[2]+167[5]018[3]-153[4]028[8]0

Forma en array

Los hijos del índice i están en 2i+1 y 2i+2.

  • Sin relación
  • Ya recorrido
  • En comparación
  • Encontrado
  • Nuevo
  • A borrar
  • Sucesor
  • Desequilibrado
  • Pivote

Sin pasos

Código

#include <iostream>
#include <algorithm>
using namespace std;
class Node { // Un nodo guarda su valor y los punteros a sus dos hijos
private: // Atributos privados: solo se tocan con los métodos
int value;
Node* left;
Node* right;
public:
Node(int v) : value(v), left(nullptr), right(nullptr) {}
int getValue() const { return value; }
Node* getLeft() const { return left; }
Node* getRight() const { return right; }
void setValue(int v) { value = v; }
void setLeft(Node* n) { left = n; }
void setRight(Node* n) { right = n; }
};
int height(Node* n) { // Altura: una hoja vale 1 y un hueco (nullptr) vale 0
if (n == nullptr) return 0;
return 1 + max(height(n->getLeft()), height(n->getRight()));
}
int balanceFactor(Node* n) { // Factor de equilibrio: altura izquierda menos altura derecha
return height(n->getLeft()) - height(n->getRight());
}
Node* rotateRight(Node* y) { // Rotación simple a la derecha: el hijo izquierdo x sube y y baja
Node* x = y->getLeft();
y->setLeft(x->getRight());
x->setRight(y);
return x;
}
Node* rotateLeft(Node* x) { // Rotación simple a la izquierda: el hijo derecho y sube y x baja
Node* y = x->getRight();
x->setRight(y->getLeft());
y->setLeft(x);
return y;
}
Node* rebalance(Node* n) { // Devuelve la raíz del subárbol ya equilibrada
int bf = balanceFactor(n); // Se calcula el factor de equilibrio del nodo
if (bf > 1) { // Pesa a la izquierda. Si el hijo izquierdo no pesa a la derecha es el caso LL
if (balanceFactor(n->getLeft()) < 0) // El hijo izquierdo pesa a la derecha: caso LR, primero se rota a la izquierda
n->setLeft(rotateLeft(n->getLeft())); // Primera rotación del caso LR
return rotateRight(n); // Rotación a la derecha: resuelve LL y la segunda parte de LR
}
if (bf < -1) { // Pesa a la derecha. Si el hijo derecho no pesa a la izquierda es el caso RR
if (balanceFactor(n->getRight()) > 0) // El hijo derecho pesa a la izquierda: caso RL, primero se rota a la derecha
n->setRight(rotateRight(n->getRight())); // Primera rotación del caso RL
return rotateLeft(n); // Rotación a la izquierda: resuelve RR y la segunda parte de RL
}
return n; // El factor está entre -1 y 1: no hace falta rotar
}
Node* insert(Node* root, int v) { // Inserta v en el árbol AVL y devuelve la raíz
if (root == nullptr) // Hueco vacío: aquí va el nodo nuevo
return new Node(v); // Crea el nodo nuevo
if (v < root->getValue()) // Los menores van a la izquierda y los mayores a la derecha
root->setLeft(insert(root->getLeft(), v)); // Baja por el subárbol izquierdo
else
root->setRight(insert(root->getRight(), v)); // Baja por el subárbol derecho
return rebalance(root); // Al volver de cada llamada se comprueba el equilibrio del nodo
}
int main() {
Node* root = buildTree(); // El árbol mostrado, ya construido
root = insert(root, v); // Primera llamada, desde main
return 0; // Fin de la operación
}

Esta herramienta parte de un árbol AVL aleatorio, un árbol binario de búsqueda que se mantiene equilibrado, y te deja modificarlo a mano: escribes un valor del 1 al 99 y pulsas Insertar, Buscar o Borrar. Cada nodo muestra su factor de equilibrio, la diferencia de alturas entre sus subárboles, y su índice en el array. Cuando un nodo llega a factor 2 o -2, la animación lo marca y aplica la rotación que toca: LL, RR, LR o RL. Debajo se ve el mismo árbol como array y el código C++ resalta la línea que se ejecuta. Todo se simula en tu navegador.

Cómo se usa

  1. Ajusta el tamaño del árbol con el deslizante o pulsa Generar árbol nuevo para cambiar el punto de partida.
  2. Escribe un valor del 1 al 99 y pulsa Insertar, Buscar o Borrar; la animación empieza sola.
  3. Fíjate en el factor de equilibrio bajo cada nodo y en la rotación que se aplica cuando llega a 2 o -2.
  4. Avanza o retrocede paso a paso, y compara el árbol con su forma en array y con la línea resaltada del código C++.

Preguntas frecuentes

¿Qué es un árbol AVL y qué garantiza?
Es un árbol binario de búsqueda que se reequilibra solo: en cada nodo, la diferencia entre la altura del subárbol izquierdo y la del derecho es como máximo 1. Esa diferencia se llama factor de equilibrio y vale -1, 0 o 1 en un AVL correcto. Gracias a ello la altura crece de forma logarítmica con el número de nodos.
¿Cuáles son los cuatro casos de rotación y cuándo se aplica cada uno?
Si un nodo queda con factor 2 y su hijo izquierdo pesa a la izquierda, es el caso LL y basta una rotación simple a la derecha. Si el hijo pesa a la derecha, es LR: se rota a la izquierda el hijo y luego a la derecha el nodo. Con factor -2 es simétrico: RR se resuelve con una rotación simple a la izquierda y RL con una rotación a la derecha del hijo seguida de otra a la izquierda.
¿Cuánto cuestan insertar, buscar y borrar frente a un BST?
En un AVL las tres operaciones cuestan tiempo logarítmico en el peor caso, porque la altura nunca se dispara. En un BST normal el coste depende de la altura, que puede llegar a ser lineal si se insertan los valores en orden y el árbol degenera en una lista. A cambio, el AVL hace algunas rotaciones al insertar o borrar.
¿Cómo se guarda un AVL en un array y qué es el índice sobre cada nodo?
En formato de montículo: la raíz va en el índice 0 y los hijos del índice i, en 2i+1 y 2i+2. El número entre corchetes sobre cada nodo es esa posición, y coincide con la celda del array donde aparece su valor. Si faltan hijos, las posiciones intermedias quedan vacías.

Herramientas relacionadas