AVL koks

Šajā apmācībā jūs uzzināsiet, kas ir avl koks. Jūs atradīsit arī dažādu operāciju piemērus, kas veikti ar avl koku C, C ++, Java un Python.

AVL koks ir pašbalansējošs binārs meklēšanas koks, kurā katrs mezgls uztur papildu informāciju, ko sauc par līdzsvara koeficientu, kura vērtība ir vai nu -1, 0 vai +1.

AVL koks savu nosaukumu ieguvis pēc izgudrotāja Georgija Adelsona-Velska un Landisa.

Bilances faktors

AVL koka mezgla līdzsvara koeficients ir starpība starp šī mezgla kreisās un labās apakškokas augstumu.

Atlikuma koeficients = (kreisās apakškārtas augstums - labās apakškoka augstums) vai (labās apakškārtas augstums - kreisās apakštes augstums)

Avl koka pašbalansējošo īpašību uztur līdzsvara koeficients. Bilances faktora vērtībai vienmēr jābūt -1, 0 vai +1.

Sabalansēta AVL koka piemērs ir:

Avl koks

Darbības ar AVL koku

Dažādas darbības, kuras var veikt ar AVL koku, ir:

Apakškoku pagriešana AVL kokā

Rotācijas darbībā apakškoku mezglu pozīcijas tiek apmainītas.

Ir divu veidu rotācijas:

Pagriezt pa kreisi

Pagriežot pa kreisi, mezglu izvietojums labajā pusē tiek pārveidots par kreisā mezgla izvietojumiem.

Algoritms

  1. Ļaujiet sākotnējam kokam būt: Pagriezieties pa kreisi
  2. Ja y ir kreisā apakškoku, piešķiriet x kā y kreisās apakškoka vecāku. Piešķiriet x kā vecumu y kreisajai apakškokai
  3. Ja x vecāks ir NULL, izveidojiet y kā koka sakni.
  4. Citādi, ja x ir p kreisais bērns, izveidojiet y kā p kreiso bērnu.
  5. Citādi piešķiriet y kā pareizo p. Mainiet x vecāku uz y
  6. Izveidojiet y kā x vecāku. Piešķiriet y kā x vecāku.

Pagriezt pa labi

Pagriežot pa kreisi, mezglu izvietojums pa kreisi tiek pārveidots par labā mezgla izvietojumiem.

  1. Ļaujiet sākotnējam kokam būt: Sākotnējam kokam
  2. Ja x ir labais apakškoks, piešķiriet y kā x labās apakškokas vecāku. Piešķiriet y kā x labās apakškopa vecāku
  3. Ja y vecāks ir NULL, izveidojiet x kā koka sakni.
  4. Citādi, ja y ir vecāka p pareizais bērns, izveidojiet x kā p pareizais bērns.
  5. Cits piešķir x kā kreiso bērnu p. Piešķiriet y vecāku kā x vecāku.
  6. Izveidojiet x kā y vecāku. Piešķiriet x kā y vecāku

Pagriezt pa kreisi-pa labi un pa labi-pa kreisi

Pagriežot pa kreisi un pa labi, kārtojums vispirms tiek pārvietots pa kreisi un pēc tam pa labi.

  1. Veiciet kreiso pagriezienu pa xy. Pagriezieties pa kreisi xy
  2. Veiciet labo pagriezienu uz yz. Pagrieziet pa labi zy

Labajā un kreisajā rotācijā kārtība vispirms tiek pārvietota pa labi un pēc tam pa kreisi.

  1. Veiciet labo pagriezienu uz xy. Pagrieziet pa labi xy
  2. Veiciet kreiso rotāciju zy. Pa kreisi pagriezt zy

Algoritms, lai ievietotu jaunuNode

