Strom AVL

V tomto tutoriáli sa dozviete, čo je strom avl. Nájdete tiež pracovné príklady rôznych operácií vykonávaných na strome avl v jazykoch C, C ++, Java a Python.

Strom AVL je samovyvažujúci binárny vyhľadávací strom, v ktorom každý uzol uchováva ďalšie informácie nazývané faktor vyváženia, ktorého hodnota je buď -1, 0, alebo +1.

Názov strom AVL dostal svoje meno po vynálezcovi Georgijovi Adelsonovi-Velskom a Landisovi.

Faktor rovnováhy

Faktor rovnováhy uzla v strome AVL je rozdiel medzi výškou ľavého podstromu a výškou pravého podstromu tohto uzla.

Faktor vyváženia = (výška ľavého podstromu - výška pravého podstromu) alebo (výška pravého podstromu - výška ľavého podstromu)

Vlastnosť automatického vyváženia stromu avl je udržiavaná faktorom rovnováhy. Hodnota faktora rovnováhy by mala byť vždy -1, 0 alebo +1.

Príklad vyváženého stromu AVL je:

Avl strom

Operácie na strome AVL

Rôzne operácie, ktoré je možné vykonať na strome AVL, sú:

Otáčanie podstromov v strome AVL

V rotačnej operácii sú polohy uzlov podstromu zamenené.

Existujú dva typy rotácií:

Otočenie doľava

Pri rotácii doľava sa usporiadanie uzlov vpravo transformuje do usporiadania ľavého uzla.

Algoritmus

  1. Počiatočný strom nechajte: Otočiť doľava
  2. Ak má y ľavý podstrom, priraďte x ako rodič ľavého podstromu y. Priraďte x ako rodič ľavého podstromu y
  3. Ak je rodičom x NULL, urobte y ako koreň stromu.
  4. Ak nie je x ľavé dieťa p, urobíme y ako ľavé dieťa p.
  5. Inak priraďte y ako správne dieťa p. Zmeňte nadradenú hodnotu x na hodnotu y
  6. Vytvorte y ako rodiča x. Priraďte y ako rodič x.

Otočiť doprava

Pri rotácii doľava sa usporiadanie uzlov vľavo transformuje do usporiadania v pravom uzle.

  1. Nech je počiatočný strom: Počiatočný strom
  2. Ak má x pravý podstrom, priraďte y ako rodiča pravého podstromu x. Priraďte y ako rodič pravého podstromu x
  3. Ak je rodičom y NULL, urobte x ako koreň stromu.
  4. Pokiaľ nie je y správne dieťa jeho rodiča p, urobme x ako správne dieťa p.
  5. Inak priraďte x ako ľavé dieťa p. Priraďte rodiča y ako rodiča x.
  6. Vytvorte x ako rodič z y. Priraďte x ako rodič y

Otočenie doľava-doprava a doprava-doľava

Pri rotácii zľava-doprava sa usporiadanie najskôr posunie doľava a potom doprava.

  1. Otočte doľava na xy. Otočenie doľava o xy
  2. Urobte rotáciu vpravo na yz. Doprava otočiť zy

Pri pravo-ľavej rotácii sú usporiadania najskôr posunuté doprava a potom doľava.

  1. Otočte doprava na xy. Otočenie doprava o xy
  2. Otočte doľava na zy. Doľava otočiť zy

Algoritmus na vloženie nového uzla

