Drzewo AVL

W tym samouczku dowiesz się, czym jest drzewo AVL. Znajdziesz również działające przykłady różnych operacji wykonywanych na drzewie AVL w językach C, C ++, Java i Python.

Drzewo AVL to samo równoważące się drzewo wyszukiwania binarnego, w którym każdy węzeł przechowuje dodatkowe informacje zwane współczynnikiem równowagi, którego wartość wynosi -1, 0 lub +1.

Drzewo AVL otrzymało swoją nazwę po swoim wynalazcy Georgy Adelson-Velsky i Landis.

Współczynnik równowagi

Współczynnik równowagi węzła w drzewie AVL to różnica między wysokością lewego poddrzewa a wysokości prawego poddrzewa tego węzła.

Współczynnik równowagi = (Wysokość lewego poddrzewa - Wysokość prawego poddrzewa) lub (Wysokość prawego poddrzewa - Wysokość lewego poddrzewa)

Właściwość równoważenia się drzewa AVL jest utrzymywana przez współczynnik równowagi. Wartość współczynnika równowagi powinna zawsze wynosić -1, 0 lub +1.

Przykładem zrównoważonego drzewa AVL jest:

Avl Tree

Operacje na drzewie AVL

Różne operacje, które można wykonać na drzewie AVL to:

Obracanie poddrzew w drzewie AVL

Podczas operacji rotacji pozycje węzłów poddrzewa są zamieniane.

Istnieją dwa rodzaje obrotów:

Obrót w lewo

Przy rotacji w lewo rozmieszczenie węzłów po prawej stronie jest przekształcane w układy na lewym węźle.

Algorytm

  1. Niech początkowe drzewo będzie: Obrót w lewo
  2. Jeśli y ma lewe poddrzewo, przypisz x jako rodzica lewego poddrzewa y. Przypisz x jako rodzica lewego poddrzewa y
  3. Jeśli rodzicem x jest NULL, utwórz y jako korzeń drzewa.
  4. W przeciwnym razie, jeśli x jest lewym dzieckiem p, zrób y jako lewe dziecko p.
  5. W przeciwnym razie przypisz y jako prawe dziecko p. Zmień rodzica x na rodzica y
  6. Uczyń y jako rodzic x. Przypisz y jako rodzica x.

Obrót w prawo

Przy rotacji w lewo rozmieszczenie węzłów po lewej stronie jest przekształcane w układy w węźle prawym.

  1. Niech początkowe drzewo będzie: Drzewo początkowe
  2. Jeśli x ma prawe poddrzewo, przypisz y jako rodzica prawego poddrzewa x. Przypisz y jako rodzica prawego poddrzewa x
  3. Jeśli rodzicem y jest NULL, utwórz x jako korzeń drzewa.
  4. W przeciwnym razie, jeśli y jest właściwym dzieckiem swojego rodzica p, uczyń x jako prawe dziecko p.
  5. W przeciwnym razie przypisz x jako lewe dziecko p. Przypisz rodzica y jako rodzica x.
  6. Niech x będzie rodzicem y. Przypisz x jako rodzica y

Obrót w lewo-w prawo i w prawo-w lewo

W rotacji lewo-prawo aranżacje są najpierw przesuwane w lewo, a następnie w prawo.

  1. Wykonaj obrót w lewo na xy. Obrót w lewo xy
  2. Wykonaj prawy obrót na yz. Obróć w prawo zy

W rotacji prawo-lewo aranżacje są najpierw przesuwane w prawo, a następnie w lewo.

  1. Wykonaj prawą rotację na xy. Obrót w prawo xy
  2. Wykonaj obrót w lewo na zy. Obrót w lewo zy

Algorytm wstawiania nowego węzła

