AVL Tree

I denne opplæringen lærer du hva et avl-tre er. Du finner også arbeidseksempler på forskjellige operasjoner utført på et AVL-tre i C, C ++, Java og Python.

AVL-treet er et selvbalanserende binært søketre der hver node opprettholder ekstra informasjon kalt en balansefaktor hvis verdi er enten -1, 0 eller +1.

AVL-treet fikk navnet sitt etter oppfinneren Georgy Adelson-Velsky og Landis.

Balansefaktor

Balansefaktoren til en node i et AVL-tre er forskjellen mellom høyden på det venstre undertreet og det til det høyre undertreet til den noden.

Balansefaktor = (Høyde på venstre undertre - Høyde på høyre undertre) eller (Høyde på høyre undertre - Høyde på venstre undertre)

Den selvbalanserende egenskapen til et avl-tre opprettholdes av balansefaktoren. Verdien av balansefaktor skal alltid være -1, 0 eller +1.

Et eksempel på et balansert avl-tre er:

Avl treet

Operasjoner på et AVL-tre

Ulike operasjoner som kan utføres på et AVL-tre er:

Rotere undertrærne i et AVL-tre

I rotasjonsoperasjon byttes posisjonene til nodene til et undertre.

Det er to typer rotasjoner:

Venstre rotasjon

I venstre rotasjon blir arrangementet av nodene til høyre transformert til arrangementene på venstre node.

Algoritme

  1. La det første treet være: Venstre rotasjon
  2. Hvis y har et venstre undertre, tildeler du x som overordnet til venstre undertre av y. Tilordne x som overordnet til venstre undertreet til y
  3. Hvis foreldrene til x er NULL, lager du y som roten til treet.
  4. Ellers hvis x er det venstre barnet til p, gjør du y som det venstre barnet til p.
  5. Annen tildeler du y som det rette barnet til s. Endre overordnet til x til det til y
  6. Gjør y som forelder til x. Tilordne y som overordnet til x.

Høyre roter

I venstre rotasjon blir arrangementet av nodene til venstre transformert til arrangementene på høyre node.

  1. La det første treet være: Initialt tre
  2. Hvis x har riktig undertre, tilordner du y som overordnet til riktig undertre av x. Tilordne y som overordnet til høyre undertre av x
  3. Hvis foreldrene til y er NULL, lager du x som roten til treet.
  4. Ellers hvis y er det rette barnet til sin forelder p, gjør x som det rette barnet til p.
  5. Annen tildel x som venstre barn på s. Tilordne foreldrene til y som overordnede til x.
  6. Lag x som forelder til y. Tilordne x som overordnet til y

Venstre-høyre og høyre-venstre rotasjon

I venstre-høyre rotasjon blir arrangementene først forskjøvet til venstre og deretter til høyre.

  1. Gjør venstre rotasjon på xy. Venstre rotasjon xy
  2. Gjør riktig rotasjon på yz. Høyre roter zy

I høyre-venstre rotasjon flyttes arrangementene først til høyre og deretter til venstre.

  1. Gjør riktig rotasjon på xy. Høyre roter xy
  2. Gjør venstre rotasjon på zy. Venstre rotasjon zy

Algoritme for å sette inn en nyNode

En newNode settes alltid inn som en bladnode med balansefaktor lik 0.

  1. La det innledende treet være: Innledende tre for innsetting
    La noden som skal settes inn være: Ny node
  2. Gå til riktig bladnode for å sette inn en nyNode ved hjelp av følgende rekursive trinn. Sammenlign newKey med rootKey for det nåværende treet.
    1. Hvis newKey <rootKey, kan du ringe innsettingsalgoritmen på venstre undertrær for gjeldende node til bladnoden er nådd.
    2. Ellers hvis newKey> rootKey, ring innleggingsalgoritme på høyre undertrær for gjeldende node til bladnoden er nådd.
    3. Annet, returbladNode. Finne stedet for å sette inn newNode
  3. Sammenlign leafKey hentet fra trinnene ovenfor med newKey:
    1. Hvis newKey <leafKey, lag newNode som venstreChild of leafNode.
    2. Ellers, lag newNode som riktigBarn av leafNode. Sette inn den nye noden
  4. Oppdater balanseFaktor for nodene. Oppdaterer balansefaktoren etter innsetting
  5. Hvis nodene er ubalanserte, balanserer du noden på nytt.
    1. Hvis balanceFactor> 1, betyr det at høyden på venstre undertre er større enn høyre undertre. Så, gjør en høyre rotasjon eller venstre-høyre rotasjon
      1. Hvis newNodeKey <leftChildKey gjør høyre rotasjon.
      2. Ellers, gjør venstre-høyre rotasjon. Balansere treet med rotasjon Balansere treet med rotasjon
    2. Hvis balanceFactor <-1, betyr det at høyden på høyre undertre er større enn den til venstre undertre. Så gjør høyre rotasjon eller høyre-venstre rotasjon
      1. Hvis newNodeKey> rightChildKey gjør venstre rotasjon.
      2. Ellers, gjør høyre-venstre rotasjon
  6. Det siste treet er: Endelig balansert tre

Algoritme for å slette en node

En node blir alltid slettet som en bladnode. Etter å ha slettet en node, blir balansefaktorene til nodene endret. For å balansere balansefaktoren utføres passende rotasjoner.

  1. Finn nodeToBeDeleted (rekursjon brukes til å finne nodeToBeDeleted i koden som brukes nedenfor). Finne noden som skal slettes
  2. Det er tre tilfeller for å slette en node:
    1. Hvis nodeToBeDeleted er bladnoden (dvs. ikke har noe barn), fjern deretter nodeToBeDeleted.
    2. Hvis nodeToBeDeleted har ett barn, erstatt innholdet i nodeToBeDeleted med det til barnet. Fjern barnet.
    3. Hvis nodeToBeDeleted har to barn, finner du ordren etterfølgeren w til nodeToBeDeleted (dvs. node med en minimumsverdi på nøkkelen i høyre undertrær). Å finne etterfølgeren
      1. Erstatt innholdet til nodeToBeDeleted med innholdet i w. Erstatt noden som skal slettes
      2. Fjern bladnoden w. Fjern m
  3. Oppdater balanseFaktor for nodene. Oppdater bf
  4. Balansere treet på nytt hvis balansefaktoren til noen av nodene ikke er lik -1, 0 eller 1.
    1. Hvis balanceFactor of currentNode> 1,
      1. Hvis balanceFactor of leftChild> = 0, gjør høyre rotasjon. Høyre-roter for å balansere treet
      2. Ellers gjør venstre-høyre rotasjon.
    2. Hvis balanceFactor of currentNode <-1,
      1. Hvis balanceFactor of rightChild <= 0, gjør venstre rotasjon.
      2. Ellers gjør høyre-venstre rotasjon.
  5. Det siste treet er: Avl treet endelig

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 av forskjellige operasjoner på et AVL-tre

Innsetting Sletting Søk
O (log n) O (log n) O (log n)

AVL-treapplikasjoner

  • For indeksering av store poster i databaser
  • For søking i store databaser

Interessante artikler...