Árbol AVL
Última actualización
Un árbol AVL es un árbol binario de búsqueda autoequilibrado. Funciona como un BST normal, pero después de cada inserción comprueba el factor de equilibrio de cada ancestro - la diferencia de altura entre sus subárboles izquierdo y derecho - y si algún nodo queda desequilibrado (una diferencia mayor que 1), realiza rotaciones para restaurar el equilibrio. Pulsa reproducir arriba para ver cómo se insertan los valores y el árbol se rota de nuevo a su forma correcta.
Como nunca deja que el árbol se incline más que ligeramente, un árbol AVL garantiza una altura de O(log n), por lo que la búsqueda, inserción y eliminación son siempre O(log n) - incluso para entradas ordenadas que destrozarían un BST normal. El coste son las rotaciones adicionales y el mantenimiento de la altura en cada inserción.
Complejidad temporal y espacial
| Operación | Complejidad | Notas |
|---|---|---|
| Búsqueda | O(log n) | La altura es siempre ~1.44 log n |
| Inserción | O(log n) | Más O(1) rotaciones |
| Eliminación | O(log n) | Más O(log n) rotaciones |
| Espacio | O(n) | Un campo de altura por nodo |
Los cuatro casos de rotación
| Caso | Desequilibrio | Corrección |
|---|---|---|
| Izquierda-Izquierda | Pesado en la izquierda del hijo izquierdo | Una rotación a la derecha |
| Derecha-Derecha | Pesado en la derecha del hijo derecho | Una rotación a la izquierda |
| Izquierda-Derecha | Pesado en la derecha del hijo izquierdo | Rotación a la izquierda y luego a la derecha |
| Derecha-Izquierda | Pesado en la izquierda del hijo derecho | Rotación a la derecha y luego a la izquierda |
Ejemplo resuelto
Insertando [10, 20, 30, 40, 50, 25] un valor a la vez:
| Paso | Estructura | Acción |
|---|---|---|
Insertar 10 | 10 | El primer nodo se convierte en la raíz; equilibrado |
Insertar 20 | 10(_, 20) | Va a la derecha de 10; sigue equilibrado |
Insertar 30 | 20(10, 30) | Derecha-Derecha en 10, así que una rotación a la izquierda eleva 20 a la raíz |
Insertar 40 | 20(10, 30(_, 40)) | Va a la derecha de 30; todos los factores de equilibrio se mantienen dentro de ±1 |
Insertar 50 | 20(10, 40(30, 50)) | Derecha-Derecha en 30, así que una rotación a la izquierda en 30 eleva 40 |
Insertar 25 | 30(20(10, 25), 40(_, 50)) | Derecha-Izquierda en 20: rota a la derecha el subárbol de 40 y luego rota a la izquierda 20 |
Cuándo usar un árbol AVL
| Úsalo cuando | Evítalo cuando |
|---|---|
| Las búsquedas superan con creces a las inserciones y quieres la altura más ajustada posible | Las inserciones y eliminaciones dominan - las rotaciones y el reequilibrio adicionales cuestan más que en un árbol rojo-negro |
Necesitas un peor caso garantizado de O(log n), incluso para entradas adversarias u ordenadas | Una tabla hash simple bastaría - no necesitas recorrido ordenado ni consultas por rango |
| Necesitas operaciones ordenadas: recorrido en orden, predecesor/sucesor, consultas por rango | El conjunto de datos es minúsculo - un BST normal o un array ordenado es más simple y suficientemente rápido |
| Los datos pueden llegar ya ordenados, lo que convertiría un BST no equilibrado en una lista enlazada | No puedes permitirte la memoria extra del campo de altura por nodo en un espacio muy ajustado |
Código de AVL Tree
Una implementación limpia y ejecutable de AVL Tree en Python, JavaScript, Java, C++, C. Elige un lenguaje, copia el código o ábrelo ya cargado en el Playground de Coddy.
Código de AVL Tree en Python
Python
1class Node:2 def __init__(self, key):3 self.key = key4 self.left = None5 self.right = None6 self.height = 17
8
9def height(node):10 return node.height if node else 011
12
13def update(node):14 node.height = 1 + max(height(node.left), height(node.right))15
16
17def rotate_right(y):18 x = y.left19 y.left = x.right20 x.right = y21 update(y)22 update(x)23 return x24
25
26def rotate_left(x):27 y = x.right28 x.right = y.left29 y.left = x30 update(x)31 update(y)32 return y33
34
35def insert(node, key):36 if node is None:37 return Node(key)38 if key < node.key:39 node.left = insert(node.left, key)40 else:41 node.right = insert(node.right, key)42 update(node)43 balance = height(node.left) - height(node.right)44 # Four imbalance cases: LL, RR, LR, RL45 if balance > 1 and key < node.left.key:46 return rotate_right(node)47 if balance < -1 and key > node.right.key:48 return rotate_left(node)49 if balance > 1:50 node.left = rotate_left(node.left)51 return rotate_right(node)52 if balance < -1:53 node.right = rotate_right(node.right)54 return rotate_left(node)55 return node56
57
58def inorder(node):59 if node is None:60 return []61 return inorder(node.left) + [node.key] + inorder(node.right)62
63
64root = None65for key in [10, 20, 30, 40, 50, 25]:66 root = insert(root, key)67
68print("Inorder:", inorder(root))69print("Root:", root.key, "| tree height:", root.height)Código de AVL Tree en JavaScript
JavaScript
1class Node {2 constructor(key) {3 this.key = key;4 this.left = null;5 this.right = null;6 this.height = 1;7 }8}9
10const height = (n) => (n ? n.height : 0);11const update = (n) => {12 n.height = 1 + Math.max(height(n.left), height(n.right));13};14const balance = (n) => height(n.left) - height(n.right);15
16function rotateRight(y) {17 const x = y.left;18 y.left = x.right;19 x.right = y;20 update(y);21 update(x);22 return x;23}24
25function rotateLeft(x) {26 const y = x.right;27 x.right = y.left;28 y.left = x;29 update(x);30 update(y);31 return y;32}33
34function insert(node, key) {35 if (!node) return new Node(key);36 if (key < node.key) node.left = insert(node.left, key);37 else node.right = insert(node.right, key);38 update(node);39 const b = balance(node);40 // Four rebalancing cases: LL, RR, LR, RL41 if (b > 1 && key < node.left.key) return rotateRight(node);42 if (b < -1 && key > node.right.key) return rotateLeft(node);43 if (b > 1) {44 node.left = rotateLeft(node.left);45 return rotateRight(node);46 }47 if (b < -1) {48 node.right = rotateRight(node.right);49 return rotateLeft(node);50 }51 return node;52}53
54function inorder(node, out = []) {55 if (!node) return out;56 inorder(node.left, out);57 out.push(node.key);58 inorder(node.right, out);59 return out;60}61
62let root = null;63for (const key of [10, 20, 30, 40, 50, 25]) root = insert(root, key);64console.log("Root after rebalancing:", root.key);65console.log("Inorder:", inorder(root).join(" "));Código de AVL Tree en Java
Java
1public class Main {2 static class Node {3 int key, height = 1;4 Node left, right;5 Node(int key) { this.key = key; }6 }7
8 static int height(Node n) { return n == null ? 0 : n.height; }9 static int balance(Node n) { return n == null ? 0 : height(n.left) - height(n.right); }10 static void update(Node n) { n.height = 1 + Math.max(height(n.left), height(n.right)); }11
12 static Node rotateRight(Node y) {13 Node x = y.left;14 y.left = x.right;15 x.right = y;16 update(y); update(x);17 return x;18 }19
20 static Node rotateLeft(Node x) {21 Node y = x.right;22 x.right = y.left;23 y.left = x;24 update(x); update(y);25 return y;26 }27
28 static Node insert(Node node, int key) {29 if (node == null) return new Node(key);30 if (key < node.key) node.left = insert(node.left, key);31 else node.right = insert(node.right, key);32 update(node);33 int b = balance(node);34 // Four imbalance cases: LL, RR, LR, RL35 if (b > 1 && key < node.left.key) return rotateRight(node);36 if (b < -1 && key > node.right.key) return rotateLeft(node);37 if (b > 1) { node.left = rotateLeft(node.left); return rotateRight(node); }38 if (b < -1) { node.right = rotateRight(node.right); return rotateLeft(node); }39 return node;40 }41
42 static void inorder(Node n, StringBuilder sb) {43 if (n == null) return;44 inorder(n.left, sb);45 sb.append(n.key).append(" ");46 inorder(n.right, sb);47 }48
49 public static void main(String[] args) {50 Node root = null;51 int[] keys = {10, 20, 30, 40, 50, 25};52 for (int k : keys) root = insert(root, k);53 StringBuilder sb = new StringBuilder();54 inorder(root, sb);55 System.out.println("Inorder: " + sb.toString().trim());56 System.out.println("Root after rebalancing: " + root.key + " (height " + root.height + ")");57 }58}Código de AVL Tree en C++
C++
1#include <algorithm>2#include <iostream>3
4struct Node {5 int value;6 int height = 1;7 Node* left = nullptr;8 Node* right = nullptr;9 explicit Node(int v) : value(v) {}10};11
12int height(const Node* n) { return n ? n->height : 0; }13int balanceFactor(const Node* n) { return height(n->left) - height(n->right); }14void updateHeight(Node* n) {15 n->height = 1 + std::max(height(n->left), height(n->right));16}17
18Node* rotateRight(Node* y) {19 Node* x = y->left;20 y->left = x->right;21 x->right = y;22 updateHeight(y);23 updateHeight(x);24 return x;25}26
27Node* rotateLeft(Node* x) {28 Node* y = x->right;29 x->right = y->left;30 y->left = x;31 updateHeight(x);32 updateHeight(y);33 return y;34}35
36Node* insert(Node* node, int value) {37 if (node == nullptr) return new Node(value);38 if (value < node->value) node->left = insert(node->left, value);39 else node->right = insert(node->right, value);40 updateHeight(node);41 int balance = balanceFactor(node);42 // Four rebalancing cases: LL, RR, LR, RL43 if (balance > 1 && value < node->left->value) return rotateRight(node);44 if (balance < -1 && value > node->right->value) return rotateLeft(node);45 if (balance > 1) {46 node->left = rotateLeft(node->left);47 return rotateRight(node);48 }49 if (balance < -1) {50 node->right = rotateRight(node->right);51 return rotateLeft(node);52 }53 return node;54}55
56void inorder(const Node* n) {57 if (n == nullptr) return;58 inorder(n->left);59 std::cout << n->value << "(h" << n->height << ") ";60 inorder(n->right);61}62
63int main() {64 Node* root = nullptr;65 for (int value : {10, 20, 30, 40, 50, 25}) root = insert(root, value);66 std::cout << "Root after rebalancing: " << root->value << "\n";67 std::cout << "In-order: ";68 inorder(root);69 std::cout << "\n";70 return 0;71}Código de AVL Tree en C
C
1#include <stdio.h>2#include <stdlib.h>3
4typedef struct Node {5 int value, height;6 struct Node* left;7 struct Node* right;8} Node;9
10int height(const Node* n) { return n ? n->height : 0; }11int balanceFactor(const Node* n) { return height(n->left) - height(n->right); }12int maxInt(int a, int b) { return a > b ? a : b; }13
14Node* newNode(int value) {15 Node* n = calloc(1, sizeof(Node));16 n->value = value;17 n->height = 1;18 return n;19}20
21void updateHeight(Node* n) {22 n->height = 1 + maxInt(height(n->left), height(n->right));23}24
25Node* rotateRight(Node* y) {26 Node* x = y->left;27 y->left = x->right;28 x->right = y;29 updateHeight(y);30 updateHeight(x);31 return x;32}33
34Node* rotateLeft(Node* x) {35 Node* y = x->right;36 x->right = y->left;37 y->left = x;38 updateHeight(x);39 updateHeight(y);40 return y;41}42
43Node* insert(Node* node, int value) {44 if (node == NULL) return newNode(value);45 if (value < node->value) node->left = insert(node->left, value);46 else node->right = insert(node->right, value);47 updateHeight(node);48 int balance = balanceFactor(node);49 // Four rebalancing cases: LL, RR, LR, RL50 if (balance > 1 && value < node->left->value) return rotateRight(node);51 if (balance < -1 && value > node->right->value) return rotateLeft(node);52 if (balance > 1) {53 node->left = rotateLeft(node->left);54 return rotateRight(node);55 }56 if (balance < -1) {57 node->right = rotateRight(node->right);58 return rotateLeft(node);59 }60 return node;61}62
63void inorder(const Node* n) {64 if (n == NULL) return;65 inorder(n->left);66 printf("%d(h%d) ", n->value, n->height);67 inorder(n->right);68}69
70int main(void) {71 int values[] = {10, 20, 30, 40, 50, 25};72 Node* root = NULL;73 for (int i = 0; i < 6; i++) root = insert(root, values[i]);74 printf("Root after rebalancing: %d\n", root->value);75 printf("In-order: ");76 inorder(root);77 printf("\n");78 return 0;79}Preguntas frecuentes sobre el árbol AVL
¿Qué es un factor de equilibrio en un árbol AVL?
El factor de equilibrio de un nodo es la altura de su subárbol izquierdo menos la altura de su subárbol derecho. Un árbol AVL mantiene el factor de equilibrio de cada nodo en -1, 0 o +1; si una inserción lo saca de ese rango, una rotación restaura el equilibrio.
¿Cuál es la diferencia entre un árbol AVL y un árbol rojo-negro?
Ambos son BST autoequilibrados con operaciones
O(log n). Los árboles AVL están más estrictamente equilibrados, por lo que las búsquedas son ligeramente más rápidas, pero pueden hacer más rotaciones en inserción/eliminación. Los árboles rojo-negro están más laxamente equilibrados, favoreciendo menos rotaciones - por eso muchas bibliotecas estándar los usan para mapas y conjuntos.¿Por qué usar un árbol AVL en lugar de un árbol binario de búsqueda normal?
Un BST normal puede degradarse a operaciones
O(n) si los valores llegan en orden, formando una cadena sesgada. Un árbol AVL rota para mantenerse equilibrado, garantizando una altura y operaciones O(log n) sin importar el orden de inserción.¿Es un árbol AVL mejor que un árbol rojo-negro para un índice de base de datos?
Depende de la carga de trabajo. Los árboles AVL están más rígidamente equilibrados, así que ganan cuando las lecturas dominan y quieres las rutas de búsqueda más cortas posibles. Pero la mayoría de las bases de datos y bibliotecas de lenguajes eligen árboles rojo-negro (o árboles B) porque reequilibran con menos rotaciones en cargas con muchas escrituras, lo que importa más cuando las inserciones y eliminaciones son frecuentes.
¿Cuántas rotaciones necesita una sola inserción en un árbol AVL?
Se necesita como máximo una rotación - ya sea una rotación simple o una doble (de dos pasos) - para reequilibrar el árbol tras insertar un valor. Esto se debe a que una inserción aumenta la altura de un subárbol en como mucho uno, así que una única corrección en el ancestro desequilibrado más bajo basta. La eliminación es diferente: puede requerir hasta
O(log n) rotaciones a medida que el reequilibrio se propaga hacia la raíz.¿Necesito actualizar las alturas de los nodos después de cada rotación?
Sí - un error común es rotar los punteros correctamente pero olvidar recalcular la altura de los dos nodos implicados. Después de cada rotación debes actualizar primero la altura del nodo degradado y luego la del nodo promovido, porque la altura del nodo promovido depende de sus nuevos hijos. Omitir esto deja factores de equilibrio obsoletos que rompen las decisiones de reequilibrio futuras.
Recursos relacionados
Más visualizaciones
