Trong hướng dẫn này, bạn sẽ học cách hoạt động của Binary Search Tree. Ngoài ra, bạn sẽ tìm thấy các ví dụ làm việc của Cây tìm kiếm nhị phân trong C, C ++, Java và Python.
Cây tìm kiếm nhị phân là một cấu trúc dữ liệu nhanh chóng cho phép chúng ta duy trì một danh sách các số đã được sắp xếp.
- Nó được gọi là cây nhị phân vì mỗi nút cây có tối đa hai nút con.
- Nó được gọi là cây tìm kiếm vì nó có thể được sử dụng để tìm kiếm sự hiện diện của một số trong
O(log(n))thời gian.
Các thuộc tính phân tách cây tìm kiếm nhị phân khỏi cây nhị phân thông thường là
- Tất cả các nút của cây con bên trái đều nhỏ hơn nút gốc
- Tất cả các nút của cây con bên phải đều hơn nút gốc
- Cả hai cây con của mỗi nút cũng là BST tức là chúng có hai thuộc tính trên
Cây có cây con bên phải với một giá trị nhỏ hơn giá trị gốc được hiển thị để chứng minh rằng nó không phải là cây tìm kiếm nhị phân hợp lệ
Cây nhị phân ở bên phải không phải là cây tìm kiếm nhị phân vì cây con bên phải của nút "3" chứa giá trị nhỏ hơn nó.
Có hai thao tác cơ bản mà bạn có thể thực hiện trên cây tìm kiếm nhị phân:
Hoạt động tìm kiếm
Thuật toán phụ thuộc vào thuộc tính của BST rằng nếu mỗi cây con bên trái có giá trị bên dưới gốc và mỗi cây con bên phải có giá trị bên trên gốc.
Nếu giá trị nằm dưới gốc, chúng ta có thể nói chắc chắn rằng giá trị đó không nằm trong cây con bên phải; chúng ta chỉ cần tìm kiếm trong cây con bên trái và nếu giá trị nằm trên gốc, chúng ta có thể nói chắc chắn rằng giá trị đó không nằm trong cây con bên trái; chúng ta chỉ cần tìm kiếm trong cây con bên phải.
Thuật toán:
If root == NULL return NULL; If number == root->data return root->data; If number data return search(root->left) If number> root->data return search(root->right)
Chúng ta hãy thử hình dung điều này bằng một sơ đồ.
4 không được tìm thấy như vậy, đi qua cây con bên trái của 8 
4 không được tìm thấy như vậy, đi qua cây con bên phải của 3 
4 không được tìm thấy, đi qua cây con bên trái của 6 4 được tìm thấy
Nếu giá trị được tìm thấy, chúng tôi trả về giá trị để nó được truyền trong mỗi bước đệ quy như thể hiện trong hình dưới đây.
Nếu bạn có thể nhận thấy, chúng tôi đã gọi tìm kiếm trả về (nút cấu trúc *) bốn lần. Khi chúng ta trả về nút mới hoặc NULL, giá trị sẽ được trả về nhiều lần cho đến khi tìm kiếm (root) trả về kết quả cuối cùng.
Nếu giá trị được tìm thấy trong bất kỳ cây con nào, nó sẽ được truyền lên để cuối cùng nó được trả về, nếu không thì trả về null
Nếu giá trị không được tìm thấy, cuối cùng chúng ta sẽ đến nút con bên trái hoặc bên phải của nút lá là NULL và nó được truyền và trả về.
Chèn hoạt động
Chèn một giá trị vào đúng vị trí tương tự như tìm kiếm vì chúng ta cố gắng duy trì quy tắc rằng cây con bên trái nhỏ hơn gốc và cây con bên phải lớn hơn gốc.
Chúng ta tiếp tục đi tới cây con bên phải hoặc cây con bên trái tùy thuộc vào giá trị và khi chúng ta đến một điểm bên trái hoặc bên phải là null, chúng ta đặt nút mới ở đó.
Thuật toán:
If node == NULL return createNode(data) if (data data) node->left = insert(node->left, data); else if (data> node->data) node->right = insert(node->right, data); return node;
Thuật toán không đơn giản như vẻ ngoài của nó. Hãy thử hình dung cách chúng ta thêm một số vào BST hiện có.
4 <8 như vậy, cắt ngang qua con trái của 8 
4> 3 như vậy, cắt ngang qua con bên phải của 8 
4 <6 như vậy, cắt ngang qua con bên trái của 6 
Chèn 4 là con trái của 6
Chúng tôi đã đính kèm nút nhưng chúng tôi vẫn phải thoát khỏi hàm mà không gây bất kỳ thiệt hại nào cho phần còn lại của cây. Đây là nơi mà return node;ở cuối có ích. Trong trường hợp của NULL, nút mới được tạo được trả về và gắn vào nút cha, nếu không thì nút tương tự được trả về mà không có bất kỳ thay đổi nào khi chúng ta đi lên cho đến khi chúng ta quay lại gốc.
Điều này đảm bảo rằng khi chúng tôi di chuyển lại cây, các kết nối nút khác không bị thay đổi.
Hình ảnh cho thấy tầm quan trọng của việc trả về phần tử gốc ở cuối để các phần tử không bị mất vị trí trong bước đệ quy hướng lên.
Thao tác xóa
Có ba trường hợp để xóa một nút khỏi cây tìm kiếm nhị phân.
Trường hợp I
Trong trường hợp đầu tiên, nút bị xóa là nút lá. Trong trường hợp này, chỉ cần xóa nút khỏi cây.
4 là bị xóa 
Xóa nút
Trường hợp II
Trong trường hợp thứ hai, nút bị xóa chỉ có một nút con duy nhất. Trong trường hợp này, hãy làm theo các bước dưới đây:
- Thay thế nút đó bằng nút con của nó.
- Loại bỏ nút con khỏi vị trí ban đầu của nó.
6 là bị xóa 
sao chép giá trị con của nó vào nút và xóa 
cây con Cuối cùng
Trường hợp III
Trong trường hợp thứ ba, nút bị xóa có hai nút con. Trong trường hợp này, hãy làm theo các bước dưới đây:
- Nhận phần tử kế nhiệm nhỏ hơn của nút đó.
- Thay thế nút bằng nút kế nhiệm nhỏ hơn.
- Loại bỏ người kế nhiệm inorder khỏi vị trí ban đầu của nó.
3 là bị xóa Sao chép giá trị của người kế nhiệm inorder (4) vào nút 
Xóa người kế nhiệm inorder
Ví dụ về Python, Java và C / C ++
Python Java C C ++ # Binary Search Tree operations in Python # Create a node class Node: def __init__(self, key): self.key = key self.left = None self.right = None # Inorder traversal def inorder(root): if root is not None: # Traverse left inorder(root.left) # Traverse root print(str(root.key) + "->", end=' ') # Traverse right inorder(root.right) # Insert a node def insert(node, key): # Return a new node if the tree is empty if node is None: return Node(key) # Traverse to the right place and insert the node if key < node.key: node.left = insert(node.left, key) else: node.right = insert(node.right, key) return node # Find the inorder successor def minValueNode(node): current = node # Find the leftmost leaf while(current.left is not None): current = current.left return current # Deleting a node def deleteNode(root, key): # Return if the tree is empty if root is None: return root # Find the node to be deleted if key root.key): root.right = deleteNode(root.right, key) else: # If the node is with only one child or no child if root.left is None: temp = root.right root = None return temp elif root.right is None: temp = root.left root = None return temp # If the node has two children, # place the inorder successor in position of the node to be deleted temp = minValueNode(root.right) root.key = temp.key # Delete the inorder successor root.right = deleteNode(root.right, temp.key) return root root = None root = insert(root, 8) root = insert(root, 3) root = insert(root, 1) root = insert(root, 6) root = insert(root, 7) root = insert(root, 10) root = insert(root, 14) root = insert(root, 4) print("Inorder traversal: ", end=' ') inorder(root) print("Delete 10") root = deleteNode(root, 10) print("Inorder traversal: ", end=' ') inorder(root)
// Binary Search Tree operations in Java class BinarySearchTree ( class Node ( int key; Node left, right; public Node(int item) ( key = item; left = right = null; ) ) Node root; BinarySearchTree() ( root = null; ) void insert(int key) ( root = insertKey(root, key); ) // Insert key in the tree Node insertKey(Node root, int key) ( // Return a new node if the tree is empty if (root == null) ( root = new Node(key); return root; ) // Traverse to the right place and insert the node if (key root.key) root.right = insertKey(root.right, key); return root; ) void inorder() ( inorderRec(root); ) // Inorder Traversal void inorderRec(Node root) ( if (root != null) ( inorderRec(root.left); System.out.print(root.key + " -> "); inorderRec(root.right); ) ) void deleteKey(int key) ( root = deleteRec(root, key); ) Node deleteRec(Node root, int key) ( // Return if the tree is empty if (root == null) return root; // Find the node to be deleted if (key root.key) root.right = deleteRec(root.right, key); else ( // If the node is with only one child or no child if (root.left == null) return root.right; else if (root.right == null) return root.left; // If the node has two children // Place the inorder successor in position of the node to be deleted root.key = minValue(root.right); // Delete the inorder successor root.right = deleteRec(root.right, root.key); ) return root; ) // Find the inorder successor int minValue(Node root) ( int minv = root.key; while (root.left != null) ( minv = root.left.key; root = root.left; ) return minv; ) // Driver Program to test above functions public static void main(String() args) ( BinarySearchTree tree = new BinarySearchTree(); tree.insert(8); tree.insert(3); tree.insert(1); tree.insert(6); tree.insert(7); tree.insert(10); tree.insert(14); tree.insert(4); System.out.print("Inorder traversal: "); tree.inorder(); System.out.println("After deleting 10"); tree.deleteKey(10); System.out.print("Inorder traversal: "); tree.inorder(); ) )
// Binary Search Tree operations in C #include #include struct node ( int key; struct node *left, *right; ); // Create a node struct node *newNode(int item) ( struct node *temp = (struct node *)malloc(sizeof(struct node)); temp->key = item; temp->left = temp->right = NULL; return temp; ) // Inorder Traversal void inorder(struct node *root) ( if (root != NULL) ( // Traverse left inorder(root->left); // Traverse root printf("%d -> ", root->key); // Traverse right inorder(root->right); ) ) // Insert a node struct node *insert(struct node *node, int key) ( // Return a new node if the tree is empty if (node == NULL) return newNode(key); // Traverse to the right place and insert the node if (key key) node->left = insert(node->left, key); else node->right = insert(node->right, key); return node; ) // Find the inorder successor struct node *minValueNode(struct node *node) ( struct node *current = node; // Find the leftmost leaf while (current && current->left != NULL) current = current->left; return current; ) // Deleting a node struct node *deleteNode(struct node *root, int key) ( // Return if the tree is empty if (root == NULL) return root; // Find the node to be deleted if (key key) root->left = deleteNode(root->left, key); else if (key> root->key) root->right = deleteNode(root->right, key); else ( // If the node is with only one child or no child if (root->left == NULL) ( struct node *temp = root->right; free(root); return temp; ) else if (root->right == NULL) ( struct node *temp = root->left; free(root); return temp; ) // If the node has two children struct node *temp = minValueNode(root->right); // Place the inorder successor in position of the node to be deleted root->key = temp->key; // Delete the inorder successor root->right = deleteNode(root->right, temp->key); ) return root; ) // Driver code int main() ( struct node *root = NULL; root = insert(root, 8); root = insert(root, 3); root = insert(root, 1); root = insert(root, 6); root = insert(root, 7); root = insert(root, 10); root = insert(root, 14); root = insert(root, 4); printf("Inorder traversal: "); inorder(root); printf("After deleting 10"); root = deleteNode(root, 10); printf("Inorder traversal: "); inorder(root); )
// Binary Search Tree operations in C++ #include using namespace std; struct node ( int key; struct node *left, *right; ); // Create a node struct node *newNode(int item) ( struct node *temp = (struct node *)malloc(sizeof(struct node)); temp->key = item; temp->left = temp->right = NULL; return temp; ) // Inorder Traversal void inorder(struct node *root) ( if (root != NULL) ( // Traverse left inorder(root->left); // Traverse root cout right); ) ) // Insert a node struct node *insert(struct node *node, int key) ( // Return a new node if the tree is empty if (node == NULL) return newNode(key); // Traverse to the right place and insert the node if (key key) node->left = insert(node->left, key); else node->right = insert(node->right, key); return node; ) // Find the inorder successor struct node *minValueNode(struct node *node) ( struct node *current = node; // Find the leftmost leaf while (current && current->left != NULL) current = current->left; return current; ) // Deleting a node struct node *deleteNode(struct node *root, int key) ( // Return if the tree is empty if (root == NULL) return root; // Find the node to be deleted if (key key) root->left = deleteNode(root->left, key); else if (key> root->key) root->right = deleteNode(root->right, key); else ( // If the node is with only one child or no child if (root->left == NULL) ( struct node *temp = root->right; free(root); return temp; ) else if (root->right == NULL) ( struct node *temp = root->left; free(root); return temp; ) // If the node has two children struct node *temp = minValueNode(root->right); // Place the inorder successor in position of the node to be deleted root->key = temp->key; // Delete the inorder successor root->right = deleteNode(root->right, temp->key); ) return root; ) // Driver code int main() ( struct node *root = NULL; root = insert(root, 8); root = insert(root, 3); root = insert(root, 1); root = insert(root, 6); root = insert(root, 7); root = insert(root, 10); root = insert(root, 14); root = insert(root, 4); cout << "Inorder traversal: "; inorder(root); cout << "After deleting 10"; root = deleteNode(root, 10); cout << "Inorder traversal: "; inorder(root); )
Độ phức tạp của cây tìm kiếm nhị phân
Thời gian phức tạp
| Hoạt động | Trường hợp phức tạp tốt nhất | Độ phức tạp của trường hợp trung bình | Trường hợp phức tạp tệ nhất |
| Tìm kiếm | O (log n) | O (log n) | Trên) |
| Chèn | O (log n) | O (log n) | Trên) |
| Xóa | O (log n) | O (log n) | Trên) |
Ở đây, n là số nút trong cây.
Không gian phức tạp
Độ phức tạp không gian cho tất cả các phép toán là O (n).
Ứng dụng cây tìm kiếm nhị phân
- Trong lập chỉ mục đa cấp trong cơ sở dữ liệu
- Để phân loại động
- Để quản lý các vùng bộ nhớ ảo trong nhân Unix
