Pokok AVL

Dalam tutorial ini, anda akan belajar apa itu pohon avl. Anda juga akan mendapat contoh kerja dari pelbagai operasi yang dilakukan pada pohon avl di C, C ++, Java dan Python.

Pokok AVL adalah pokok carian binari yang mengimbangkan sendiri di mana setiap nod mengekalkan maklumat tambahan yang disebut faktor keseimbangan yang nilainya sama -1, 0 atau +1.

Pokok AVL mendapat namanya setelah penciptanya Georgy Adelson-Velsky dan Landis.

Faktor Imbangan

Faktor keseimbangan nod dalam pokok AVL adalah perbezaan antara ketinggian subtree kiri dan subtree kanan nod tersebut.

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

Harta keseimbangan diri pokok avl dikekalkan oleh faktor keseimbangan. Nilai faktor keseimbangan harus selalu -1, 0 atau +1.

Contoh pokok avl yang seimbang adalah:

Pokok Avl

Operasi pada pokok AVL

Pelbagai operasi yang dapat dilakukan pada pokok AVL adalah:

Memusingkan subtumbuhan di Pokok AVL

Dalam operasi putaran, kedudukan nod subtree ditukar.

Terdapat dua jenis putaran:

Putar Kiri

Dalam putaran kiri, susunan nod di sebelah kanan diubah menjadi susunan di simpul kiri.

Algoritma

  1. Biarkan pokok awal: Putar kiri
  2. Sekiranya y mempunyai subtree kiri, tetapkan x sebagai induk subtree kiri y. Tugaskan x sebagai induk subtree kiri y
  3. Sekiranya induk x adalah NULL, jadikan y sebagai akar pokok.
  4. Jika tidak, x adalah anak kiri p, jadikan y sebagai anak kiri p.
  5. Else menetapkan y sebagai anak yang tepat bagi p. Tukar induk x kepada y
  6. Jadikan y sebagai ibu bapa x. Tugaskan y sebagai ibu bapa x.

Putar Kanan

Dalam putaran kiri, susunan nod di sebelah kiri diubah menjadi susunan di simpul kanan.

  1. Biarkan pokok awal: Pokok permulaan
  2. Sekiranya x mempunyai subtree kanan, tetapkan y sebagai induk subtree kanan. Tugaskan y sebagai induk subtree kanan x
  3. Sekiranya ibu bapa y NULL, jadikan x sebagai akar pokok.
  4. Jika tidak, jika anda adalah anak yang tepat dari ibu bapanya, jadikan x sebagai anak yang tepat bagi p.
  5. Jika tidak, tetapkan x sebagai anak kiri p. Tugaskan induk y sebagai induk x.
  6. Jadikan x sebagai ibu bapa y. Tugaskan x sebagai ibu bapa y

Putar Kiri-Kanan dan Kanan-Kiri

Dalam putaran kiri-kanan, susunannya mula-mula beralih ke kiri dan kemudian ke kanan.

  1. Lakukan putaran kiri pada xy. Putar kiri xy
  2. Lakukan putaran kanan pada yz. Putar kanan zy

Dalam putaran kanan-kiri, susunannya mula-mula dialihkan ke kanan dan kemudian ke kiri.

  1. Lakukan putaran kanan pada xy. Putar kanan xy
  2. Lakukan putaran kiri pada zy. Putar kiri zy

Algoritma untuk memasukkan Node baru

