AVL puu

Selles õpetuses saate teada, mis on AVL-puu. Samuti leiate toimivaid näiteid erinevatest toimingutest, mis on tehtud avl-puus C, C ++, Java ja Python.

AVL puu on isetasakaalustuv kahendotsingupuu, milles iga sõlm säilitab lisateavet, mida nimetatakse tasakaaluteguriks, mille väärtus on kas -1, 0 või +1.

AVL puu sai oma nime leiutaja Georgi Adelson-Velsky ja Landise järgi.

Tasakaalutegur

AVL-puu sõlme tasakaalustegur on vahe selle sõlme vasaku ja parema alampuu kõrguse vahel.

Tasakaalukoefitsient = (vasakpoolse alampuu kõrgus - parempoolse alampuu kõrgus) või (parempoolse alampuu kõrgus - vasakpoolse alampuu kõrgus)

Avl-puu isetasakaalustavat omadust hoiab tasakaalu tegur. Tasakaaluteguri väärtus peaks alati olema -1, 0 või +1.

Tasakaalustatud AVL-puu näide on:

Avl puu

Toimingud AVL-puus

AVL-puul saab teha erinevaid toiminguid:

Alampuude pööramine AVL-puus

Pöörlemisoperatsioonis vahetatakse alampuu sõlmede asukohad.

Pöördeid on kahte tüüpi:

Vasakule pööramine

Vasakpoolses pöörlemises muudetakse parempoolsete sõlmede paigutus vasaku sõlme paigutusteks.

Algoritm

  1. Olgu esialgne puu järgmine: pöörake vasakule
  2. Kui y-l on vasak alampuu, määrake x y-i vasaku alampuu vanemaks. Määra x y vasakpoolse alampuu vanemaks
  3. Kui xi vanem on NULL, siis tehke puu juureks y.
  4. Muul juhul, kui x on p p vasak laps, tehke y p vasakpoolseks lapseks.
  5. Muul juhul määrake y p-i õigeks lapseks. Muutke xi vanem y-ks
  6. Tehke y x-i vanemaks. Määra y x-i vanemaks.

Paremale pöörake

Vasakpoolses pöörlemises muudetakse vasakpoolsete sõlmede paigutus parempoolse sõlme paigutusteks.

  1. Olgu algpuu: Algpuu
  2. Kui x-l on parem alampuu, määrake x-i parema alampuu vanemaks y. Määra y x-i parema alampuu vanemaks
  3. Kui y on vanem NULL, siis tehke puu juureks x.
  4. Muul juhul, kui y on oma vanema p õige laps, tehke x p-i õige lapsena.
  5. Muul juhul määrake x vasakule lapsele x. Määrake x vanemaks y vanem.
  6. Tehke y vanemana x. Määrake x vanemaks y

Vasak-parem ja parem-vasak pööramine

Vasakul-paremal pööramisel nihutatakse paigutus kõigepealt vasakule ja seejärel paremale.

  1. Tehke vasakul pööramine xy-l. Vasakul pöörake xy
  2. Tehke parempoolne pöörlemine yz-l. Paremale pöörake zy

Parema ja vasaku pööramise korral nihutatakse seaded kõigepealt paremale ja seejärel vasakule.

  1. Pöörake xy-l paremale. Paremale pöörake xy
  2. Tehke vasak pööramine zy-l. Vasakul pöörake zy

Algoritm uue sõlme sisestamiseks

