Arborele AVL

În acest tutorial, veți afla ce este un copac avl. De asemenea, veți găsi exemple de lucru ale diferitelor operații efectuate pe un copac avl în C, C ++, Java și Python.

Arborele AVL este un arbore de căutare binar auto-echilibrat în care fiecare nod menține informații suplimentare numite un factor de echilibru a cărui valoare este -1, 0 sau +1.

Arborele AVL și-a luat numele după inventatorul său Georgy Adelson-Velsky și Landis.

Factor de echilibru

Factorul de echilibru al unui nod dintr-un arbore AVL este diferența dintre înălțimea subarborelui stâng și cea a subarborelui drept al acelui nod.

Factor de echilibru = (Înălțimea subarborelui stâng - Înălțimea subarborelui drept) sau (Înălțimea subarborelui drept - Înălțimea subarborelui stâng)

Proprietatea de echilibrare a unui copac avl este menținută de factorul de echilibru. Valoarea factorului de echilibru trebuie să fie întotdeauna -1, 0 sau +1.

Un exemplu de arbore avl echilibrat este:

Copac Avl

Operații pe un arbore AVL

Diferite operații care pot fi efectuate pe un arbore AVL sunt:

Rotirea subarborilor într-un arbore AVL

În operațiunea de rotație, pozițiile nodurilor unui subarbore sunt schimbate.

Există două tipuri de rotații:

Rotire stânga

În rotația la stânga, dispunerea nodurilor din dreapta este transformată în aranjamentele din nodul stâng.

Algoritm

  1. Lăsați arborele inițial să fie: Rotiți la stânga
  2. Dacă y are un subarboroc din stânga, atribuiți x ca părinte al subarborelui din stânga al lui y. Atribuiți x ca părinte al subarborelui stâng al lui y
  3. Dacă părintele lui x este NULL, faceți y ca rădăcină a copacului.
  4. Altfel dacă x este copilul stâng al lui p, faceți y ca copilul stâng al lui p.
  5. În caz contrar, atribuiți-vă y drept copilul potrivit din p. Schimbați părintele lui x cu cel al lui y
  6. Faceți-l pe y ca părinte al lui x. Alocați y ca părinte al lui x.

Rotire dreapta

În rotația stânga, dispunerea nodurilor din stânga este transformată în aranjamentele nodului din dreapta.

  1. Arborele inițial să fie: Arborele inițial
  2. Dacă x are un subarborodrept, atribuiți y ca părinte al subarborelui drept al lui x. Alocați y ca părinte al subarborelui drept al lui x
  3. Dacă părintele lui y este NULL, faceți x ca rădăcină a copacului.
  4. Altfel dacă y este copilul potrivit al părintelui său p, faceți x ca copilul potrivit al lui p.
  5. Altfel atribuiți x ca copil stâng al pag. Atribuiți părintele lui y ca părinte al lui x.
  6. Faceți x ca părinte al lui y. Atribuiți x ca părinte al lui y

Rotire stânga-dreapta și dreapta-stânga

În rotația stânga-dreapta, aranjamentele sunt mai întâi deplasate spre stânga și apoi spre dreapta.

  1. Faceți rotația la stânga pe xy. Rotire stânga xy
  2. Faceți rotația corectă pe yz. Rotiți dreapta zy

În rotația dreapta-stânga, aranjamentele sunt mai întâi deplasate spre dreapta și apoi spre stânga.

  1. Faceți rotația corectă pe xy. Rotiți dreapta xy
  2. Faceți rotația la stânga pe zy. Rotiți stânga zy

Algoritm pentru a insera un newNode

