AVL дърво

В този урок ще научите какво е авл дърво. Също така ще намерите работни примери за различни операции, извършени върху авл дърво в C, C ++, Java и Python.

AVL дървото е самобалансиращо се двоично дърво за търсене, в което всеки възел поддържа допълнителна информация, наречена балансов фактор, чиято стойност е -1, 0 или +1.

Дървото AVL получи името си след изобретателя си Георги Аделсън-Велски и Ландис.

Баланс фактор

Баланс фактор на възел в AVL дърво е разликата между височината на лявото поддърво и тази на дясното поддърво на този възел.

Балансов фактор = (Височина на лявото поддърво - Височина на дясното поддърво) или (Височина на дясното поддърво - Височина на лявото поддърво)

Собствеността на самобалансиране на avl дърво се поддържа от фактора баланс. Стойността на балансовия фактор винаги трябва да бъде -1, 0 или +1.

Пример за балансирано avl дърво е:

Авл дърво

Операции върху AVL дърво

Различни операции, които могат да бъдат извършени върху AVL дърво са:

Завъртане на поддърветата в AVL дърво

При операция на въртене позициите на възлите на поддърво се обменят.

Има два вида ротации:

Въртене наляво

При ляво въртене разположението на възлите вдясно се трансформира в разположението на левия възел.

Алгоритъм

  1. Нека първоначалното дърво е: Въртене наляво
  2. Ако y има ляво поддърво, задайте x като родител на лявото поддърво на y. Задайте x като родител на лявото поддърво на y
  3. Ако родителят на x е NULL, направете y като корен на дървото.
  4. В противен случай, ако x е лявото дете на p, направете y като лявото дете на p.
  5. В противен случай задайте y като правилното дете на p. Променете родителя на x на този на y
  6. Направете y като родител на x. Задайте y като родител на x.

Завъртане надясно

При ляво въртене разположението на възлите вляво се трансформира в разположението на десния възел.

  1. Нека първоначалното дърво да бъде: Начално дърво
  2. Ако x има дясно поддърво, задайте y като родител на дясното поддърво на x. Задайте y като родител на дясното поддърво на x
  3. Ако родителят на y е NULL, направете x като корен на дървото.
  4. В противен случай, ако y е правилното дете на своя родител p, направете x като правилното дете на p.
  5. В противен случай задайте x като ляво дете на p. Задайте родителя на y като родител на x.
  6. Направете x като родител на y. Задайте x като родител на y

Завъртане наляво-надясно и надясно-наляво

При въртене наляво-надясно подредбите първо се изместват наляво и след това надясно.

  1. Направете въртене наляво на xy. Въртене наляво xy
  2. Направете дясна ротация на yz. Завъртете надясно zy

При въртене надясно-наляво подредбите първо се изместват надясно и след това наляво.

  1. Направете дясна ротация на xy. Завъртете надясно xy
  2. Направете въртене наляво на zy. Въртене наляво zy

Алгоритъм за вмъкване на новNode

Нов възел винаги се вмъква като листен възел с балансов фактор, равен на 0.

  1. Нека първоначалното дърво е: Първоначално дърво за вмъкване
    Нека възелът, който трябва да бъде вмъкнат, е: Нов възел
  2. Отидете до съответния листен възел, за да вмъкнете нов възел, като използвате следните рекурсивни стъпки. Сравнете newKey с rootKey на текущото дърво.
    1. Ако newKey <rootKey, извикайте алгоритъма за вмъкване в лявото поддърво на текущия възел, докато се достигне листният възел.
    2. В противен случай ако newKey> rootKey, извикайте алгоритъма за вмъкване в дясното поддърво на текущия възел, докато се достигне листният възел.
    3. В противен случай върнете leafNode. Намиране на местоположението за вмъкване на newNode
  3. Сравнете leafKey, получен от горните стъпки, с newKey:
    1. Ако newKey <leafKey, направете newNode като leftChild of leafNode.
    2. Иначе направете newNode като rightChild of leafNode. Вмъкване на новия възел
  4. Актуализирайте balanceFactor на възлите. Актуализиране на балансовия фактор след вмъкване
  5. Ако възлите са небалансирани, ребалансирайте възела.
    1. Ако balanceFactor> 1, това означава, че височината на лявото поддърво е по-голяма от тази на дясното поддърво. Така че, направете ротация надясно или наляво-надясно
      1. Ако newNodeKey <leftChildKey направете дясно въртене.
      2. В противен случай направете въртене наляво-надясно. Балансиране на дървото с въртене Балансиране на дървото с въртене
    2. Ако balanceFactor <-1, това означава, че височината на дясното поддърво е по-голяма от тази на лявото поддърво. Така че, направете въртене надясно или дясно-ляво
      1. Ако newNodeKey> rightChildKey направете ляво завъртане.
      2. В противен случай направете дясно-ляво завъртане
  6. Крайното дърво е: Крайно балансирано дърво

Алгоритъм за изтриване на възел

Възел винаги се изтрива като листен възел. След изтриване на възел факторите на баланса на възлите се променят. За да се балансира фактора на баланса, се извършват подходящи ротации.

  1. Намерете nodeToBeDeleted (рекурсията се използва за намиране на nodeToBeDeleted в кода, използван по-долу). Намиране на възела за изтриване
  2. Има три случая за изтриване на възел:
    1. Ако nodeToBeDeleted е листният възел (т.е. няма дете), тогава премахнете nodeToBeDeleted.
    2. Ако nodeToBeDeleted има едно дете, заместете съдържанието на nodeToBeDeleted с това на детето. Премахнете детето.
    3. Ако nodeToBeDeleted има две деца, намерете наследника inorder на nodeToBeDeleted (т.е. възел с минимална стойност на ключа в дясното поддърво). Намиране на наследник
      1. Заместете съдържанието на nodeToBeDeleted с това на w. Заместете възела, който ще бъде изтрит
      2. Премахнете листния възел w. Премахнете w
  3. Актуализирайте balanceFactor на възлите. Актуализиране bf
  4. Повторно балансирайте дървото, ако коефициентът на баланс на някой от възлите не е равен на -1, 0 или 1.
    1. Ако balanceFactor на currentNode> 1,
      1. Ако balanceFactor на leftChild> = 0, направете дясно въртене. Завъртане надясно за балансиране на дървото
      2. В противен случай въртете наляво-надясно.
    2. Ако balanceFactor на currentNode <-1,
      1. Ако balanceFactor на rightChild <= 0, направете ляво въртене.
      2. В противен случай направете дясно-ляво завъртане.
  5. Крайното дърво е: Avl дърво окончателно

Примери за Python, Java и 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); )

Сложността на различните операции на AVL дърво

Вмъкване Изтриване Търсене
O (log n) O (log n) O (log n)

Приложения на AVL Tree

  • За индексиране на големи записи в бази данни
  • За търсене в големи бази данни

Интересни статии...