UusNode sisestatakse alati lehesõlmena, mille tasakaalutegur on võrdne 0-ga.

  1. Olgu algpuu: Algne puu sisestamiseks
    Olgu lisatav sõlm: Uus sõlm
  2. Uute sõlmede sisestamiseks järgmiste rekursiivsete toimingute abil minge sobivale lehesõlmele. Võrdle newKey praeguse puu rootKey-ga.
    1. Kui newKey <rootKey, helistage sisestusalgoritm praeguse sõlme vasakule alampuule, kuni lehesõlm on saavutatud.
    2. Muul juhul, kui newKey> rootKey, helistage sisestamise algoritm praeguse sõlme paremal alampuul kuni lehesõlmeni jõudmiseni.
    3. Muul juhul tagastage leafNode. NewNode'i sisestamiseks asukoha leidmine
  3. Võrrelge ülaltoodud sammudest saadud leafKey funktsiooni newKey:
    1. Kui newKey <leafKey, tehke newNode leheNode leftChild'iks.
    2. Muul juhul tehke newNode leheNode parempoolse lapsena. Uue sõlme sisestamine
  4. Uuenda balanceFactori sõlmed. Tasakaaluteguri värskendamine pärast sisestamist
  5. Kui sõlmed on tasakaalustamata, siis tasakaalustage sõlm uuesti.
    1. Kui balanceFactor> 1, tähendab see, et vasaku alampuu kõrgus on suurem kui parempoolse alampuu kõrgus. Niisiis, tehke parem- või vasakpööret
      1. Kui newNodeKey <leftChildKey pöörab õigesti.
      2. Muul juhul tehke vasak-parem pööret. Puu tasakaalustamine pöörlemisega Puu tasakaalustamine pöörlemisega
    2. Kui balanceFactor <-1, tähendab see, et parema alampuu kõrgus on suurem kui vasaku alampuu kõrgus. Niisiis, tehke parem- või vasakpööret
      1. Kui newNodeKey> rightChildKey teevad vasakpöörde.
      2. Muul juhul tehke parem-vasak pööret
  6. Viimane puu on: Lõplik tasakaalustatud puu

Algoritm sõlme kustutamiseks

Sõlm kustutatakse alati lehesõlmena. Pärast sõlme kustutamist muutuvad sõlmede tasakaalutegurid. Tasakaaluteguri tasakaalustamiseks viiakse läbi sobivad pöörded.

  1. Leidke nodeToBeDeleted (rekursiooni kasutatakse nodeToBeDeleted leidmiseks allpool kasutatud koodist). Kustutatava sõlme asukoht
  2. Sõlme kustutamiseks on kolm juhtumit.
    1. Kui nodeToBeDeleted on lehesõlm (st tal pole ühtegi last), siis eemaldage nodeToBeDeleted.
    2. Kui nodeToBeDeletedil on üks laps, asendage nodeToBeDeleted sisu lapse omaga. Eemaldage laps.
    3. Kui nodeToBeDeletedil on kaks last, leidke nodeToBeDeleted järglane w (st sõlme, mille parempoolses alampuus on võtme minimaalne väärtus). Pärija leidmine
      1. Asendage nodeToBeDeleted sisu w-ga. Asendage kustutatav sõlm
      2. Eemaldage lehesõlm w. Eemaldage w
  3. Uuenda balanceFactori sõlmed. Uuenda bf
  4. Tasakaalustage puu uuesti, kui ühegi sõlme tasakaalutegur ei ole võrdne -1, 0 või 1.
    1. Kui balanceFactor of currentNode> 1,
      1. Kui balanceFactor of leftChild> = 0, pöörake paremale. Puu tasakaalustamiseks paremale pööramine
      2. Muul juhul tehke vasak-parem pööret.
    2. Kui balanceFactor of currentNode <-1,
      1. Kui balanceFactor of rightChild <= 0, tehke vasakpööret.
      2. Muul juhul tehke parem-vasak pööret.
  5. Viimane puu on: Avl puu lõplik

Pythoni, Java ja C / C ++ näited

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

AVL-puu erinevate toimingute keerukus

Sisestamine Kustutamine Otsing
O (log n) O (log n) O (log n)

AVL-i puu rakendused

  • Suurte kirjete indekseerimiseks andmebaasides
  • Suurtest andmebaasidest otsimiseks

Huvitavad Artiklid...