AVL stablo

U ovom uputstvu naučit ćete što je avl stablo. Također ćete pronaći radne primjere raznih operacija izvedenih na avl stablu u C, C ++, Java i Python.

AVL stablo je samobalansirajuće binarno stablo pretraživanja u kojem svaki čvor održava dodatne informacije koje se nazivaju faktor ravnoteže čija je vrijednost -1, 0 ili +1.

Drvo AVL dobilo je ime po izumitelju Georgyu Adelson-Velskyu i Landisu.

Faktor ravnoteže

Faktor ravnoteže čvora u AVL stablu razlika je između visine lijevog podstabla i visine desnog podstabla tog čvora.

Faktor ravnoteže = (Visina lijevog podstabla - Visina desnog podstabla) ili (Visina desnog podstabla - Visina lijevog poddreveta)

Svojstvo samobalansiranja avl stabla održava se faktorom ravnoteže. Vrijednost bilansnog faktora uvijek treba biti -1, 0 ili +1.

Primjer uravnoteženog avl stabla je:

Avl stablo

Operacije na AVL stablu

Razne operacije koje se mogu izvesti na AVL stablu su:

Rotiranje podstabala u AVL stablu

U operaciji rotacije, položaji čvorova podstabla izmjenjuju se.

Postoje dvije vrste rotacija:

Rotiraj ulijevo

U rotaciji lijevo, raspored čvorova s ​​desne strane transformira se u raspored na lijevom čvoru.

Algoritam

  1. Neka početno stablo bude: Rotirajte lijevo
  2. Ako y ima lijevo podstablo, dodijelite x kao roditelja lijevog podstabla y. Dodijelite x kao nadređenog lijevog podstabla y
  3. Ako je roditelj x NULL, neka y bude korijen stabla.
  4. Inače ako je x lijevo dijete p, neka y bude lijevo dijete p.
  5. Inače dodijelite y kao pravo dijete p. Promijenite nadređenu x u y
  6. Neka y bude roditelj x-a. Dodijelite y kao roditelja x.

Zakreni udesno

U rotaciji lijevo, raspored čvorova s ​​lijeve strane transformira se u raspored na desnom čvoru.

  1. Neka početno stablo bude: Inicijalno stablo
  2. Ako x ima pravo podstablo, dodijelite y kao roditelja pravog podstabla x. Dodijelite y kao nadređenog desnog podstabla x
  3. Ako je roditelj y NULL, napravite x kao korijen stabla.
  4. Inače ako je y pravo dijete svog roditelja p, neka x bude pravo dijete p.
  5. Inače dodijelite x kao lijevo podređeno dijete str. Dodijelite roditelja y kao roditelja x.
  6. Neka x bude roditelj y-a. Dodijelite x kao roditelja nad y

Rotiranje lijevo-desno i desno-lijevo

U rotaciji lijevo-desno raspored se prvo pomiče ulijevo, a zatim udesno.

  1. Okrećite lijevo na xy. Zakretanje ulijevo xy
  2. Okrećite se desno na yz. Okrenite udesno zy

U rotaciji desno-lijevo, raspored se prvo pomiče udesno, a zatim ulijevo.

  1. Okrećite se desno na xy. Okrenite udesno xy
  2. Okrećite lijevo na zy. Zakreni lijevo zy

Algoritam za umetanje novogČvora

