Pohon AVL

Dalam tutorial ini, Anda akan mempelajari apa itu pohon avl. Selain itu, Anda akan menemukan contoh kerja dari berbagai operasi yang dilakukan pada pohon avl di C, C ++, Java dan Python.

Pohon AVL adalah pohon pencarian biner self-balancing di mana setiap node menyimpan informasi tambahan yang disebut faktor keseimbangan yang nilainya -1, 0 atau +1.

Pohon AVL mendapatkan namanya setelah penemunya Georgy Adelson-Velsky dan Landis.

Faktor Keseimbangan

Faktor keseimbangan dari sebuah simpul dalam pohon AVL adalah selisih antara tinggi dari subpohon kiri dan yang dari subpohon kanan dari simpul tersebut.

Faktor Keseimbangan = (Tinggi Subtree Kiri - Tinggi Subtree Kanan) atau (Tinggi Subtree Kanan - Tinggi Subtree Kiri)

Properti self balancing dari pohon avl dipertahankan oleh faktor keseimbangan. Nilai faktor keseimbangan harus selalu -1, 0 atau +1.

Contoh pohon avl yang seimbang adalah:

Pohon avl

Operasi pada pohon AVL

Berbagai operasi yang dapat dilakukan pada pohon AVL adalah:

Memutar subpohon di Pohon AVL

Dalam operasi rotasi, posisi simpul subpohon dipertukarkan.

Ada dua jenis rotasi:

Putar Kiri

Pada putaran kiri, susunan simpul di sebelah kanan diubah menjadi susunan di simpul kiri.

Algoritma

  1. Biarkan pohon awal menjadi: Rotasi kiri
  2. Jika y memiliki subpohon kiri, tetapkan x sebagai orang tua dari subpohon kiri y. Tentukan x sebagai orang tua dari subpohon kiri dari y
  3. Jika induk x adalah NULL, jadikan y sebagai akar pohon.
  4. Lain jika x adalah anak kiri dari p, jadikan y sebagai anak kiri dari p.
  5. Lain tentukan y sebagai anak kanan dari p. Ubah orang tua dari x menjadi y
  6. Jadikan y sebagai orang tua dari x. Tentukan y sebagai orang tua dari x.

Putar Kanan

Pada putaran kiri, susunan simpul di sebelah kiri diubah menjadi susunan di simpul kanan.

  1. Biarkan pohon awal menjadi: Pohon awal
  2. Jika x memiliki subpohon kanan, tetapkan y sebagai orang tua dari subpohon kanan x. Tentukan y sebagai orang tua dari subpohon kanan x
  3. Jika induk dari y adalah NULL, jadikan x sebagai akar pohon.
  4. Jika y adalah anak kanan dari orang tuanya p, jadikan x sebagai anak kanan dari p.
  5. Lain tetapkan x sebagai anak kiri dari p. Tetapkan orang tua dari y sebagai orang tua dari x.
  6. Jadikan x sebagai orang tua dari y. Tentukan x sebagai induk dari y

Putar Kiri-Kanan dan Kanan-Kiri

Pada rotasi kiri-kanan, pengaturan digeser terlebih dahulu ke kiri lalu ke kanan.

  1. Lakukan rotasi ke kiri pada xy. Putar kiri xy
  2. Lakukan rotasi yang benar pada yz. Putar kanan zy

Pada rotasi kanan-kiri, pengaturan digeser terlebih dahulu ke kanan lalu ke kiri.

  1. Lakukan rotasi yang benar pada xy. Putar kanan xy
  2. Lakukan rotasi ke kiri pada zy. Putar kiri zy

Algoritma untuk memasukkan newNode

