Árbol AVL

En este tutorial, aprenderá qué es un árbol avl. Además, encontrará ejemplos prácticos de varias operaciones realizadas en un árbol avl en C, C ++, Java y Python.

El árbol AVL es un árbol de búsqueda binario autoequilibrado en el que cada nodo mantiene información adicional llamada factor de equilibrio cuyo valor es -1, 0 o +1.

El árbol AVL recibió su nombre de su inventor Georgy Adelson-Velsky y Landis.

Factor de equilibrio

El factor de equilibrio de un nodo en un árbol AVL es la diferencia entre la altura del subárbol izquierdo y la del subárbol derecho de ese nodo.

Factor de equilibrio = (Altura del subárbol izquierdo - Altura del subárbol derecho) o (Altura del subárbol derecho - Altura del subárbol izquierdo)

La propiedad de autoequilibrio de un árbol avl se mantiene mediante el factor de equilibrio. El valor del factor de equilibrio siempre debe ser -1, 0 o +1.

Un ejemplo de un árbol avl equilibrado es:

Árbol avl

Operaciones en un árbol AVL

Varias operaciones que se pueden realizar en un árbol AVL son:

Rotación de los subárboles en un árbol AVL

En la operación de rotación, las posiciones de los nodos de un subárbol se intercambian.

Hay dos tipos de rotaciones:

Girar a la izquierda

En la rotación a la izquierda, la disposición de los nodos de la derecha se transforma en las disposiciones del nodo izquierdo.

Algoritmo

1. Sea el árbol inicial: Rotación a la izquierda
2. Si y tiene un subárbol izquierdo, asigne x como padre del subárbol izquierdo de y. Asignar x como padre del subárbol izquierdo de y
3. Si el padre de x es NULL, haga que y sea la raíz del árbol.
4. De lo contrario, si x es el hijo izquierdo de p, haga que y sea el hijo izquierdo de p.
5. De lo contrario, asigne y como el hijo derecho de p. Cambiar el padre de x por el de y
6. Haga que y sea el padre de x. Asigne y como padre de x.

Girar a la derecha

En la rotación a la izquierda, la disposición de los nodos de la izquierda se transforma en las disposiciones del nodo derecho.

1. Sea el árbol inicial: árbol inicial
2. Si x tiene un subárbol derecho, asigne y como padre del subárbol derecho de x. Asignar y como padre del subárbol derecho de x
3. Si el padre de y es NULL, haz que x sea la raíz del árbol.
4. De lo contrario, si y es el hijo derecho de su padre p, haga que x sea el hijo derecho de p.
5. De lo contrario, asigne x como el hijo izquierdo de p. Asigne el padre de y como padre de x.
6. Haga que x sea el padre de y. Asignar x como padre de y

Girar de izquierda a derecha y de derecha a izquierda

En la rotación de izquierda a derecha, los arreglos se desplazan primero a la izquierda y luego a la derecha.

1. Haga la rotación a la izquierda en xy. Girar a la izquierda xy
2. Haga la rotación correcta en yz. Girar a la derecha zy

En la rotación derecha-izquierda, los arreglos se desplazan primero a la derecha y luego a la izquierda.

1. Realice la rotación correcta en xy. Girar a la derecha xy
2. Haga la rotación a la izquierda en zy. Girar a la izquierda zy

Algoritmo para insertar un nuevo nodo

Un newNode siempre se inserta como un nodo hoja con un factor de balance igual a 0.

1. Sea el árbol inicial: Árbol inicial para la inserción
   Sea el nodo a insertar: Nuevo nodo
2. Vaya al nodo hoja apropiado para insertar un newNode usando los siguientes pasos recursivos. Compare newKey con rootKey del árbol actual.
   1. Si newKey <rootKey, llame al algoritmo de inserción en el subárbol izquierdo del nodo actual hasta que se alcance el nodo hoja.
   2. De lo contrario, si newKey> rootKey, llame al algoritmo de inserción en el subárbol derecho del nodo actual hasta que se alcance el nodo hoja.
   3. De lo contrario, devuelva leafNode. Encontrar la ubicación para insertar newNode
3. Compare leafKey obtenida de los pasos anteriores con newKey:
   1. Si newKey <leafKey, haga que newNode sea el leftChild de leafNode.
   2. De lo contrario, convierta newNode en rightChild de leafNode. Insertar el nuevo nodo
