Strom AVL

V tomto výukovém programu se dozvíte, co je strom AVL. Najdete také pracovní příklady různých operací prováděných se stromem avl v jazycích C, C ++, Java a Python.

Strom AVL je samovyvažující binární vyhledávací strom, ve kterém každý uzel udržuje další informace zvané faktor vyvážení, jehož hodnota je buď -1, 0 nebo +1.

Název stromu AVL dostal své jméno podle vynálezce Georgy Adelsona-Velského a Landise.

Faktor rovnováhy

Faktor vyvážení uzlu ve stromu AVL je rozdíl mezi výškou levého podstromu a výškou pravého podstromu daného uzlu.

Faktor vyvážení = (výška levého podstromu - výška pravého podstromu) nebo (výška pravého podstromu - výška levého podstromu)

Vlastnost samovyvažování stromu avl je udržována faktorem rovnováhy. Hodnota faktoru rovnováhy by měla být vždy -1, 0 nebo +1.

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

Avl strom

Operace na stromě AVL

Různé operace, které lze provést na stromě AVL, jsou:

Otáčení podstromů ve stromu AVL

V rotační operaci jsou polohy uzlů podstromu zaměňovány.

Existují dva typy rotací:

Otočit doleva

Při otáčení doleva je uspořádání uzlů vpravo transformováno do uspořádání v levém uzlu.

Algoritmus

  1. Nechte počáteční strom být: Otočit doleva
  2. Pokud má y levý podstrom, přiřaďte x jako rodiče levého podstromu y. Přiřaďte x jako rodiče levého podstromu y
  3. Pokud je rodičem x NULL, udělejte y jako kořen stromu.
  4. Jinak pokud x je levé dítě p, udělejte y jako levé dítě p.
  5. Jinak přiřaďte y jako správné dítě p. Změňte nadřazenou hodnotu x na hodnotu y
  6. Vytvořte y jako rodiče x. Přiřaďte y jako nadřazený prvek x.

Otočit doprava

Při otáčení doleva je uspořádání uzlů vlevo transformováno do uspořádání v pravém uzlu.

  1. Nechte počáteční strom být: Počáteční strom
  2. Pokud má x pravý podstrom, přiřaďte y jako rodiče pravého podstromu x. Přiřaďte y jako rodiče pravého podstromu x
  3. Pokud je rodičem y NULL, udělejte x jako kořen stromu.
  4. Jinak, pokud je y správným dítětem jeho rodiče p, udělejte x jako správné dítě p.
  5. Jinak přiřaďte x jako levé dítě p. Přiřaďte rodiče y jako rodiče x.
  6. Udělej x jako rodič y. Přiřaďte x jako nadřazený prvek y

Otočení zleva doprava a doprava doleva

Při rotaci zleva doprava se uspořádání nejprve posune doleva a poté doprava.

  1. Otočte doleva na xy. Otočit doleva xy
  2. Proveďte správnou rotaci na yz. Otočit doprava zy

Při rotaci zprava doleva se uspořádání nejprve posune doprava a poté doleva.

  1. Proveďte správnou rotaci na xy. Otočit doprava xy
  2. Proveďte rotaci doleva na zy. Otočit doleva zy

Algoritmus pro vložení nového uzlu

NewNode je vždy vložen jako listový uzel s faktorem rovnováhy rovným 0.

  1. Nechte počáteční strom: Počáteční strom pro vložení
    Nechte vložený uzel : Nový uzel
  2. Přejděte do příslušného uzlu listu a vložte nový uzel pomocí následujících rekurzivních kroků. Porovnejte newKey s rootKey aktuálního stromu.
    1. Pokud newKey <rootKey, zavolejte algoritmus vložení na levém podstromu aktuálního uzlu, dokud nebude dosažen uzel listu.
    2. Jinak pokud newKey> rootKey, zavolejte algoritmus vložení na pravém podstromu aktuálního uzlu, dokud nebude dosažen uzel listu.
    3. Jinak vraťte listNode. Nalezení umístění pro vložení newNode
  3. Porovnejte listKey získaný z výše uvedených kroků s newKey:
    1. Pokud newKey <leafKey, udělejte newNode jako leftChild z leafNode.
    2. Jinak udělejte newNode jako rightChild z leafNode. Vkládání nového uzlu
  4. Aktualizujte balanceFactor uzlů. Aktualizace bilančního faktoru po vložení
  5. Pokud jsou uzly nevyvážené, proveďte opětovné vyvážení uzlu.
    1. Pokud balanceFactor> 1, znamená to, že výška levého podstromu je větší než výška pravého podstromu. Proveďte tedy pravou nebo levou pravou rotaci
      1. Pokud newNodeKey <leftChildKey proveďte rotaci vpravo.
      2. Jinak proveďte rotaci zleva doprava. Vyvažování stromu rotací Vyvažování stromu rotací
    2. Pokud balanceFactor <-1, znamená to, že výška pravého podstromu je větší než výška levého podstromu. Proveďte tedy pravou nebo levou rotaci
      1. Pokud newNodeKey> rightChildKey proveďte rotaci doleva.
      2. Jinak proveďte rotaci zprava doleva
  6. Konečný strom je: Konečný vyvážený strom

Algoritmus pro odstranění uzlu

Uzel je vždy odstraněn jako uzel listu. Po odstranění uzlu se změní faktory rovnováhy uzlů. Za účelem vyvážení vyváženého faktoru se provádějí vhodné rotace.

  1. Vyhledejte nodeToBeDeleted (rekurze se používá k vyhledání nodeToBeDeleted v kódu použitém níže). Nalezení uzlu, který má být odstraněn
  2. Existují tři případy odstranění uzlu:
    1. Pokud nodeToBeDeleted je listový uzel (tj. Nemá žádné podřízené), pak odeberte nodeToBeDeleted.
    2. Pokud má nodeToBeDeleted jedno podřízené, pak obsah nodeToBeDeleted nahraďte obsahem podřízeného. Vyjměte dítě.
    3. Pokud má nodeToBeDeleted dvě podřízené položky, najděte následného pořadí w nodeToBeDeleted (tj. Uzel s minimální hodnotou klíče v pravém podstromu). Hledání nástupce
      1. Nahraďte obsah nodeToBeDeleted obsahem w. Nahraďte uzel, který má být odstraněn
      2. Odstraňte uzel listu w. Odstranit w
  3. Aktualizujte balanceFactor uzlů. Aktualizovat bf
  4. Znovu vyvážte strom, pokud se faktor vyvážení některého z uzlů nerovná -1, 0 nebo 1.
    1. Pokud balanceFactor of currentNode> 1,
      1. Pokud balanceFactor of leftChild> = 0, proveďte pravou rotaci. Otočení doprava pro vyvážení stromu
      2. Jinak proveďte rotaci zleva doprava.
    2. Pokud balanceFactor of currentNode <-1,
      1. Pokud je balanceFactor rightChild <= 0, proveďte rotaci doleva.
      2. Jinak proveďte rotaci zprava doleva.
  5. Konečný strom je: Konečný strom Avl

Python, Java a C / C ++ příklady

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); )

Složitost různých operací na stromě AVL

Vložení Vymazání Vyhledávání
O (log n) O (log n) O (log n)

Aplikace AVL Tree

  • Pro indexování velkých záznamů v databázích
  • Pro vyhledávání ve velkých databázích

Zajímavé články...