NewNode vienmēr tiek ievietots kā lapu mezgls ar bilances koeficientu, kas vienāds ar 0.

  1. Lai sākotnējais koks būtu: Sākotnējais koks ievietošanai
    Ļaujiet ievietojamajam mezglam būt: Jauns mezgls
  2. Dodieties uz atbilstošo lapu mezglu, lai ievietotu newNode, izmantojot šādas rekursīvās darbības. Salīdziniet newKey ar pašreizējā koka rootKey.
    1. Ja newKey <rootKey, izsauciet ievietošanas algoritmu pašreizējā mezgla kreisajā apakškokā, līdz tiek sasniegts lapu mezgls.
    2. Else if newKey> rootKey, izsauciet ievietošanas algoritmu pašreizējā mezgla labajā apakškokā, līdz tiek sasniegts lapu mezgls.
    3. Cits, atgriezties leafNode. Atrašanās vietas atrašana, lai ievietotu newNode
  3. Salīdziniet leafKey, kas iegūts no iepriekš minētajām darbībām, ar newKey:
    1. Ja newKey <leafKey, izveidojiet newNode kā leafNode leftChild.
    2. Citādi izveidojiet newNode kā leafNode kā rightChild. Jaunā mezgla ievietošana
  4. Atjaunināt balanceFactor no mezgliem. Atlikuma faktora atjaunināšana pēc ievietošanas
  5. Ja mezgli nav līdzsvaroti, tad līdzsvarojiet mezglu.
    1. Ja balanceFactor> 1, tas nozīmē, ka kreisās apakškokas augstums ir lielāks nekā labās apakškoka augstums. Tātad, veiciet labo vai kreiso-labo pagriezienu
      1. Ja newNodeKey <leftChildKey veic labo pagriešanu.
      2. Citādi veiciet kreiso un labo pagriezienu. Koka līdzsvarošana ar rotāciju Koka līdzsvarošana ar griešanos
    2. Ja balanceFactor <-1, tas nozīmē, ka labās apakškokas augstums ir lielāks nekā kreisā apakškoka augstums. Tātad, veiciet rotāciju pa labi vai pa kreisi
      1. Ja newNodeKey> rightChildKey veic rotāciju pa kreisi.
      2. Citādi veiciet labās un kreisās puses rotāciju
  6. Pēdējais koks ir: Galīgais līdzsvarotais koks

Mezgla dzēšanas algoritms

Mezgls vienmēr tiek izdzēsts kā lapu mezgls. Pēc mezgla dzēšanas mezglu līdzsvara faktori tiek mainīti. Lai līdzsvarotu līdzsvara koeficientu, tiek veiktas piemērotas rotācijas.

  1. Atrodiet nodeToBeDeleted (rekursija tiek izmantota, lai zemāk izmantotajā kodā atrastu nodeToBeDeleted). Dzēšamā mezgla atrašana
  2. Mezgla dzēšanai ir trīs gadījumi:
    1. Ja nodeToBeDeleted ir lapu mezgls (ti, tam nav neviena bērna), tad noņemiet nodeToBeDeleted.
    2. Ja nodeToBeDeleted ir viens bērns, tad nodeToBeDeleted saturu aizstāj ar bērna saturu. Noņemiet bērnu.
    3. Ja nodeToBeDeleted ir divi bērni, atrodiet nodeToBeDeleted pēcteci w (ti, mezglu ar atslēgas minimālo vērtību labajā apakškokā). Pēcteces atrašana
      1. NodeToBeDeleted saturu aizstāj ar w. Nomainiet dzēšamo mezglu
      2. Noņemiet lapu mezglu w. Noņemt w
  3. Atjaunināt balanceFactor no mezgliem. Atjaunināt bf
  4. Pārbalansējiet koku, ja jebkura mezgla bilances koeficients nav vienāds ar -1, 0 vai 1.
    1. Ja bilanceFactor of currentNode> 1,
      1. Ja balanceFactor of leftChild> = 0, veiciet labo pagriešanu. Pagrieziet pa labi, lai līdzsvarotu koku
      2. Citādi veiciet kreiso un labo rotāciju.
    2. Ja bilanceFactor of currentNode <-1,
      1. Ja balanceFactor of rightChild <= 0, veiciet kreiso pagriešanu.
      2. Citādi veiciet labās un kreisās puses rotāciju.
  5. Galīgais koks ir: Avl tree final

Python, Java un C / C ++ piemēri

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

Dažādu AVL koka darbību sarežģītība

Ievietošana Dzēšana Meklēt
O (log n) O (log n) O (log n)

AVL koka lietojumprogrammas

  • Lielu ierakstu indeksēšanai datubāzēs
  • Meklēšanai lielās datu bāzēs

Interesanti raksti...