AVL-træ

I denne vejledning lærer du, hvad et AVL-træ er. Du finder også arbejdseksempler på forskellige operationer udført på et AVL-træ i C, C ++, Java og Python.

AVL-træ er et selvbalancerende binært søgetræ, hvor hvert knudepunkt opretholder ekstra information kaldet en balancefaktor, hvis værdi enten er -1, 0 eller +1.

AVL-træet fik sit navn efter sin opfinder Georgy Adelson-Velsky og Landis.

Balancefaktor

Balancefaktor for en knude i et AVL-træ er forskellen mellem højden af ​​det venstre undertræ og det for det højre undertræ for det knudepunkt.

Balancefaktor = (højde på venstre undertræ - højde på højre undertræ) eller (højde på højre undertræ - højde på venstre undertræ)

Den selvbalancerende egenskab af et avl-træ opretholdes af balancefaktoren. Værdien af ​​balancefaktoren skal altid være -1, 0 eller +1.

Et eksempel på et afbalanceret avl-træ er:

Avl træ

Funktioner på et AVL-træ

Forskellige operationer, der kan udføres på et AVL-træ er:

Rotation af undertrærne i et AVL-træ

I rotationsoperation udskiftes positionerne for noderne i et undertræ.

Der er to typer rotationer:

Venstre rotering

I venstre rotation omdannes arrangementet af knudepunkterne til højre til arrangementerne på venstre knude.

Algoritme

  1. Lad det oprindelige træ være: Venstre rotering
  2. Hvis y har et venstre undertræ, tildeles x som overordnet til det venstre undertræ af y. Tildel x som forælder til venstre undertræ af y
  3. Hvis forælderen til x er NULL, skal du lave y som træets rod.
  4. Ellers hvis x er det venstre barn af p, skal du gøre y som det venstre barn af p.
  5. Ellers tildel y som det rigtige barn på s. Skift overordnet til x til y
  6. Lav y som forælder til x. Tildel y som forælder til x.

Højre rotering

I venstre rotation omdannes arrangementet af knudepunkterne til venstre til arrangementerne på højre knude.

  1. Lad det oprindelige træ være: Indledende træ
  2. Hvis x har et rigtigt undertræ, tildeles y som forælder til det rigtige undertræ af x. Tildel y som forælder til det højre undertræ af x
  3. Hvis forælderen til y er NULL, skal du lave x som træets rod.
  4. Ellers hvis y er det rigtige barn af sin forælder p, skal du oprette x som det rigtige barn af p.
  5. Ellers tildeles x som det venstre barn på s. Tildel forælderen til y som forælder til x.
  6. Lav x som forælder til y. Tildel x som forælder til y

Venstre-højre og højre-venstre rotering

I venstre-højre rotation flyttes arrangementerne først til venstre og derefter til højre.

  1. Gør venstre rotation på xy. Venstre rotering xy
  2. Gør højre rotation på yz. Højre roter zy

I højre-venstre rotation flyttes arrangementerne først til højre og derefter til venstre.

  1. Gør højre rotation på xy. Højre drej xy
  2. Gør venstre rotation på zy. Venstre rotering zy

Algoritme til at indsætte en nyNode

En newNode indsættes altid som en bladknude med en balancefaktor lig med 0.

  1. Lad det oprindelige træ være: Indledende træ til indsættelse
    Lad den node, der skal indsættes, være: Ny node
  2. Gå til den relevante bladknude for at indsætte en ny knude ved hjælp af følgende rekursive trin. Sammenlign newKey med rootKey for det aktuelle træ.
    1. Hvis newKey <rootKey, kaldes indsætningsalgoritmen til venstre undertræ i den aktuelle knude, indtil bladknuden nås.
    2. Ellers hvis newKey> rootKey, kald indsætningsalgoritme på det højre undertræ i det aktuelle knudepunkt, indtil bladknuden nås.
    3. Ellers returner bladNode. Find det sted, der skal indsættes newNode
  3. Sammenlign leafKey opnået fra ovenstående trin med newKey:
    1. Hvis newKey <leafKey, skal du oprette newNode som den venstreChild af leafNode.
    2. Ellers, lav newNode som højreBarn af leafNode. Indsættelse af den nye knude
  4. Opdater balanceFaktor for noderne. Opdatering af balancefaktoren efter indsættelse
  5. Hvis noderne ikke er i balance, skal du balancere noden igen.
    1. Hvis balanceFactor> 1 betyder det, at højden på det venstre undertræ er større end det højre undertræs. Så gør en højre rotation eller venstre-højre rotation
      1. Hvis newNodeKey <leftChildKey skal dreje til højre.
      2. Ellers, drej venstre-højre-rotation. Balancere træet med rotation Balancere træet med rotation
    2. Hvis balanceFactor <-1 betyder det, at højden på det højre undertræ er større end det venstre undertræs. Så gør højre rotation eller højre-venstre rotation
      1. Hvis newNodeKey> rightChildKey skal dreje til venstre.
      2. Ellers, drej højre-venstre-rotation
  6. Det sidste træ er: Endelig afbalanceret træ

Algoritme til at slette en node

En node slettes altid som en bladknude. Efter sletning af en node ændres balancefaktorerne for noderne. For at genbalancere balancefaktoren udføres passende rotationer.

  1. Find nodeToBeDeleted (rekursion bruges til at finde nodeToBeDeleted i koden anvendt nedenfor). Find den node, der skal slettes
  2. Der er tre tilfælde til sletning af en node:
    1. Hvis nodeToBeDeleted er bladnoden (dvs. ikke har noget barn), skal du fjerne nodeToBeDeleted.
    2. Hvis nodeToBeDeleted har et barn, skal du erstatte indholdet af nodeToBeDeleted med barnets. Fjern barnet.
    3. Hvis nodeToBeDeleted har to børn, skal du finde ordren efterfølger w for nodeToBeDeleted (dvs. node med en minimumsværdi af nøgle i det højre undertræ). At finde efterfølgeren
      1. Erstat indholdet af nodeToBeDeleted med det af w. Erstat den knude, der skal slettes
      2. Fjern bladknuden w. Fjern w
  3. Opdater balanceFaktor for noderne. Opdater bf
  4. Ombalancere træet, hvis balancefaktoren for en af ​​noderne ikke er lig med -1, 0 eller 1.
    1. Hvis balanceFaktor for strømNode> 1,
      1. Hvis balanceFactor of leftChild> = 0, skal du dreje til højre. Højre-drej for at balancere træet
      2. Ellers gør venstre-højre rotation.
    2. Hvis balanceFaktor for strømNode <-1,
      1. Hvis balanceFactor of rightChild <= 0, skal du dreje til venstre.
      2. Ellers gør højre-venstre rotation.
  5. Det sidste træ er: Avl-træet endeligt

Python, Java og C / C ++ eksempler

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

Kompleksiteter af forskellige operationer på et AVL-træ

Indskud Sletning Søg
O (log n) O (log n) O (log n)

AVL-træapplikationer

  • Til indeksering af store poster i databaser
  • Til søgning i store databaser

Interessante artikler...