Дерево AVL

У цьому підручнику ви дізнаєтеся, що таке авл-дерево. Крім того, ви знайдете робочі приклади різних операцій, виконуваних над 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 як правильну дочірню сторінку с. Змініть батьківський 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

Алгоритм вставки новогоНода

Новий Вузол завжди вставляється як листовий вузол з коефіцієнтом балансу, рівним 0.

  1. Нехай початкове дерево буде: Початкове дерево для вставки
    Нехай вузол, який потрібно вставити, буде: Новий вузол
  2. Перейдіть до відповідного листового вузла, щоб вставити newNode, використовуючи наступні рекурсивні кроки. Порівняйте 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. Оновити баланс фактора вузлів. Оновлення коефіцієнта балансу після вставки
  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 w з nodeToBeDeleted (тобто. Вузол з мінімальним значенням ключа в правому піддереві). Пошук наступника
      1. Замініть вміст nodeToBeDeleted на вміст w. Підставте вузол, який потрібно видалити
      2. Видалити листовий вузол w. Видалити w
  3. Оновити баланс фактора вузлів. Оновлення bf
  4. Збалансуйте дерево, якщо коефіцієнт балансу будь-якого з вузлів не дорівнює -1, 0 або 1.
    1. Якщо balanceFactor поточногоNode> 1,
      1. Якщо balanceFactor leftChild> = 0, виконайте обертання праворуч. Поверніть праворуч для балансування дерева
      2. В іншому випадку робіть обертання вліво-вправо.
    2. Якщо balanceFactor поточногоNode <-1,
      1. Якщо balanceFactor rightChild <= 0, виконайте обертання ліворуч.
      2. В іншому випадку робіть обертання вправо-вліво.
  5. Остаточне дерево: Avl tree final

Приклади 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 (журнал n) O (журнал n) O (журнал n)

Програми дерева AVL

  • Для індексації великих записів у базах даних
  • Для пошуку у великих базах даних

Цікаві статті...