Nowy węzeł jest zawsze wstawiany jako węzeł liścia ze współczynnikiem równowagi równym 0.

  1. Niech początkowe drzewo będzie: Początkowe drzewo do wstawienia
    Niech wstawiany węzeł będzie: Nowy węzeł
  2. Przejdź do odpowiedniego węzła liścia, aby wstawić newNode, wykonując następujące czynności cykliczne. Porównaj newKey z rootKey w bieżącym drzewie.
    1. Jeśli newKey <rootKey, wywołaj algorytm wstawiania z lewego poddrzewa bieżącego węzła, aż do osiągnięcia węzła liścia.
    2. W przeciwnym razie, jeśli newKey> rootKey, wywołaj algorytm wstawiania na prawym poddrzewie bieżącego węzła, aż do osiągnięcia węzła liścia.
    3. W przeciwnym razie zwraca leafNode. Znajdowanie lokalizacji do wstawienia newNode
  3. Porównaj leafKey uzyskany w powyższych krokach z newKey:
    1. Jeśli newKey <leafKey, utwórz newNode jako leftChild elementu leafNode.
    2. W przeciwnym razie utwórz newNode jako rightChild z leafNode. Wstawianie nowego węzła
  4. Zaktualizuj balanceFactor węzłów. Aktualizacja współczynnika równowagi po włożeniu
  5. Jeśli węzły są niezrównoważone, zrównoważyć węzeł.
    1. Jeśli balanceFactor> 1, oznacza to, że wysokość lewego poddrzewa jest większa niż prawego poddrzewa. Zrób więc obrót w prawo lub obrót w lewo-prawo
      1. Jeśli newNodeKey <leftChildKey wykonuje obrót w prawo.
      2. W przeciwnym razie wykonaj obrót od lewej do prawej. Równoważenie drzewa z rotacją Równoważenie drzewa z rotacją
    2. Jeśli balanceFactor <-1, oznacza to, że wysokość prawego poddrzewa jest większa niż lewego poddrzewa. Więc wykonaj obrót w prawo lub obrót w prawo-lewo
      1. Jeśli newNodeKey> rightChildKey wykonuje obrót w lewo.
      2. W przeciwnym razie wykonaj obrót w prawo-lewo
  6. Ostatnie drzewo to: Ostateczne zrównoważone drzewo

Algorytm usuwania węzła

Węzeł jest zawsze usuwany jako węzeł liścia. Po usunięciu węzła zmieniają się współczynniki równowagi węzłów. Aby zrównoważyć współczynnik równowagi, wykonuje się odpowiednie obroty.

  1. Zlokalizuj nodeToBeDeleted (rekursja służy do znalezienia nodeToBeDeleted w kodzie użytym poniżej). Lokalizowanie węzła do usunięcia
  2. Istnieją trzy przypadki usunięcia węzła:
    1. Jeśli nodeToBeDeleted jest węzłem liścia (tj. Nie ma żadnego potomka), usuń nodeToBeDeleted.
    2. Jeśli nodeToBeDeleted ma jedno dziecko, zamień zawartość nodeToBeDeleted na zawartość elementu podrzędnego. Usuń dziecko.
    3. Jeśli nodeToBeDeleted ma dwoje dzieci, znajdź następcę w kolejności w nodeToBeDeleted (tj. Węzeł z minimalną wartością klucza w prawym poddrzewie). Znalezienie następcy
      1. Zastąp zawartość nodeToBeDeleted zawartością w. Zastąp węzeł, który ma zostać usunięty
      2. Usuń węzeł liścia w. Usuń w
  3. Zaktualizuj balanceFactor węzłów. Zaktualizuj bf
  4. Ponownie wyważ drzewo, jeśli współczynnik równowagi któregokolwiek z węzłów nie jest równy -1, 0 lub 1.
    1. Jeśli balanceFactor of currentNode> 1,
      1. Jeśli balanceFactor of leftChild> = 0, wykonaj rotację w prawo. Obróć w prawo, aby zrównoważyć drzewo
      2. W przeciwnym razie wykonaj rotację lewo-prawo.
    2. Jeśli balanceFactor of currentNode <-1,
      1. Jeśli balanceFactor of rightChild <= 0, wykonaj rotację w lewo.
      2. W przeciwnym razie wykonaj obrót w prawo-lewo.
  5. Ostatnie drzewo to: Avl tree final

Przykłady w Pythonie, Javie 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); )

Złożoność różnych operacji na drzewie AVL

Wprowadzenie Usunięcie Szukaj
O (log n) O (log n) O (log n)

Aplikacje AVL Tree

  • Do indeksowania dużych rekordów w bazach danych
  • Do wyszukiwania w dużych bazach danych

Interesujące artykuły...