4. Actualizar balanceFactor de los nodos. Actualización del factor de equilibrio después de la inserción
5. Si los nodos están desequilibrados, reequilibre el nodo.
   1. Si balanceFactor> 1, significa que la altura del subárbol izquierdo es mayor que la del subárbol derecho. Entonces, haz una rotación a la derecha o una rotación de izquierda a derecha
      1. Si newNodeKey <leftChildKey, realice la rotación derecha.
      2. De lo contrario, haga la rotación de izquierda a derecha. Equilibrar el árbol con la rotación Equilibrar el árbol con la rotación
   2. Si balanceFactor <-1, significa que la altura del subárbol derecho es mayor que la del subárbol izquierdo. Entonces, haz rotación derecha o rotación derecha-izquierda
      1. Si newNodeKey> rightChildKey, haga la rotación a la izquierda.
      2. De lo contrario, haz una rotación de derecha a izquierda
6. El árbol final es: árbol equilibrado final

Algoritmo para eliminar un nodo

Un nodo siempre se elimina como nodo hoja. Después de eliminar un nodo, los factores de equilibrio de los nodos cambian. Para reequilibrar el factor de equilibrio, se realizan rotaciones adecuadas.

1. Busque nodeToBeDeleted (la recursividad se usa para encontrar nodeToBeDeleted en el código que se usa a continuación). Ubicación del nodo que se eliminará
2. Hay tres casos para eliminar un nodo:
   1. Si nodeToBeDeleted es el nodo hoja (es decir, no tiene ningún hijo), elimine nodeToBeDeleted.
   2. Si nodeToBeDeleted tiene un hijo, sustituya el contenido de nodeToBeDeleted por el del hijo. Retire al niño.
   3. Si nodeToBeDeleted tiene dos hijos, busque el sucesor en orden w de nodeToBeDeleted (es decir, un nodo con un valor mínimo de clave en el subárbol derecho). Encontrar al sucesor
      1. Sustituya el contenido de nodeToBeDeleted por el de w. Sustituir el nodo a eliminar
      2. Retire el nodo hoja w. Quitar w
3. Actualizar balanceFactor de los nodos. Actualizar bf
4. Reequilibre el árbol si el factor de equilibrio de cualquiera de los nodos no es igual a -1, 0 o 1.
   1. Si balanceFactor of currentNode> 1,
      1. Si balanceFactor of leftChild> = 0, haga la rotación derecha. Gire a la derecha para equilibrar el árbol
      2. De lo contrario, realice la rotación de izquierda a derecha.
   2. Si balanceFactor de currentNode <-1,
      1. Si balanceFactor of rightChild <= 0, haga la rotación a la izquierda.
      2. De lo contrario, haga la rotación derecha-izquierda.
5. El árbol final es: Avl tree final

Ejemplos de Python, Java y C / C ++

