AVL-boom

In deze tutorial leer je wat een avl-boom is. Ook vindt u werkvoorbeelden van verschillende bewerkingen die worden uitgevoerd op een avl-structuur in C, C ++, Java en Python.

AVL-boom is een zelfbalancerende binaire zoekboom waarin elk knooppunt extra informatie bijhoudt, een balansfactor genaamd, waarvan de waarde -1, 0 of +1 is.

AVL Tree dankt zijn naam aan zijn uitvinder Georgy Adelson-Velsky en Landis.

Evenwichtsfactor

De balansfactor van een knoop in een AVL-boom is het verschil tussen de hoogte van de linker substructuur en die van de rechter substructuur van dat knooppunt.

Evenwichtsfactor = (hoogte van linker subboom - hoogte van rechter subboom) of (hoogte van rechter subboom - hoogte van linker subboom)

De zelfbalancerende eigenschap van een avl-boom wordt gehandhaafd door de balansfactor. De waarde van de balansfactor moet altijd -1, 0 of +1 zijn.

Een voorbeeld van een gebalanceerde avl-boom is:

Avl Tree

Bewerkingen op een AVL-structuur

Verschillende bewerkingen die kunnen worden uitgevoerd op een AVL-structuur zijn:

De substructuren in een AVL-structuur roteren

Bij rotatie worden de posities van de knooppunten van een substructuur verwisseld.

Er zijn twee soorten rotaties:

Links draaien

Bij rotatie naar links wordt de opstelling van de knooppunten aan de rechterkant omgezet in de opstelling op het linkerknooppunt.

Algoritme

  1. Laat de eerste boom zijn: linksom draaien
  2. Als y een linker substructuur heeft, wijs dan x toe als de ouder van de linker substructuur van y. Wijs x toe als de ouder van de linker substructuur van y
  3. Als de ouder van x is NULL, maak dan y als de wortel van de boom.
  4. Anders, als x het linkerkind van p is, maak dan y als het linkerkind van p.
  5. Wijs y anders toe als het juiste kind van p. Verander de ouder van x in die van y
  6. Maak y als de ouder van x. Wijs y toe als de ouder van x.

Rechts draaien

Bij rotatie naar links wordt de opstelling van de knooppunten aan de linkerkant omgezet in de opstelling op het rechterknooppunt.

  1. Laat de eerste boom zijn: Eerste boom
  2. Als x een rechter substructuur heeft, wijs dan y toe als de ouder van de rechter substructuur van x. Wijs y toe als de ouder van de rechter substructuur van x
  3. Als de ouder van y is NULL, maak dan x als de wortel van de boom.
  4. Anders, als y het juiste kind is van zijn ouder p, maak dan x als het juiste kind van p.
  5. Wijs anders x toe als het linkerkind van p. Wijs de ouder van y toe als de ouder van x.
  6. Maak x als de ouder van y. Wijs x toe als de ouder van y

Links-rechts en rechts-links draaien

Bij links-rechts rotatie worden de arrangementen eerst naar links en vervolgens naar rechts verschoven.

  1. Draai naar links op xy. Links draaien xy
  2. Draai naar rechts op yz. Draai naar rechts

Bij rechts-links draaien worden de arrangementen eerst naar rechts en vervolgens naar links verschoven.

  1. Draai naar rechts op xy. Rechts draaien xy
  2. Draai naar links op zy. Links draaien zy

Algoritme om een ​​newNode in te voegen

