AVL Ağacı

Bu eğitimde avl ağacının ne olduğunu öğreneceksiniz. Ayrıca, C, C ++, Java ve Python'da bir avl ağacında gerçekleştirilen çeşitli işlemlerin çalışma örneklerini bulacaksınız.

AVL ağacı, her bir düğümün değeri -1, 0 veya +1 olan bir denge faktörü adı verilen ekstra bilgileri koruduğu kendi kendini dengeleyen bir ikili arama ağacıdır.

AVL ağacı adını mucidi Georgy Adelson-Velsky ve Landis'in ardından almıştır.

Denge Faktörü

Bir AVL ağacındaki bir düğümün denge faktörü, sol alt ağacın yüksekliği ile o düğümün sağ alt ağacının yüksekliği arasındaki farktır.

Denge Faktörü = (Sol Alt Ağacın Yüksekliği - Sağ Alt Ağacın Yüksekliği) veya (Sağ Alt Ağacın Yüksekliği - Sol Alt Ağacın Yüksekliği)

Bir avl ağacının kendi kendini dengeleme özelliği denge faktörü tarafından korunur. Denge faktörünün değeri her zaman -1, 0 veya +1 olmalıdır.

Dengeli bir avl ağacı örneği:

Avl ağacı

AVL ağacında işlemler

Bir AVL ağacında gerçekleştirilebilecek çeşitli işlemler şunlardır:

Bir AVL Ağacındaki alt ağaçları döndürme

Döndürme işleminde, bir alt ağacın düğümlerinin pozisyonları değiştirilir.

İki tür rotasyon vardır:

Sola Döndür

Sola dönüşte sağdaki düğümlerin dizilişi, sol düğümdeki düzenlemelere dönüştürülür.

Algoritma

  1. İlk ağaç şöyle olsun: Sola döndür
  2. Y'nin bir sol alt ağacı varsa, y'nin sol alt ağacının ebeveyni olarak x'i atayın. X'i y'nin sol alt ağacının ebeveyni olarak atayın
  3. Eğer x'in ebeveyni ise NULL, y'yi ağacın kökü olarak yapın.
  4. Aksi takdirde, x, p'nin sol çocuğu ise, y'yi p'nin sol çocuğu yapın.
  5. Aksi takdirde, y'yi p'nin doğru çocuğu olarak atayın. X'in ebeveynini y'nin ebeveyni olarak değiştirin
  6. Y'yi x'in ebeveyni yapın. Y'yi x'in ebeveyni olarak atayın.

Sağa Döndür

Sola dönüşte, soldaki düğümlerin dizilişi, sağ düğümdeki düzenlemelere dönüştürülür.

  1. İlk ağaç şöyle olsun: İlk ağaç
  2. Eğer x'in bir sağ alt ağacı varsa, y'yi x'in sağ alt ağacının ebeveyni olarak atayın. Y'yi x'in sağ alt ağacının ebeveyni olarak atayın
  3. Y'nin ebeveyni ise NULL, ağacın kökü olarak x yapın.
  4. Aksi takdirde, y ebeveyn p'nin doğru çocuğu ise, x'i p'nin doğru çocuğu yapın.
  5. Aksi takdirde, x'i p'nin sol çocuğu olarak atayın. Y'nin ebeveynini x'in ebeveyni olarak atayın.
  6. X'i y'nin ebeveyni yapın. X'i y'nin ebeveyni olarak atayın

Sola-Sağa ve Sağa-Sola Döndür

Sol-sağ dönüşte, düzenlemeler önce sola sonra sağa kaydırılır.

  1. Xy'de sola dönüş yapın. Xy'yi sola döndür
  2. Yz'de sağa döndürme yapın. Sağa döndür zy

Sağa-sola dönüşte, düzenlemeler önce sağa sonra sola kaydırılır.

  1. Xy'de sağa döndürme yapın. Xy'yi sağa döndür
  2. Zy'de sola dönüş yapın. Sola döndürme zy

Yeni bir Düğüm eklemek için algoritma

