AVL Tree

В этом руководстве вы узнаете, что такое avl-дерево. Кроме того, вы найдете рабочие примеры различных операций, выполняемых с деревом avl на языках C, C ++, Java и Python.

Дерево AVL - это самобалансирующееся двоичное дерево поиска, в котором каждый узел поддерживает дополнительную информацию, называемую коэффициентом баланса, значение которого равно -1, 0 или +1.

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

Фактор баланса

Фактор баланса узла в дереве 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

Алгоритм вставки нового узла

NewNode всегда вставляется как листовой узел с коэффициентом баланса, равным 0.

  1. Пусть начальным деревом будет: Начальное дерево для вставки
    Пусть вставляемый узел будет: Новый узел
  2. Перейдите к соответствующему конечному узлу, чтобы вставить новый узел, выполнив следующие рекурсивные шаги. Сравните newKey с rootKey текущего дерева.
    1. Если newKey <rootKey, вызвать алгоритм вставки в левом поддереве текущего узла, пока не будет достигнут конечный узел.
    2. В противном случае, если newKey> rootKey, вызвать алгоритм вставки в правом поддереве текущего узла, пока не будет достигнут конечный узел.
    3. В противном случае верните leafNode. Поиск места для вставки нового узла
  3. Сравните leafKey, полученный на вышеуказанных шагах, с newKey:
    1. Если newKey <leafKey, сделайте newNode как leftChild для leafNode.
    2. В противном случае сделайте newNode как rightChild для 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 имеет двух дочерних элементов, найдите последовательного преемника w для nodeToBeDeleted (т.е. узел с минимальным значением ключа в правом поддереве). В поисках преемника
      1. Замените содержимое nodeToBeDeleted содержимым w. Замените удаляемый узел
      2. Удалите листовой узел w. Удалить w
  3. Обновите balanceFactor узлов. Обновить bf
  4. Перебалансируйте дерево, если коэффициент баланса любого из узлов не равен -1, 0 или 1.
    1. Если balanceFactor of currentNode> 1,
      1. Если balanceFactor leftChild> = 0, повернуть вправо. Поверните вправо для балансировки дерева
      2. Иначе сделайте вращение влево-вправо.
    2. Если balanceFactor of 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 (журнал n) O (журнал n) O (журнал n)

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

  • Для индексации больших записей в базах данных
  • Для поиска в больших базах данных

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