Een newNode wordt altijd ingevoegd als een leaf-knoop met balansfactor gelijk aan 0.

  1. Laat de initiële boom zijn: Initiële boom voor invoeging
    Laat het in te voegen knooppunt zijn: Nieuw knooppunt
  2. Ga naar het juiste leaf-knooppunt om een ​​newNode in te voegen met behulp van de volgende recursieve stappen. Vergelijk newKey met rootKey van de huidige boomstructuur.
    1. Als newKey <rootKey, roep het invoegalgoritme aan op de linker substructuur van het huidige knooppunt totdat het leaf-knooppunt is bereikt.
    2. Anders, als newKey> rootKey, roep het invoegalgoritme aan op de rechter substructuur van het huidige knooppunt totdat het leaf-knooppunt is bereikt.
    3. Anders retourneert u leafNode. De locatie zoeken om newNode in te voegen
  3. Vergelijk leafKey verkregen uit de bovenstaande stappen met newKey:
    1. Als newKey <leafKey, maak newNode aan als leftChild van leafNode.
    2. Anders maakt u newNode als rightChild of leafNode. Het nieuwe knooppunt invoegen
  4. Update balanceFactor van de knooppunten. Bijwerken van de balansfactor na inbrengen
  5. Als de knooppunten onevenwichtig zijn, moet u het knooppunt opnieuw in evenwicht brengen.
    1. Als balanceFactor> 1, betekent dit dat de hoogte van de linker substructuur groter is dan die van de rechter substructuur. Dus draai naar rechts of links-rechts
      1. Als newNodeKey <leftChildKey draai naar rechts.
      2. Anders draai je links-rechts. Balanceren van de boom met rotatie Balanceren van de boom met rotatie
    2. Als balanceFactor <-1, betekent dit dat de hoogte van de rechter substructuur groter is dan die van de linker substructuur. Dus draai naar rechts of rechts-links
      1. Als newNodeKey> rightChildKey linksom draaien.
      2. Anders draai je rechts-links
  6. De laatste boom is: Eindgebalanceerde boom

Algoritme om een ​​knooppunt te verwijderen

Een knooppunt wordt altijd verwijderd als een bladknooppunt. Na het verwijderen van een knoop worden de balansfactoren van de knooppunten gewijzigd. Om de balansfactor opnieuw in evenwicht te brengen, worden geschikte rotaties uitgevoerd.

  1. Zoek nodeToBeDeleted (recursie wordt gebruikt om nodeToBeDeleted te vinden in de onderstaande code). Lokaliseren van het knooppunt dat moet worden verwijderd
  2. Er zijn drie gevallen voor het verwijderen van een knooppunt:
    1. Als nodeToBeDeleted het bladknooppunt is (dat wil zeggen heeft geen kind), verwijder dan nodeToBeDeleted.
    2. Als nodeToBeDeleted één kind heeft, vervangt u de inhoud van nodeToBeDeleted door die van het kind. Verwijder het kind.
    3. Als nodeToBeDeleted twee kinderen heeft, zoek dan de involgorde opvolger w van nodeToBeDeleted (dwz knooppunt met een minimumwaarde van key in de rechter substructuur). De opvolger vinden
      1. Vervang de inhoud van nodeToBeDeleted door die van w. Vervang het te verwijderen knooppunt
      2. Verwijder de bladknoop w. Verwijder w
  3. Update balanceFactor van de knooppunten. Update bf
  4. Breng de structuur opnieuw in evenwicht als de balansfactor van een van de knooppunten niet gelijk is aan -1, 0 of 1.
    1. Als balanceFactor van currentNode> 1,
      1. Als balanceFactor van leftChild> = 0, draai dan naar rechts. Rechtsom draaien om de boom in evenwicht te houden
      2. Anders draai je links-rechts.
    2. Als balanceFactor van currentNode <-1,
      1. Als balanceFactor of rightChild <= 0, draai dan naar links.
      2. Anders draai je rechts-links.
  5. De laatste boom is: Avl tree final

Python, Java en C / C ++ voorbeelden

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

Complexiteit van verschillende bewerkingen op een AVL-structuur

Invoeging Verwijdering Zoeken
O (logboek n) O (logboek n) O (logboek n)

AVL Tree-toepassingen

  • Voor het indexeren van grote records in databases
  • Voor het zoeken in grote databases

Interessante artikelen...