Yeni bir düğüm her zaman denge faktörü 0'a eşit olan bir yaprak düğüm olarak eklenir.

  1. İlk ağaç şöyle olsun: Ekleme için ilk ağaç Eklenecek
    düğüm şöyle olsun: Yeni düğüm
  2. Aşağıdaki özyinelemeli adımları kullanarak yeni bir Düğüm eklemek için uygun yaprak düğümüne gidin. NewKey'i mevcut ağacın rootKey'i ile karşılaştırın.
    1. NewKey <rootKey ise, yaprak düğüme ulaşılana kadar geçerli düğümün sol alt ağacında ekleme algoritmasını çağırın.
    2. Aksi takdirde, newKey> rootKey ise, yaprak düğüme ulaşılana kadar geçerli düğümün sağ alt ağacında ekleme algoritmasını çağırın.
    3. Aksi takdirde, leafNode'u döndür. Yeni Düğüm eklemek için konumu bulma
  3. Yukarıdaki adımlardan elde edilen leafKey'i newKey ile karşılaştırın:
    1. NewKey <leafKey ise, leafNode'un leftChild'i olarak newNode yapın.
    2. Aksi takdirde, newNode'u rightChild of leafNode olarak yapın. Yeni düğümü eklemek
  4. Düğümlerin denge faktörünü güncelleyin. Eklemeden sonra denge faktörünün güncellenmesi
  5. Düğümler dengesizse, düğümü yeniden dengeleyin.
    1. BalanceFactor> 1 ise, sol alt ağacın yüksekliğinin sağ alt ağacınkinden daha büyük olduğu anlamına gelir. Yani, sağa döndürme veya sola-sağa döndürme yapın
      1. NewNodeKey <leftChildKey sağa döndürürse.
      2. Aksi takdirde, sola-sağa dönüş yapın. Ağacı rotasyonla dengelemek Ağacı rotasyonla dengelemek
    2. BalanceFactor <-1 ise, sağ alt ağacın yüksekliğinin soldaki alt ağacınkinden daha büyük olduğu anlamına gelir. Yani, sağa döndürme veya sağa-sola döndürme yapın
      1. NewNodeKey> rightChildKey sola döndürürse.
      2. Aksi takdirde, sağa-sola dönüş yapın
  6. Son ağaç: Son dengeli ağaç

Düğümü Silme Algoritması

Bir düğüm her zaman bir yaprak düğüm olarak silinir. Bir düğümü sildikten sonra, düğümlerin denge faktörleri değişir. Denge faktörünü yeniden dengelemek için uygun rotasyonlar yapılır.

  1. NodeToBeDeleted'i bulun (özyineleme, aşağıda kullanılan kodda nodeToBeDeleted'i bulmak için kullanılır). Silinecek düğümün yerini belirleme
  2. Bir düğümü silmek için üç durum vardır:
    1. NodeToBeDeleted, yaprak düğüm ise (yani, herhangi bir çocuğu yoksa), nodeToBeDeleted'i kaldırın.
    2. NodeToBeDeleted bir alt öğeye sahipse, nodeToBeDeleted içeriğini alt öğenin içeriğiyle değiştirin. Çocuğu çıkarın.
    3. NodeToBeDeleted iki alt öğeye sahipse, nodeToBeDeleted'in sıralı halefini bulun (yani, sağ alt ağaçta minimum anahtar değerine sahip düğüm). Halefi bulmak
      1. NodeToBeDeleted içeriğini w ile değiştirin. Silinecek düğümü değiştirin
      2. Yaprak düğümünü w çıkarın. W kaldır
  3. Düğümlerin denge faktörünü güncelleyin. Bf'yi güncelle
  4. Düğümlerden herhangi birinin denge faktörü -1, 0 veya 1'e eşit değilse ağacı yeniden dengeleyin.
    1. CurrentNode'un BalanceFactor değeri> 1 ise,
      1. LeftChild> = 0 için balanceFactor ise, sağa döndürme yapın. Ağacı dengelemek için sağa döndürün
      2. Aksi takdirde sola-sağa dönüş yapın.
    2. CurrentNode'un balanceFactor değeri <-1 ise,
      1. RightChild <= 0 için balanceFactor ise, sola döndürme yapın.
      2. Aksi takdirde sağa-sola dönüş yapın.
  5. Son ağaç: Avl ağacı final

Python, Java ve C / C ++ Örnekleri

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); )

Bir AVL Ağacı Üzerinde Farklı İşlemlerin Karmaşıklıkları

Yerleştirme Silme Arama
O (log n) O (log n) O (log n)

AVL Tree Uygulamaları

  • Veritabanlarında büyük kayıtları indekslemek için
  • Büyük veri tabanlarında arama yapmak için

Ilginç makaleler...