Node baru selalu disisipkan sebagai simpul daun dengan faktor keseimbangan sama dengan 0.

  1. Biarkan pohon awal menjadi: Pohon awal untuk penyisipan
    Biarkan simpul yang akan dimasukkan menjadi: Node baru
  2. Pergi ke node daun yang sesuai untuk memasukkan node baru menggunakan langkah rekursif berikut. Bandingkan newKey dengan rootKey dari pohon saat ini.
    1. Jika newKey <rootKey, panggil algoritma penyisipan pada subpohon kiri dari simpul saat ini sampai simpul daun tercapai.
    2. Lain jika newKey> rootKey, panggil algoritma penyisipan pada sub pohon kanan simpul saat ini sampai simpul daun tercapai.
    3. Lain, kembalikan leafNode. Menemukan lokasi untuk memasukkan newNode
  3. Bandingkan leafKey yang diperoleh dari langkah-langkah di atas dengan newKey:
    1. Jika newKey <leafKey, buat newNode sebagai leftChild dari leafNode.
    2. Lain, buat newNode sebagai rightChild dari leafNode. Memasukkan node baru
  4. Perbarui balanceFactor dari node. Memperbarui faktor keseimbangan setelah penyisipan
  5. Jika node tidak seimbang, maka seimbangkan kembali node tersebut.
    1. Jika balanceFactor> 1, berarti tinggi subtree kiri lebih besar dari subtree kanan. Jadi, lakukan rotasi ke kanan atau kiri-kanan
      1. Jika newNodeKey <leftChildKey melakukan rotasi kanan.
      2. Atau, lakukan rotasi kiri-kanan. Menyeimbangkan pohon dengan rotasi Menyeimbangkan pohon dengan rotasi
    2. Jika balanceFactor <-1, artinya tinggi subtree kanan lebih besar dari subtree kiri. Jadi, lakukan rotasi kanan atau rotasi kanan-kiri
      1. Jika newNodeKey> rightChildKey melakukan rotasi ke kiri.
      2. Lain, lakukan rotasi kanan-kiri
  6. Pohon terakhir adalah: Pohon keseimbangan akhir

Algoritma untuk menghapus node

Sebuah node selalu dihapus sebagai node daun. Setelah menghapus sebuah node, faktor keseimbangan dari node tersebut akan berubah. Untuk menyeimbangkan kembali faktor keseimbangan, rotasi yang sesuai dilakukan.

  1. Temukan nodeToBeDeleted (rekursi digunakan untuk menemukan nodeToBeDeleted dalam kode yang digunakan di bawah ini). Menemukan node yang akan dihapus
  2. Ada tiga kasus untuk menghapus node:
    1. Jika nodeToBeDeleted adalah node daun (mis. Tidak memiliki anak), maka hapus nodeToBeDeleted.
    2. Jika nodeToBeDeleted memiliki satu anak, gantikan konten nodeToBeDeleted dengan konten anak tersebut. Hapus anak itu.
    3. Jika nodeToBeDeleted memiliki dua anak, temukan penerus inorder w dari nodeToBeDeleted (yaitu node dengan nilai kunci minimum di subpohon kanan). Menemukan penggantinya
      1. Gantikan konten nodeToBeDeleted dengan konten w. Gantikan node yang akan dihapus
      2. Hapus simpul daun w. Hapus w
  3. Perbarui balanceFactor dari node. Perbarui bf
  4. Seimbangkan kembali pohon jika faktor keseimbangan dari salah satu node tidak sama dengan -1, 0 atau 1.
    1. Jika balanceFactor dari currentNode> 1,
      1. Jika balanceFactor of leftChild> = 0, lakukan rotasi ke kanan. Putar kanan untuk menyeimbangkan pohon
      2. Lain lakukan rotasi kiri-kanan.
    2. Jika balanceFactor dari currentNode <-1,
      1. Jika balanceFactor of rightChild <= 0, lakukan rotasi ke kiri.
      2. Lain lakukan rotasi kanan-kiri.
  5. Pohon terakhir adalah: Pohon akhir avl

Contoh Python, Java dan C / C ++

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

Kompleksitas Operasi Berbeda pada Pohon AVL

Insersi Penghapusan Cari
O (log n) O (log n) O (log n)

Aplikasi Pohon AVL

  • Untuk mengindeks record besar dalam database
  • Untuk mencari di database besar

Artikel yang menarik...