NewNode je vždy vložený ako listový uzol s bilančným faktorom rovným 0.

  1. Počiatočný strom nech je: Počiatočný strom na vloženie
    Nech je vložený uzol : Nový uzol
  2. Prejdite na príslušný uzol listu a vložte nový uzol pomocou nasledujúcich rekurzívnych krokov. Porovnajte newKey s rootKey aktuálneho stromu.
    1. Ak newKey <rootKey, zavolajte algoritmus vkladania na ľavom podstrome aktuálneho uzla, kým sa nedosiahne listový uzol.
    2. Ak nie je newKey> rootKey, zavolajte algoritmus vkladania na pravom podstrome aktuálneho uzla, kým sa nedosiahne listový uzol.
    3. Inak vráťte listNode. Nájdenie umiestnenia na vloženie nového uzla
  3. Porovnajte leafKey získaný z vyššie uvedených krokov s newKey:
    1. Ak newKey <leafKey, urobte newNode ako leftChild z leafNode.
    2. Inak urobte newNode ako rightChild of leafNode. Vkladanie nového uzla
  4. Aktualizovať balanceFactor uzlov. Aktualizácia rovnovážneho faktora po vložení
  5. Ak sú uzly nevyvážené, potom uzol vyvážte znova.
    1. Ak balanceFactor> 1, znamená to, že výška ľavého podstromu je väčšia ako výška pravého podstromu. Urobte teda pravú alebo ľavú rotáciu
      1. Ak newNodeKey <leftChildKey urobte rotáciu vpravo.
      2. Inak robte rotáciu zľava-doprava. Vyvažovanie stromu rotáciou Vyvažovanie stromu rotáciou
    2. Ak balanceFactor <-1, znamená to, že výška pravého podstromu je väčšia ako výška ľavého podstromu. Robte teda pravú alebo ľavú rotáciu
      1. Ak newNodeKey> rightChildKey urobte rotáciu doľava.
      2. Inak robte rotáciu vpravo-vľavo
  6. Konečný strom je: Konečný vyvážený strom

Algoritmus na odstránenie uzla

Uzol sa vždy odstráni ako listový uzol. Po odstránení uzla sa zmenia bilančné faktory uzlov. Aby sa vyvážil vyvážený faktor, uskutočňujú sa vhodné rotácie.

  1. Vyhľadajte nodeToBeDeleted (rekurzia sa používa na nájdenie nodeToBeDeleted v kóde použitom nižšie). Vyhľadanie uzla, ktorý sa má vymazať
  2. Existujú tri prípady odstránenia uzla:
    1. Ak je nodeToBeDeleted listový uzol (tj. Nemá žiadne potomstvo), odstráňte nodeToBeDeleted.
    2. Ak má nodeToBeDeleted jedno dieťa, potom nahraďte obsah nodeToBeDeleted obsahom dieťaťa. Odstráňte dieťa.
    3. Ak má nodeToBeDeleted dve podradené položky, nájdite nasledovného poradia w nodeToBeDeleted (tj. Uzol s minimálnou hodnotou kľúča v pravom podstrome). Hľadanie nástupcu
      1. Nahraďte obsah nodeToBeDeleted obsahom w. Nahraďte uzol, ktorý sa má vymazať
      2. Odstráňte listový uzol w. Odstráňte w
  3. Aktualizovať balanceFactor uzlov. Aktualizácia bf
  4. Znova vyvážte strom, ak sa rovnovážny faktor ktoréhokoľvek z uzlov nerovná -1, 0 alebo 1.
    1. Ak balanceFactor of currentNode> 1,
      1. Ak balanceFactor of leftChild> = 0, urobte pravú rotáciu. Otočenie doprava pre vyváženie stromu
      2. Inak robte rotáciu zľava-doprava.
    2. Ak balanceFactor currentNode <-1,
      1. Ak je balanceFactor rightChild <= 0, urobte rotáciu doľava.
      2. Inak robte rotáciu zľava doprava.
  5. Konečný strom je: Konečný strom Avl

Príklady jazyka Python, Java a 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); )

Zložitosť rôznych operácií na strome AVL

Vloženie Vymazanie Vyhľadávanie
O (log n) O (log n) O (log n)

Aplikácie stromu AVL

  • Na indexovanie veľkých záznamov v databázach
  • Na vyhľadávanie vo veľkých databázach

Zaujímavé články...