NewNode selalu dimasukkan sebagai simpul daun dengan faktor keseimbangan sama dengan 0.

  1. Biarkan pokok awal: Pohon awal untuk penyisipan
    Biarkan simpul yang akan dimasukkan menjadi: Simpul baru
  2. Pergi ke simpul daun yang sesuai untuk memasukkan Node baru menggunakan langkah rekursif berikut. Bandingkan newKey dengan rootKey dari pokok semasa.
    1. Sekiranya newKey <rootKey, algoritma penyisipan panggilan pada subtree kiri nod semasa sehingga simpul daun tercapai.
    2. Jika tidak, newKey> rootKey, algoritma penyisipan panggilan pada subtree kanan nod semasa sehingga simpul daun tercapai.
    3. Lain, kembalikan daunNode. Mencari lokasi untuk memasukkan NewNode
  3. Bandingkan leafKey yang diperoleh dari langkah di atas dengan newKey:
    1. Sekiranya newKey <leafKey, jadikan newNode sebagai kiriChild of leafNode.
    2. Lain, jadikan newNode sebagai kananChild of leafNode. Memasukkan nod baru
  4. Kemas kini keseimbangan Faktor nod. Mengemas kini faktor keseimbangan selepas penyisipan
  5. Sekiranya nod tidak seimbang, maka seimbangkan semula nod.
    1. Sekiranya balanceFactor> 1, ini bermaksud ketinggian subtree kiri lebih besar daripada subtree kanan. Jadi, lakukan putaran kanan atau putaran kiri-kanan
      1. Sekiranya newNodeKey <leftChildKey melakukan putaran kanan.
      2. Jika tidak, lakukan putaran kiri-kanan. Mengimbangkan pokok dengan putaran Mengimbangkan pokok dengan putaran
    2. Sekiranya balanceFactor <-1, ini bermaksud ketinggian subtree kanan lebih besar daripada subtree kiri. Jadi, lakukan putaran kanan atau putaran kanan-kiri
      1. Sekiranya newNodeKey> rightChildKey lakukan putaran kiri.
      2. Jika tidak, lakukan putaran kanan-kiri
  6. Pokok terakhir ialah: Pokok seimbang akhir

Algoritma untuk Memadamkan nod

Node selalu dihapuskan sebagai simpul daun. Setelah memotong nod, faktor keseimbangan nod berubah. Untuk mengimbangi faktor keseimbangan, putaran yang sesuai dilakukan.

  1. Cari nodeToBeDeleted (rekursi digunakan untuk mencari nodeToBeDeleted dalam kod yang digunakan di bawah). Mencari nod yang akan dipadamkan
  2. Terdapat tiga kes untuk menghapus nod:
    1. Sekiranya nodeToBeDeleted adalah simpul daun (iaitu tidak mempunyai anak), kemudian keluarkan nodeToBeDeleted.
    2. Sekiranya nodeToBeDeleted mempunyai satu anak, maka ganti kandungan nodeToBeDeleted dengan anak. Buang anak.
    3. Sekiranya nodeToBeDeleted mempunyai dua anak, cari pengganti penyusun nodeToBeDeleted (iaitu simpul dengan nilai minimum kunci di subtree kanan). Mencari pengganti
      1. Ganti kandungan nodeToBeDeleted dengan isi w. Ganti nod yang hendak dihapuskan
      2. Tanggalkan simpul daun w. Keluarkan w
  3. Kemas kini keseimbangan Faktor nod. Kemas kini bf
  4. Naikkan semula pokok sekiranya faktor keseimbangan salah satu nod tidak sama dengan -1, 0 atau 1.
    1. Sekiranya keseimbanganFaktor arusNode> 1,
      1. Sekiranya keseimbanganFaktor kiriChild> = 0, lakukan putaran kanan. Putar kanan untuk mengimbangkan pokok
      2. Lain-lain lakukan putaran kiri-kanan.
    2. Sekiranya keseimbanganFaktor arusNode <-1,
      1. Sekiranya keseimbanganFaktor kananChild <= 0, lakukan putaran kiri.
      2. Lain-lain lakukan putaran kanan-kiri.
  5. Pokok terakhir ialah: Pokok akhir Avl

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

Kerumitan Operasi Berbeza pada Pokok AVL

Penyisipan Penghapusan Cari
O (log n) O (log n) O (log n)

Aplikasi Pokok AVL

  • Untuk mengindeks rekod besar dalam pangkalan data
  • Untuk mencari di pangkalan data yang besar

Artikel menarik...