Un nou nod este întotdeauna inserat ca nod frunză cu factor de echilibru egal cu 0.

  1. Fie arborele inițial să fie: Arborele inițial pentru inserare
    Fie nodul de inserat să fie: Nod nou
  2. Mergeți la nodul frunzei corespunzător pentru a insera un nou nod folosind pașii recursivi următori. Comparați newKey cu rootKey din arborele curent.
    1. Dacă newKey <rootKey, apelați algoritmul de inserare din subarborele din stânga al nodului curent până când nodul frunzei este atins.
    2. Altfel, dacă newKey> rootKey, apelați algoritmul de inserare în subarborele din dreapta al nodului curent până când nodul frunzei este atins.
    3. Altfel, întoarce leafNode. Găsirea locației pentru a insera newNode
  3. Comparați leafKey obținut din pașii de mai sus cu newKey:
    1. Dacă newKey <leafKey, faceți newNode ca leftChild al leafNode.
    2. Altfel, faceți NewNode drept RightChild of leafNode. Se introduce noul nod
  4. Actualizați echilibrul Factorul nodurilor. Actualizarea factorului de echilibru după inserare
  5. Dacă nodurile sunt dezechilibrate, atunci reechilibrează nodul.
    1. Dacă balanceFactor> 1, înseamnă că înălțimea subarborelui stâng este mai mare decât cea a subarborelui drept. Deci, faceți o rotație dreaptă sau rotație stânga-dreapta
      1. Dacă newNodeKey <leftChildKey face rotația corectă.
      2. Altfel, faceți rotație stânga-dreapta. Echilibrarea arborelui cu rotație Echilibrarea arborelui cu rotația
    2. Dacă balanceFactor <-1, înseamnă că înălțimea subarborelui drept este mai mare decât cea a subarborelui stâng. Deci, faceți rotație dreaptă sau rotație dreapta-stânga
      1. Dacă newNodeKey> rightChildKey face rotația la stânga.
      2. Altfel, faceți rotația dreapta-stânga
  6. Arborele final este: Arborele final echilibrat

Algoritm pentru a șterge un nod

Un nod este întotdeauna șters ca nod frunză. După ștergerea unui nod, factorii de echilibru ai nodurilor se modifică. Pentru a reechilibra factorul de echilibru, se efectuează rotații adecvate.

  1. Localizați nodeToBeDeleted (recursivitatea este utilizată pentru a găsi nodeToBeDeleted în codul folosit mai jos). Localizarea nodului de șters
  2. Există trei cazuri pentru ștergerea unui nod:
    1. Dacă nodeToBeDeleted este nodul frunzei (adică nu are niciun copil), atunci eliminați nodeToBeDeleted.
    2. Dacă nodeToBeDeleted are un singur copil, atunci înlocuiți conținutul nodeToBeDeleted cu cel al copilului. Scoateți copilul.
    3. Dacă nodeToBeDeleted are doi copii, găsiți succesorul inorder w al nodeToBeDeleted (adică nod cu o valoare minimă a cheii din subarborele din dreapta). Găsirea succesorului
      1. Înlocuiți conținutul nodeToBeDeleted cu cel al w. Înlocuiți nodul de șters
      2. Îndepărtați nodul frunzei w. Eliminați w
  3. Actualizați echilibrul Factorul nodurilor. Actualizați bf
  4. Reechilibrați arborele dacă factorul de echilibru al oricărui nod nu este egal cu -1, 0 sau 1.
    1. Dacă balanceFactor of currentNode> 1,
      1. Dacă balanceFactor of leftChild> = 0, faceți rotația dreaptă. Rotiți dreapta pentru echilibrarea copacului
      2. Altfel faceți rotația stânga-dreapta.
    2. Dacă balanceFactor of currentNode <-1,
      1. Dacă balanceFactor of rightChild <= 0, faceți rotația la stânga.
      2. Altfel faceți rotația dreapta-stânga.
  5. Arborele final este: Avl tree final

Exemple Python, 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); )

Complexități ale diferitelor operațiuni pe un arbore AVL

Inserare Ștergere Căutare
O (jurnal n) O (jurnal n) O (jurnal n)

Aplicații de copac AVL

  • Pentru indexarea înregistrărilor mari în baze de date
  • Pentru căutare în baze de date mari

Articole interesante...