Python Java C C ++

 # AVL tree implementation in Python import sys # Create a tree node class TreeNode(object): def __init__(self, key): self.key = key self.left = None self.right = None self.height = 1 class AVLTree(object): # Function to insert a node def insert_node(self, root, key): # Find the correct location and insert the node if not root: return TreeNode(key) elif key 1: if key < root.left.key: return self.rightRotate(root) else: root.left = self.leftRotate(root.left) return self.rightRotate(root) if balanceFactor root.right.key: return self.leftRotate(root) else: root.right = self.rightRotate(root.right) return self.leftRotate(root) return root # Function to delete a node def delete_node(self, root, key): # Find the node to be deleted and remove it if not root: return root elif key root.key: root.right = self.delete_node(root.right, key) else: if root.left is None: temp = root.right root = None return temp elif root.right is None: temp = root.left root = None return temp temp = self.getMinValueNode(root.right) root.key = temp.key root.right = self.delete_node(root.right, temp.key) if root is None: return root # Update the balance factor of nodes root.height = 1 + max(self.getHeight(root.left), self.getHeight(root.right)) balanceFactor = self.getBalance(root) # Balance the tree if balanceFactor> 1: if self.getBalance(root.left)>= 0: return self.rightRotate(root) else: root.left = self.leftRotate(root.left) return self.rightRotate(root) if balanceFactor < -1: if self.getBalance(root.right) <= 0: return self.leftRotate(root) else: root.right = self.rightRotate(root.right) return self.leftRotate(root) return root # Function to perform left rotation def leftRotate(self, z): y = z.right T2 = y.left y.left = z z.right = T2 z.height = 1 + max(self.getHeight(z.left), self.getHeight(z.right)) y.height = 1 + max(self.getHeight(y.left), self.getHeight(y.right)) return y # Function to perform right rotation def rightRotate(self, z): y = z.left T3 = y.right y.right = z z.left = T3 z.height = 1 + max(self.getHeight(z.left), self.getHeight(z.right)) y.height = 1 + max(self.getHeight(y.left), self.getHeight(y.right)) return y # Get the height of the node def getHeight(self, root): if not root: return 0 return root.height # Get balance factore of the node def getBalance(self, root): if not root: return 0 return self.getHeight(root.left) - self.getHeight(root.right) def getMinValueNode(self, root): if root is None or root.left is None: return root return self.getMinValueNode(root.left) def preOrder(self, root): if not root: return print("(0) ".format(root.key), end="") self.preOrder(root.left) self.preOrder(root.right) # Print the tree def printHelper(self, currPtr, indent, last): if currPtr != None: sys.stdout.write(indent) if last: sys.stdout.write("R----") indent += " " else: sys.stdout.write("L----") indent += "| " print(currPtr.key) self.printHelper(currPtr.left, indent, False) self.printHelper(currPtr.right, indent, True) myTree = AVLTree() root = None nums = (33, 13, 52, 9, 21, 61, 8, 11) for num in nums: root = myTree.insert_node(root, num) myTree.printHelper(root, "", True) key = 13 root = myTree.delete_node(root, key) print("After Deletion: ") myTree.printHelper(root, "", True)

 // AVL tree implementation in Java // Create node class Node ( int item, height; Node left, right; Node(int d) ( item = d; height = 1; ) ) // Tree class class AVLTree ( Node root; int height(Node N) ( if (N == null) return 0; return N.height; ) int max(int a, int b) ( return (a> b) ? a : b; ) Node rightRotate(Node y) ( Node x = y.left; Node T2 = x.right; x.right = y; y.left = T2; y.height = max(height(y.left), height(y.right)) + 1; x.height = max(height(x.left), height(x.right)) + 1; return x; ) Node leftRotate(Node x) ( Node y = x.right; Node T2 = y.left; y.left = x; x.right = T2; x.height = max(height(x.left), height(x.right)) + 1; y.height = max(height(y.left), height(y.right)) + 1; return y; ) // Get balance factor of a node int getBalanceFactor(Node N) ( if (N == null) return 0; return height(N.left) - height(N.right); ) // Insert a node Node insertNode(Node node, int item) ( // Find the position and insert the node if (node == null) return (new Node(item)); if (item node.item) node.right = insertNode(node.right, item); else return node; // Update the balance factor of each node // And, balance the tree node.height = 1 + max(height(node.left), height(node.right)); int balanceFactor = getBalanceFactor(node); if (balanceFactor> 1) ( if (item node.left.item) ( node.left = leftRotate(node.left); return rightRotate(node); ) ) if (balanceFactor node.right.item) ( return leftRotate(node); ) else if (item < node.right.item) ( node.right = rightRotate(node.right); return leftRotate(node); ) ) return node; ) Node nodeWithMimumValue(Node node) ( Node current = node; while (current.left != null) current = current.left; return current; ) // Delete a node Node deleteNode(Node root, int item) ( // Find the node to be deleted and remove it if (root == null) return root; if (item root.item) root.right = deleteNode(root.right, item); else ( if ((root.left == null) || (root.right == null)) ( Node temp = null; if (temp == root.left) temp = root.right; else temp = root.left; if (temp == null) ( temp = root; root = null; ) else root = temp; ) else ( Node temp = nodeWithMimumValue(root.right); root.item = temp.item; root.right = deleteNode(root.right, temp.item); ) ) if (root == null) return root; // Update the balance factor of each node and balance the tree root.height = max(height(root.left), height(root.right)) + 1; int balanceFactor = getBalanceFactor(root); if (balanceFactor> 1) ( if (getBalanceFactor(root.left)>= 0) ( return rightRotate(root); ) else ( root.left = leftRotate(root.left); return rightRotate(root); ) ) if (balanceFactor < -1) ( if (getBalanceFactor(root.right) <= 0) ( return leftRotate(root); ) else ( root.right = rightRotate(root.right); return leftRotate(root); ) ) return root; ) void preOrder(Node node) ( if (node != null) ( System.out.print(node.item + " "); preOrder(node.left); preOrder(node.right); ) ) // Print the tree private void printTree(Node currPtr, String indent, boolean last) ( if (currPtr != null) ( System.out.print(indent); if (last) ( System.out.print("R----"); indent += " "; ) else ( System.out.print("L----"); indent += "| "; ) System.out.println(currPtr.item); printTree(currPtr.left, indent, false); printTree(currPtr.right, indent, true); ) ) // Driver code public static void main(String() args) ( AVLTree tree = new AVLTree(); tree.root = tree.insertNode(tree.root, 33); tree.root = tree.insertNode(tree.root, 13); tree.root = tree.insertNode(tree.root, 53); tree.root = tree.insertNode(tree.root, 9); tree.root = tree.insertNode(tree.root, 21); tree.root = tree.insertNode(tree.root, 61); tree.root = tree.insertNode(tree.root, 8); tree.root = tree.insertNode(tree.root, 11); tree.printTree(tree.root, "", true); tree.root = tree.deleteNode(tree.root, 13); System.out.println("After Deletion: "); tree.printTree(tree.root, "", true); ) )

 // AVL tree implementation in C #include #include // Create Node struct Node ( int key; struct Node *left; struct Node *right; int height; ); int max(int a, int b); // Calculate height int height(struct Node *N) ( if (N == NULL) return 0; return N->height; ) int max(int a, int b) ( return (a> b) ? a : b; ) // Create a node struct Node *newNode(int key) ( struct Node *node = (struct Node *) malloc(sizeof(struct Node)); node->key = key; node->left = NULL; node->right = NULL; node->height = 1; return (node); ) // Right rotate struct Node *rightRotate(struct Node *y) ( struct Node *x = y->left; struct Node *T2 = x->right; x->right = y; y->left = T2; y->height = max(height(y->left), height(y->right)) + 1; x->height = max(height(x->left), height(x->right)) + 1; return x; ) // Left rotate struct Node *leftRotate(struct Node *x) ( struct Node *y = x->right; struct Node *T2 = y->left; y->left = x; x->right = T2; x->height = max(height(x->left), height(x->right)) + 1; y->height = max(height(y->left), height(y->right)) + 1; return y; ) // Get the balance factor int getBalance(struct Node *N) ( if (N == NULL) return 0; return height(N->left) - height(N->right); ) // Insert node struct Node *insertNode(struct Node *node, int key) ( // Find the correct position to insertNode the node and insertNode it if (node == NULL) return (newNode(key)); if (key key) node->left = insertNode(node->left, key); else if (key> node->key) node->right = insertNode(node->right, key); else return node; // Update the balance factor of each node and // Balance the tree node->height = 1 + max(height(node->left), height(node->right)); int balance = getBalance(node); if (balance> 1 && key left->key) return rightRotate(node); if (balance node->right->key) return leftRotate(node); if (balance> 1 && key> node->left->key) ( node->left = leftRotate(node->left); return rightRotate(node); ) if (balance < -1 && key right->key) ( node->right = rightRotate(node->right); return leftRotate(node); ) return node; ) struct Node *minValueNode(struct Node *node) ( struct Node *current = node; while (current->left != NULL) current = current->left; return current; ) // Delete a nodes struct Node *deleteNode(struct Node *root, int key) ( // Find the node and delete it if (root == NULL) return root; if (key key) root->left = deleteNode(root->left, key); else if (key> root->key) root->right = deleteNode(root->right, key); else ( if ((root->left == NULL) || (root->right == NULL)) ( struct Node *temp = root->left ? root->left : root->right; if (temp == NULL) ( temp = root; root = NULL; ) else *root = *temp; free(temp); ) else ( struct Node *temp = minValueNode(root->right); root->key = temp->key; root->right = deleteNode(root->right, temp->key); ) ) if (root == NULL) return root; // Update the balance factor of each node and // balance the tree root->height = 1 + max(height(root->left), height(root->right)); int balance = getBalance(root); if (balance> 1 && getBalance(root->left)>= 0) return rightRotate(root); if (balance> 1 && getBalance(root->left) left = leftRotate(root->left); return rightRotate(root); ) if (balance right) <= 0) return leftRotate(root); if (balance right)> 0) ( root->right = rightRotate(root->right); return leftRotate(root); ) return root; ) // Print the tree void printPreOrder(struct Node *root) ( if (root != NULL) ( printf("%d ", root->key); printPreOrder(root->left); printPreOrder(root->right); ) ) int main() ( struct Node *root = NULL; root = insertNode(root, 2); root = insertNode(root, 1); root = insertNode(root, 7); root = insertNode(root, 4); root = insertNode(root, 5); root = insertNode(root, 3); root = insertNode(root, 8); printPreOrder(root); root = deleteNode(root, 3); printf("After deletion: "); printPreOrder(root); return 0; )

 // AVL tree implementation in C++ #include using namespace std; class Node ( public: int key; Node *left; Node *right; int height; ); int max(int a, int b); // Calculate height int height(Node *N) ( if (N == NULL) return 0; return N->height; ) int max(int a, int b) ( return (a> b) ? a : b; ) // New node creation Node *newNode(int key) ( Node *node = new Node(); node->key = key; node->left = NULL; node->right = NULL; node->height = 1; return (node); ) // Rotate right Node *rightRotate(Node *y) ( Node *x = y->left; Node *T2 = x->right; x->right = y; y->left = T2; y->height = max(height(y->left), height(y->right)) + 1; x->height = max(height(x->left), height(x->right)) + 1; return x; ) // Rotate left Node *leftRotate(Node *x) ( Node *y = x->right; Node *T2 = y->left; y->left = x; x->right = T2; x->height = max(height(x->left), height(x->right)) + 1; y->height = max(height(y->left), height(y->right)) + 1; return y; ) // Get the balance factor of each node int getBalanceFactor(Node *N) ( if (N == NULL) return 0; return height(N->left) - height(N->right); ) // Insert a node Node *insertNode(Node *node, int key) ( // Find the correct postion and insert the node if (node == NULL) return (newNode(key)); if (key key) node->left = insertNode(node->left, key); else if (key> node->key) node->right = insertNode(node->right, key); else return node; // Update the balance factor of each node and // balance the tree node->height = 1 + max(height(node->left), height(node->right)); int balanceFactor = getBalanceFactor(node); if (balanceFactor> 1) ( if (key left->key) ( return rightRotate(node); ) else if (key> node->left->key) ( node->left = leftRotate(node->left); return rightRotate(node); ) ) if (balanceFactor node->right->key) ( return leftRotate(node); ) else if (key right->key) ( node->right = rightRotate(node->right); return leftRotate(node); ) ) return node; ) // Node with minimum value Node *nodeWithMimumValue(Node *node) ( Node *current = node; while (current->left != NULL) current = current->left; return current; ) // Delete a node Node *deleteNode(Node *root, int key) ( // Find the node and delete it if (root == NULL) return root; if (key key) root->left = deleteNode(root->left, key); else if (key> root->key) root->right = deleteNode(root->right, key); else ( if ((root->left == NULL) || (root->right == NULL)) ( Node *temp = root->left ? root->left : root->right; if (temp == NULL) ( temp = root; root = NULL; ) else *root = *temp; free(temp); ) else ( Node *temp = nodeWithMimumValue(root->right); root->key = temp->key; root->right = deleteNode(root->right, temp->key); ) ) if (root == NULL) return root; // Update the balance factor of each node and // balance the tree root->height = 1 + max(height(root->left), height(root->right)); int balanceFactor = getBalanceFactor(root); if (balanceFactor> 1) ( if (getBalanceFactor(root->left)>= 0) ( return rightRotate(root); ) else ( root->left = leftRotate(root->left); return rightRotate(root); ) ) if (balanceFactor right) right = rightRotate(root->right); return leftRotate(root); ) ) return root; ) // Print the tree void printTree(Node *root, string indent, bool last) ( if (root != nullptr) ( cout << indent; if (last) ( cout << "R----"; indent += " "; ) else ( cout << "L----"; indent += "| "; ) cout  right, indent, true); ) ) int main() ( Node *root = NULL; root = insertNode(root, 33); root = insertNode(root, 13); root = insertNode(root, 53); root = insertNode(root, 9); root = insertNode(root, 21); root = insertNode(root, 61); root = insertNode(root, 8); root = insertNode(root, 11); printTree(root, "", true); root = deleteNode(root, 13); cout << "After deleting " << endl; printTree(root, "", true); ) 

Complejidades de diferentes operaciones en un árbol AVL

Inserción	Supresión	Buscar
O (log n)	O (log n)	O (log n)

Aplicaciones de árbol AVL

• Para indexar grandes registros en bases de datos
• Para buscar en grandes bases de datos