AVL Tree

Neste tutorial, você aprenderá o que é uma árvore avl. Além disso, você encontrará exemplos de trabalho de várias operações realizadas em uma árvore avl em C, C ++, Java e Python.

A árvore AVL é uma árvore de busca binária de autobalanceamento em que cada nó mantém informações extras chamadas fator de equilíbrio, cujo valor é -1, 0 ou +1.

A árvore AVL recebeu o nome de seu inventor Georgy Adelson-Velsky e Landis.

Fator de equilíbrio

O fator de equilíbrio de um nó em uma árvore AVL é a diferença entre a altura da subárvore esquerda e a da subárvore direita desse nó.

Fator de equilíbrio = (altura da subárvore esquerda - altura da subárvore direita) ou (altura da subárvore direita - altura da subárvore esquerda)

A propriedade de auto-equilíbrio de uma árvore avl é mantida pelo fator de equilíbrio. O valor do fator de equilíbrio deve ser sempre -1, 0 ou +1.

Um exemplo de árvore avl balanceada é:

Árvore Avl

Operações em uma árvore AVL

Várias operações que podem ser realizadas em uma árvore AVL são:

Girando as subárvores em uma árvore AVL

Na operação de rotação, as posições dos nós de uma subárvore são trocadas.

Existem dois tipos de rotação:

Girar para a esquerda

Na rotação para a esquerda, o arranjo dos nós à direita é transformado no arranjo do nó esquerdo.

Algoritmo

  1. Deixe a árvore inicial ser: Girar para a esquerda
  2. Se y tiver uma subárvore esquerda, atribua x como o pai da subárvore esquerda de y. Atribuir x como o pai da subárvore esquerda de y
  3. Se o pai de x for NULL, faça y como a raiz da árvore.
  4. Do contrário, se x é o filho esquerdo de p, torne y o filho esquerdo de p.
  5. Caso contrário, atribua y como o filho certo de p. Mude o pai de x para o de y
  6. Faça y como o pai de x. Atribua y como o pai de x.

Girar para a direita

Na rotação para a esquerda, o arranjo dos nós à esquerda é transformado no arranjo do nó direito.

  1. Seja a árvore inicial: Árvore inicial
  2. Se x tiver uma subárvore direita, atribua y como o pai da subárvore direita de x. Atribuir y como o pai da subárvore direita de x
  3. Se o pai de y for NULL, faça x como a raiz da árvore.
  4. Do contrário, se y é o filho certo de seu pai p, torne x o filho certo de p.
  5. Caso contrário, atribua x como o filho esquerdo de p. Atribua o pai de y como o pai de x.
  6. Faça x como o pai de y. Atribuir x como o pai de y

Rotação esquerda-direita e direita-esquerda

Na rotação esquerda-direita, os arranjos são primeiro deslocados para a esquerda e depois para a direita.

  1. Faça a rotação para a esquerda em xy. Girar para a esquerda xy
  2. Faça a rotação correta em yz. Girar para a direita

Na rotação direita-esquerda, os arranjos são primeiro deslocados para a direita e depois para a esquerda.

  1. Faça a rotação correta em xy. Rotação xy para a direita
  2. Faça a rotação para a esquerda em zy. Girar para a esquerda zy

Algoritmo para inserir um novo nó

Um newNode é sempre inserido como um nó folha com fator de equilíbrio igual a 0.

  1. Seja a árvore inicial: Árvore inicial para inserção
    Seja o nó a ser inserido: Novo nó
  2. Vá para o nó folha apropriado para inserir um newNode usando as seguintes etapas recursivas. Compare newKey com rootKey da árvore atual.
    1. Se newKey <rootKey, chamar o algoritmo de inserção na subárvore esquerda do nó atual até que o nó folha seja alcançado.
    2. Caso contrário, se newKey> rootKey, chame o algoritmo de inserção na subárvore direita do nó atual até que o nó folha seja alcançado.
    3. Caso contrário, retorne leafNode. Encontrar a localização para inserir newNode
  3. Compare leafKey obtido nas etapas acima com newKey:
    1. Se newKey <leafKey, torne newNode como leftChild de leafNode.
    2. Caso contrário, torne newNode como rightChild de leafNode. Inserindo o novo nó
  4. Atualize balanceFactor dos nós. Atualizando o fator de equilíbrio após a inserção
  5. Se os nós estiverem desequilibrados, rebalanceie o nó.
    1. Se balanceFactor> 1, significa que a altura da subárvore esquerda é maior do que a da subárvore direita. Então, faça uma rotação direita ou rotação esquerda-direita
      1. Se newNodeKey <leftChildKey gire para a direita.
      2. Caso contrário, faça rotação esquerda-direita. Balanceando a árvore com rotação Balanceando a árvore com rotação
    2. Se balanceFactor <-1, significa que a altura da subárvore direita é maior do que a da subárvore esquerda. Então, faça rotação direita ou rotação direita-esquerda
      1. Se newNodeKey> rightChildKey gire para a esquerda.
      2. Caso contrário, faça rotação direita-esquerda
  6. A árvore final é: Árvore final balanceada

Algoritmo para excluir um nó

Um nó é sempre excluído como um nó folha. Depois de excluir um nó, os fatores de equilíbrio dos nós são alterados. Para reequilibrar o fator de equilíbrio, rotações adequadas são realizadas.

  1. Localize nodeToBeDeleted (a recursão é usada para localizar nodeToBeDeleted no código usado abaixo). Localizando o nó a ser excluído
  2. Existem três casos para excluir um nó:
    1. Se nodeToBeDeleted for o nó folha (ou seja, não tiver nenhum filho), remova nodeToBeDeleted.
    2. Se nodeToBeDeleted tiver um filho, substitua o conteúdo de nodeToBeDeleted pelo do filho. Remova a criança.
    3. Se nodeToBeDeleted tiver dois filhos, encontre o sucessor de ordem w de nodeToBeDeleted (isto é, nó com um valor mínimo de chave na subárvore direita). Encontrando o sucessor
      1. Substitua o conteúdo de nodeToBeDeleted pelo de w. Substitua o nó a ser excluído
      2. Remova o nó folha w. Remover w
  3. Atualize balanceFactor dos nós. Atualizar bf
  4. Rebalanceie a árvore se o fator de equilíbrio de qualquer um dos nós não for igual a -1, 0 ou 1.
    1. Se balanceFactor de currentNode> 1,
      1. Se balanceFactor of leftChild> = 0, faça a rotação para a direita. Gire para a direita para equilibrar a árvore
      2. Do contrário, faça a rotação esquerda-direita.
    2. Se balanceFactor de currentNode <-1,
      1. Se balanceFactor of rightChild <= 0, faça a rotação para a esquerda.
      2. Do contrário, faça a rotação direita-esquerda.
  5. A árvore final é: Avl tree final

Exemplos de Python, Java e 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); )

Complexidades de diferentes operações em uma árvore AVL

Inserção Eliminação Pesquisa
O (log n) O (log n) O (log n)

Aplicativos AVL Tree

  • Para indexar grandes registros em bancos de dados
  • Para pesquisar em grandes bancos de dados

Artigos interessantes...