Cây AVL

Trong hướng dẫn này, bạn sẽ tìm hiểu cây avl là gì. Ngoài ra, bạn sẽ tìm thấy các ví dụ làm việc về các hoạt động khác nhau được thực hiện trên cây avl trong C, C ++, Java và Python.

Cây AVL là một cây tìm kiếm nhị phân tự cân bằng, trong đó mỗi nút duy trì thông tin bổ sung được gọi là hệ số cân bằng có giá trị là -1, 0 hoặc +1.

Cây AVL được đặt theo tên của nhà phát minh Georgy Adelson-Velsky và Landis.

Yếu tố cân bằng

Hệ số cân bằng của một nút trong cây AVL là hiệu số giữa chiều cao của cây con bên trái và chiều cao của cây con bên phải của nút đó.

Hệ số cân bằng = (Chiều cao của cây con bên trái - Chiều cao của cây con bên phải) hoặc (Chiều cao của cây con bên phải - Chiều cao của cây con bên trái)

Thuộc tính tự cân bằng của cây avl được duy trì bởi hệ số cân bằng. Giá trị của hệ số cân bằng phải luôn là -1, 0 hoặc +1.

Một ví dụ về cây avl cân bằng là:

Cây Avl

Các thao tác trên cây AVL

Các hoạt động khác nhau có thể được thực hiện trên cây AVL là:

Xoay các cây con trong Cây AVL

Trong hoạt động xoay, vị trí của các nút của cây con được hoán đổi cho nhau.

Có hai kiểu quay:

Xoay trái

Trong phép quay trái, sự sắp xếp của các nút bên phải được chuyển thành cách sắp xếp ở nút bên trái.

Thuật toán

  1. Đặt cây ban đầu là: Xoay trái
  2. Nếu y có một cây con bên trái, hãy gán x là con của cây con bên trái của y. Gán x là cha của cây con bên trái của y
  3. Nếu gốc của x là NULL, hãy lấy y làm gốc của cây.
  4. Ngược lại, nếu x là con trái của p, hãy đặt y là con trái của p.
  5. Khác gán y là con bên phải của p. Thay đổi gốc của x thành của y
  6. Đặt y là mẹ của x. Gán y là cha của x.

Xoay phải

Trong phép quay trái, sự sắp xếp của các nút bên trái được chuyển thành cách sắp xếp ở nút bên phải.

  1. Đặt cây ban đầu là: Cây ban đầu
  2. Nếu x có một cây con bên phải, hãy gán y là con của cây con bên phải của x. Gán y làm cha của cây con bên phải của x
  3. Nếu là gốc của y NULL, hãy lấy x làm gốc của cây.
  4. Ngược lại nếu y là con bên phải của p cha, hãy đặt x là con bên phải của p.
  5. Khác gán x là con bên trái của p. Chỉ định cha mẹ của y làm cha mẹ của x.
  6. Đặt x là cha của y. Gán x là cha của y

Xoay trái-phải và phải-trái

Trong xoay trái-phải, các sắp xếp đầu tiên được chuyển sang trái và sau đó sang phải.

  1. Thực hiện quay trái trên xy. Xoay trái xy
  2. Thực hiện xoay phải trên yz. Xoay phải zy

Trong phép quay phải-trái, các sắp xếp đầu tiên được chuyển sang phải và sau đó là sang trái.

  1. Thực hiện quay bên phải trên xy. Xoay phải xy
  2. Thực hiện xoay trái trên zy. Xoay trái zy

Thuật toán chèn mã mới

