1. Introducción
En este tutorial, presentaremos el árbol AVL y veremos algoritmos para insertar, eliminar y buscar valores.
2. ¿Qué es AVL Tree?
El árbol AVL, que lleva el nombre de sus inventores Adelson-Velsky y Landis, es un árbol de búsqueda binaria (BST) autoequilibrado.
Un árbol de autoequilibrio es un árbol de búsqueda binario que equilibra la altura después de la inserción y eliminación de acuerdo con algunas reglas de equilibrio.
La complejidad temporal en el peor de los casos de una BST es una función de la altura del árbol. Específicamente, el camino más largo desde la raíz del árbol hasta un nodo. Para un BST con N nodos, digamos que cada nodo tiene solo cero o un hijo. Por lo tanto, su altura es igual a N y el tiempo de búsqueda en el peor de los casos es O (N). Entonces, nuestro principal objetivo en un BST es mantener la altura máxima cerca del registro (N).
El factor de equilibrio del nodo N es altura (derecha (N)) - altura (izquierda (N)) . En un árbol AVL, el factor de equilibrio de un nodo podría ser solo uno de los valores 1, 0 o -1.
Definamos un objeto Node para nuestro árbol:
public class Node { int key; int height; Node left; Node right; ... }A continuación, definamos el AVLTree :
public class AVLTree { private Node root; void updateHeight(Node n) { n.height = 1 + Math.max(height(n.left), height(n.right)); } int height(Node n) { return n == null ? -1 : n.height; } int getBalance(Node n) { return (n == null) ? 0 : height(n.right) - height(n.left); } ... }3. ¿Cómo equilibrar un árbol AVL?
El árbol AVL verifica el factor de equilibrio de sus nodos después de la inserción o eliminación de un nodo. Si el factor de equilibrio de un nodo es mayor que uno o menor que -1, el árbol se reequilibra.
Hay dos operaciones para reequilibrar un árbol:
- rotación derecha y
- Rotación a la izquierda.
3.1. Rotación derecha
Comencemos con la rotación correcta.
Suponga que tenemos una BST llamada T1, con Y como nodo raíz, X como el hijo izquierdo de Y y Z como el hijo derecho de X. Dadas las características de una BST, sabemos que X <Z <Y.
Después de una rotación derecha de Y, tenemos un árbol llamado T2 con X como raíz e Y como hijo derecho de X y Z como hijo izquierdo de Y. T2 sigue siendo un BST porque mantiene el orden X <Z <Y .
Echemos un vistazo a la operación de rotación correcta para nuestro AVLTree :
Node rotateRight(Node y) { Node x = y.left; Node z = x.right; x.right = y; y.left = z; updateHeight(y); updateHeight(x); return x; }3.2. Operación de rotación izquierda
También tenemos una operación de rotación a la izquierda.
Suponga una BST llamada T1, con Y como nodo raíz, X como hijo derecho de Y y Z como hijo izquierdo de X. Dado esto, sabemos que Y <Z <X.
Después de una rotación a la izquierda de Y, tenemos un árbol llamado T2 con X como raíz e Y como hijo izquierdo de X y Z como hijo derecho de Y. T2 sigue siendo un BST porque mantiene el orden Y <Z <X .
Echemos un vistazo a la operación de rotación a la izquierda de nuestro AVLTree :
Node rotateLeft(Node y) { Node x = y.right; Node z = x.left; x.left = y; y.right = z; updateHeight(y); updateHeight(x); return x; }3.3. Técnicas de reequilibrio
Podemos utilizar las operaciones de rotación derecha e izquierda en combinaciones más complejas para mantener el árbol AVL equilibrado después de cualquier cambio en sus nodos . En una estructura desequilibrada, al menos un nodo tiene un factor de equilibrio igual a 2 o -2. Veamos cómo podemos equilibrar el árbol en estas situaciones.
Cuando el factor de equilibrio del nodo Z es 2, el subárbol con Z como raíz está en uno de estos dos estados, considerando Y como el hijo derecho de Z.
For the first case, the height in the right child of Y (X) is greater than the hight of the left child (T2). We can rebalance the tree easily by a left rotation of Z.
For the second case, the height of the right child of Y (T4) is less than the height of the left child (X). This situation needs a combination of rotation operations.
In this case, we first rotate Y to the right, so the tree gets in the same shape as the previous case. Then we can rebalance the tree by a left rotation of Z.
Also, when the balance factor of node Z is -2, its subtree is in one of these two states, so we consider Z as the root and Y as its left child.
The height in the left child of Y is greater than that of its right child, so we balance the tree with the right rotation of Z.
Or in the second case, the right child of Y has a greater height than its left child.
So, first of all, we transform it into the former shape with a left rotation of Y, then we balance the tree with the right rotation of Z.
Let's take a look at the rebalance operation for our AVLTree:
Node rebalance(Node z) { updateHeight(z); int balance = getBalance(z); if (balance > 1) { if (height(z.right.right) > height(z.right.left)) { z = rotateLeft(z); } else { z.right = rotateRight(z.right); z = rotateLeft(z); } } else if (balance height(z.left.right)) z = rotateRight(z); else { z.left = rotateLeft(z.left); z = rotateRight(z); } } return z; }We'll use rebalance after inserting or deleting a node for all the nodes in the path from the changed node to the root.
4. Insert a Node
When we're going to insert a key in the tree, we have to locate its proper position to pass the BST rules. So we start from the root and compare its value with the new key. If the key is greater, we continue to the right — otherwise, we go to the left child.
Once we find the proper parent node, then we add the new key as a node to left or right, depending on the value.
After inserting the node, we have a BST, but it may not be an AVL Tree. Therefore, we check the balance factors and rebalance the BST for all the nodes in the path from the new node to the root.
Let's take a look at the insert operation:
Node insert(Node node, int key) { if (node == null) { return new Node(key); } else if (node.key > key) { node.left = insert(node.left, key); } else if (node.key < key) { node.right = insert(node.right, key); } else { throw new RuntimeException("duplicate Key!"); } return rebalance(node); }It is important to remember that a key is unique in the tree — no two nodes share the same key.
The time complexity of the insert algorithm is a function of the height. Since our tree is balanced, we can assume that time complexity in the worst case is O(log(N)).
5. Delete a Node
To delete a key from the tree, we first have to find it in the BST.
After we find the node (called Z), we have to introduce the new candidate to be its replacement in the tree. If Z is a leaf, the candidate is empty. If Z has only one child, this child is the candidate, but if Z has two children, the process is a bit more complicated.
Assume the right child of Z called Y. First, we find the leftmost node of the Y and call it X. Then, we set the new value of Z equal to X ‘s value and continue to delete X from Y.
Finally, we call the rebalance method at the end to keep the BST an AVL Tree.
Here is our delete method:
Node delete(Node node, int key) { if (node == null) { return node; } else if (node.key > key) { node.left = delete(node.left, key); } else if (node.key < key) { node.right = delete(node.right, key); } else { if (node.left == null || node.right == null) { node = (node.left == null) ? node.right : node.left; } else { Node mostLeftChild = mostLeftChild(node.right); node.key = mostLeftChild.key; node.right = delete(node.right, node.key); } } if (node != null) { node = rebalance(node); } return node; }The time complexity of the delete algorithm is a function of the height of the tree. Similar to the insert method, we can assume that time complexity in the worst case is O(log(N)).
6. Search for a Node
Searching for a node in an AVL Tree is the same as with any BST.
Start from the root of the tree and compare the key with the value of the node. If the key equals the value, return the node. If the key is greater, search from the right child, otherwise continue the search from the left child.
La complejidad temporal de la búsqueda es función de la altura. Podemos suponer que la complejidad del tiempo en el peor de los casos es O (log (N)).
Veamos el código de muestra:
Node find(int key) { Node current = root; while (current != null) { if (current.key == key) { break; } current = current.key < key ? current.right : current.left; } return current; }7. Conclusión
En este tutorial, hemos implementado un árbol AVL con operaciones de inserción, eliminación y búsqueda.
Como siempre, puedes encontrar el código en Github.