AVL-träd

I denna handledning lär du dig vad ett avl-träd är. Du hittar också arbetsexempel på olika operationer som utförs på ett AVL-träd i C, C ++, Java och Python.

AVL-träd är ett självbalanserande binärt sökträd där varje nod upprätthåller extra information som kallas en balansfaktor vars värde är antingen -1, 0 eller +1.

AVL-trädet fick sitt namn efter uppfinnaren Georgy Adelson-Velsky och Landis.

Balansfaktor

Balansfaktorn för en nod i ett AVL-träd är skillnaden mellan höjden på det vänstra underträdet och höjden på det högra underträdet i den noden.

Balansfaktor = (höjd på vänster subtree - höjd på höger subtree) eller (höjd på höger subtree - höjd på vänster subtree)

Den självbalanserande egenskapen hos ett AVL-träd upprätthålls av balansfaktorn. Värdet på balansfaktorn ska alltid vara -1, 0 eller +1.

Ett exempel på ett balanserat AVL-träd är:

Avl träd

Funktioner på ett AVL-träd

Olika operationer som kan utföras på ett AVL-träd är:

Rotera underträd i ett AVL-träd

Vid rotationsoperation byts positionerna för noder i ett underträd.

Det finns två typer av rotationer:

Vänster rotera

I vänsterrotation omvandlas arrangemanget av noderna till höger till arrangemangen på den vänstra noden.

Algoritm

  1. Låt det ursprungliga trädet vara: Vänster rotera
  2. Om y har ett vänster underträd, tilldela x som förälder till det vänstra underträdet till y. Tilldela x som överordnad till vänster underträd av y
  3. Om föräldern till x är NULL, gör y som trädets rot.
  4. Annars om x är det vänstra barnet till p, gör y som det vänstra barnet till p.
  5. Annan tilldela y som rätt barn på s. Ändra föräldern till x till den för y
  6. Gör y som förälder till x. Tilldela y som förälder till x.

Höger rotera

I vänsterrotation omvandlas arrangemanget av noderna till vänster till arrangemangen på höger nod.

  1. Låt det ursprungliga trädet vara: Initialt träd
  2. Om x har rätt underträd, tilldela y som förälder till rätt underträd till x. Tilldela y som förälder till rätt underträd av x
  3. Om föräldern till y är NULL, gör x som roten till trädet.
  4. Annars om y är rätt barn till sin förälder p, gör x som rätt barn till p.
  5. Annars tilldelas x som det vänstra barnet på s. Tilldela föräldern till y som förälder till x.
  6. Gör x som förälder till y. Tilldela x som förälder till y

Vänster-höger och höger-vänster-rotering

I vänster-höger rotation flyttas arrangemangen först åt vänster och sedan till höger.

  1. Gör vänsterrotation på xy. Vänster rotera xy
  2. Gör rätt rotation på yz. Höger rotera zy

I höger-vänster rotation flyttas arrangemangen först till höger och sedan till vänster.

  1. Gör rätt rotation på xy. Höger rotera xy
  2. Gör vänsterrotation på zy. Vänster rotera zy

Algoritm för att infoga en newNode

En newNode infogas alltid som en bladnod med balansfaktor lika med 0.

  1. Låt det ursprungliga trädet vara: Initialt träd för insättning
    Låt noden som ska infogas vara: Ny nod
  2. Gå till lämplig bladnod för att infoga en nyNode med följande rekursiva steg. Jämför newKey med rootKey för det aktuella trädet.
    1. Om newKey <rootKey, anropa insättningsalgoritmen på den vänstra underträdet för den aktuella noden tills bladnoden nås.
    2. Annars om newKey> rootKey, anropsinföringsalgoritm på den högra underträdet för aktuell nod tills bladnoden nås.
    3. Annars, returbladNod. Hitta platsen för att infoga newNode
  3. Jämför leafKey från ovanstående steg med newKey:
    1. Om newKey <leafKey, gör newNode som leftChild of leafNode.
    2. Annars, gör newNode som rättBarn av leafNode. Infoga den nya noden
  4. Uppdatera balansFaktor för noderna. Uppdaterar balansfaktorn efter införandet
  5. Om noderna är obalanserade, balansera sedan noden igen.
    1. Om balansFaktor> 1 betyder det att höjden på vänster underträd är större än höger underträd. Så gör en höger rotation eller vänster-höger rotation
      1. Om newNodeKey <leftChildKey gör rätt rotation.
      2. Annars, gör vänster-höger rotation. Balansera trädet med rotation Balansera trädet med rotation
    2. Om balansFaktor <-1 betyder det att höjden på det högra underträdet är större än det vänstra underträdet. Så gör höger rotation eller höger-vänster rotation
      1. Om newNodeKey> rightChildKey gör vänsterrotation.
      2. Annars, gör höger-vänster rotation
  6. Det sista trädet är: Slutligt balanserat träd

Algoritm för att radera en nod

En nod raderas alltid som en bladnod. Efter att ha raderat en nod ändras balansfaktorerna för noderna. För att balansera balansfaktorn utförs lämpliga rotationer.

  1. Leta upp nodeToBeDeleted (rekursion används för att hitta nodeToBeDeleted i koden som används nedan). Hitta noden som ska raderas
  2. Det finns tre fall för att radera en nod:
    1. Om nodeToBeDeleted är bladnoden (dvs. har inget barn), ta bort nodToBeDeleted.
    2. Om nodeToBeDeleted har ett barn, ersätt sedan innehållet i nodeToBeDeleted med det för barnet. Ta bort barnet.
    3. Om nodeToBeDeleted har två barn, leta reda på efterföljaren w för nodeToBeDeleted (dvs. nod med ett minimivärde på nyckeln i rätt underträd). Hitta efterträdaren
      1. Ersätt innehållet i nodeToBeDeleted med innehållet i w. Ersätt noden som ska raderas
      2. Ta bort bladnoden w. Ta bort w
  3. Uppdatera balansFaktor för noderna. Uppdatera bf
  4. Ombalansera trädet om balansfaktorn för någon av noderna inte är lika med -1, 0 eller 1.
    1. If balanceFactor of currentNode> 1,
      1. Om balanceFactor of leftChild> = 0, gör rätt rotation. Högerrotera för att balansera trädet
      2. Annars gör du vänster-höger rotation.
    2. If balanceFactor of currentNode <-1,
      1. Om balanceFactor of rightChild <= 0, gör vänsterrotation.
      2. Annars gör du höger-vänster rotation.
  5. Det sista trädet är: Avl tree final

Python, Java och C / C ++ exempel

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

Komplexiteter av olika funktioner på ett AVL-träd

Införande Radering Sök
O (log n) O (log n) O (log n)

AVL-trädapplikationer

  • För indexering av stora poster i databaser
  • För sökning i stora databaser

Intressanta artiklar...