Một newNode luôn được chèn vào dưới dạng nút lá với hệ số cân bằng bằng 0.

  1. Đặt cây ban đầu là: Cây ban đầu để chèn
    Cho nút được chèn là: Nút mới
  2. Đi tới nút lá thích hợp để chèn NewNode bằng cách sử dụng các bước đệ quy sau. So sánh newKey với rootKey của cây hiện tại.
    1. Nếu newKey <rootKey, gọi thuật toán chèn vào cây con bên trái của nút hiện tại cho đến khi đạt đến nút lá.
    2. Khác nếu newKey> rootKey, gọi thuật toán chèn vào cây con bên phải của nút hiện tại cho đến khi đạt đến nút lá.
    3. Khác, trả về leafNode. Tìm vị trí để chèn newNode
  3. So sánh leafKey thu được từ các bước trên với newKey:
    1. Nếu newKey <leafKey, hãy đặt newNode làm con bên trái của leafNode.
    2. Nếu không, tạo newNode là rightChild của leafNode. Chèn nút mới
  4. Cập nhật số dư Cơ cấu của các nút. Cập nhật hệ số cân bằng sau khi chèn
  5. Nếu các nút không cân bằng, sau đó cân bằng lại nút.
    1. Nếu balanceFactor> 1, có nghĩa là chiều cao của cây con bên trái lớn hơn chiều cao của cây con bên phải. Vì vậy, hãy thực hiện xoay phải hoặc xoay trái-phải
      1. Nếu newNodeKey <leftChildKey thực hiện xoay phải.
      2. Khác, thực hiện xoay trái-phải. Cân bằng cây bằng luân phiên Cân bằng cây bằng cách xoay
    2. Nếu balanceFactor <-1, có nghĩa là chiều cao của cây con bên phải lớn hơn chiều cao của cây con bên trái. Vì vậy, hãy thực hiện xoay phải hoặc xoay phải trái
      1. Nếu newNodeKey> rightChildKey thực hiện xoay trái.
      2. Khác, thực hiện xoay phải trái
  6. Cây cuối cùng là: Cây cân bằng cuối cùng

Thuật toán xóa nút

Một nút luôn bị xóa dưới dạng nút lá. Sau khi xóa một nút, hệ số cân bằng của các nút sẽ thay đổi. Để cân bằng lại hệ số cân bằng, người ta thực hiện các phép quay thích hợp.

  1. Định vị nodeToBeDeleted (đệ quy được sử dụng để tìm nodeToBeDeleted trong mã được sử dụng bên dưới). Định vị nút sẽ bị xóa
  2. Có ba trường hợp để xóa một nút:
    1. Nếu nodeToBeDeleted là nút lá (tức là không có con nào), thì hãy loại bỏ nodeToBeDeleted.
    2. Nếu nodeToBeDeleted có một con, thì hãy thay thế nội dung của nodeToBeDeleted bằng nội dung của con đó. Loại bỏ đứa trẻ.
    3. Nếu nodeToBeDeleted có hai phần tử con, hãy tìm phần tử kế thừa thứ nhất w của nodeToBeDeleted (tức là nút có giá trị nhỏ nhất của khóa trong cây con bên phải). Tìm người kế thừa
      1. Thay thế nội dung của nodeToBeDeleted bằng nội dung của w. Thay thế nút bị xóa
      2. Bỏ nút lá w. Xóa w
  3. Cập nhật số dư Cơ cấu của các nút. Cập nhật bf
  4. Cân bằng lại cây nếu hệ số cân bằng của bất kỳ nút nào không bằng -1, 0 hoặc 1.
    1. Nếu balanceFactor of currentNode> 1,
      1. Nếu balanceFactor của leftChild> = 0, hãy thực hiện xoay phải. Xoay phải để giữ thăng bằng cho cây
      2. Khác thực hiện xoay trái-phải.
    2. Nếu balanceFactor of currentNode <-1,
      1. Nếu balanceFactor of rightChild <= 0, hãy thực hiện xoay trái.
      2. Làm khác xoay phải trái.
  5. Cây cuối cùng là: Cây Avl cuối cùng

Ví dụ về Python, Java và 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); )

Sự phức tạp của các hoạt động khác nhau trên cây AVL

Chèn Xóa Tìm kiếm
O (log n) O (log n) O (log n)

Ứng dụng cây AVL

  • Để lập chỉ mục các bản ghi lớn trong cơ sở dữ liệu
  • Để tìm kiếm trong cơ sở dữ liệu lớn

thú vị bài viết...