Uvijek se umetne noviČvor kao čvor s faktorom ravnoteže jednakim 0.

  1. Neka početno stablo bude: Inicijalno stablo za umetanje
    Neka čvor koji treba umetnuti bude: Novi čvor
  2. Idite na odgovarajući čvor lista da biste umetnuli novi čvor pomoću sljedećih rekurzivnih koraka. Usporedite newKey s rootKey trenutnog stabla.
    1. Ako je newKey <rootKey, pozovite algoritam za umetanje na lijevom podstablu trenutnog čvora dok se ne postigne lisni čvor.
    2. Inače ako je newKey> rootKey, algoritam za umetanje poziva na desnom podstablu trenutnog čvora dok se ne postigne čvor lista.
    3. Inače, vratite leafNode. Pronalaženje mjesta za umetanje novogNode
  3. Usporedite leafKey dobiven iz gornjih koraka s newKey:
    1. Ako je newKey <leafKey, napravite newNode kao leftChild of leafNode.
    2. Inače, napravi newNode kao desniDijete leafNode. Umetanje novog čvora
  4. Ažuriraj faktor ravnoteže čvorova. Ažuriranje faktora ravnoteže nakon umetanja
  5. Ako su čvorovi neuravnoteženi, ponovno uravnotežite čvor.
    1. Ako je balanceFactor> 1, to znači da je visina lijevog podstabla veća od visine desnog podstabla. Dakle, napravite rotaciju udesno ili ulijevo-udesno
      1. Ako je newNodeKey <leftChildKey, napravite desnu rotaciju.
      2. Inače, vrti rotaciju lijevo-desno. Balansiranje stabla rotacijom Balansiranje stabla rotacijom
    2. Ako je balanceFactor <-1, to znači da je visina desnog podstabla veća od visine lijevog podstabla. Dakle, napravite rotaciju udesno ili udesno-ulijevo
      1. Ako newNodeKey> rightChildKey izvrši rotaciju ulijevo.
      2. Inače, vrti rotaciju desno-lijevo
  6. Konačno stablo je: Konačno uravnoteženo stablo

Algoritam za brisanje čvora

Čvor se uvijek briše kao čvor lista. Nakon brisanja čvora, faktori ravnoteže čvorova mijenjaju se. Kako bi se uravnotežio faktor ravnoteže, izvode se odgovarajuće rotacije.

  1. Pronađite nodeToBeDeleted (rekurzija se koristi za pronalaženje nodeToBeDeleted u kodu koji se koristi dolje). Lociranje čvora za brisanje
  2. Tri su slučaja za brisanje čvora:
    1. Ako je nodeToBeDeleted čvor lista (tj. Nema nijedno dijete), tada uklonite nodeToBeDeleted.
    2. Ako nodeToBeDeleted ima jedno dijete, tada sadržaj nodeToBeDeleted zamijenite sadržajem djeteta. Uklonite dijete.
    3. Ako nodeToBeDeleted ima dvoje djece, pronađite nasljednika w po narudžbi nodeToBeDeleted (tj. Čvor s minimalnom vrijednošću ključa u desnom podstablu). Pronalaženje nasljednika
      1. Zamijenite sadržaj nodeToBeDeleted sa sadržajem w. Zamijenite čvor koji želite izbrisati
      2. Uklonite lisni čvor w. Uklonite w
  3. Ažuriraj faktor ravnoteže čvorova. Ažuriranje bf
  4. Rebalansirajte stablo ako faktor ravnoteže bilo kojeg od čvorova nije jednak -1, 0 ili 1.
    1. Ako je balanceFactor trenutnog Čvora> 1,
      1. Ako je balanceFactor leftChild> = 0, napravite rotaciju udesno. Okrenite se udesno za uravnoteženje stabla
      2. Inače vrte rotaciju lijevo-desno.
    2. Ako je balanceFactor trenutnogNode <-1,
      1. Ako je balanceFactor rightChild <= 0, napravite rotaciju ulijevo.
      2. Inače vrte rotaciju desno-lijevo.
  5. Konačno stablo je: Avl stablo konačno

Primjeri Pythona, Java i C / C ++

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

Složenost različitih operacija na AVL stablu

Umetanje Brisanje traži
O (zapisnik n) O (zapisnik n) O (zapisnik n)

Aplikacije AVL stabla

  • Za indeksiranje velikih zapisa u bazama podataka
  • Za pretraživanje u velikim bazama podataka

Zanimljivi članci...