Cây nhị phân trong cấu trúc dữ liệu (VÍ DỤ)
Sarah Chen
Cây nhị phân là gì?
Từ nhị phân có nghĩa là hai. Trong cấu trúc dữ liệu cây “Cây nhị phân”, có nghĩa là một cây trong đó mỗi nút có thể có tối đa hai nút con (nút trái và nút phải). Nó là một cây nhị phân đơn giản.
Tuy nhiên, có một cây nhị phân khác được sử dụng thường xuyên nhất và có một số trường hợp sử dụng. Nó được gọi là Cây tìm kiếm nhị phân (BST). Cây này có thể làm cho thuật toán tìm kiếm nhanh hơn nhiều, chính xác là độ phức tạp thời gian log(n). Trong cấu trúc dữ liệu, n có nghĩa là số nút trong cây nhị phân.
Sự khác biệt giữa Cây nhị phân và Cây tìm kiếm nhị phân là gì?
Sự khác biệt giữa BST và cây nhị phân thông thường là ở nút bên trái BST có giá trị nhỏ hơn nút gốc và nút bên phải có giá trị lớn hơn nút gốc. Vì vậy, cây con bên trái sẽ luôn chứa giá trị nhỏ hơn gốc và cây con bên phải sẽ luôn chứa giá trị lớn hơn gốc.
Ví dụ về cây tìm kiếm nhị phân
Chúng ta hãy xem ví dụ sau để chứng minh các khái niệm về Cây tìm kiếm nhị phân.
Ở đây bạn có thể tất cả các nút tuân theo kỷ luật nhất định. Có một công thức cho số lượng nút tối đa trong Cây tìm kiếm nhị phân. Nếu quan sát cây trên, chúng ta có thể thấy mỗi nút có hai nút con ngoại trừ tất cả các nút lá. Và chiều cao (h) của Cây nhị phân đã cho là 4. Công thức là 2h - 1. Vì vậy, nó cho 15.
Hình ảnh đã cho ở trên không phải là Cây nhị phân hoàn chỉnh hoặc Cây nhị phân cân bằng, được gọi là Cây nhị phân hoàn chỉnh hoặc Cây nhị phân cân bằng. Có một Cấu trúc dữ liệu khác gọi là AVL (một loại Cây nhị phân khác) giúp tối ưu hóa chiều cao của Cây nhị phân và thực hiện tìm kiếm BST nhanh hơn như trong Hình 3.
Hãy thử tính toán việc duyệt theo thứ tự của Cây nhị phân đã cho ở trên. Bạn sẽ thấy rằng nó sẽ đưa ra một mảng được sắp xếp không giảm và các thuật toán Truyền tải sẽ giống như Cây nhị phân.
Các loại cây nhị phân
Dưới đây là một số loại cây nhị phân quan trọng:
- Cây nhị phân đầy đủ: Mỗi nút có thể có 0 hoặc 2 nút con trong cây nhị phân này. Chỉ một nút con không được phép trong loại cây nhị phân này. Vì vậy, ngoại trừ nút lá, tất cả các nút sẽ có 2 nút con.
- Cây nhị phân đầy đủ: Mỗi nút có thể có 0 hoặc 2 nút. Nó có vẻ giống như Cây nhị phân đầy đủ, nhưng tất cả các phần tử lá đều nghiêng về cây con bên trái, trong khi ở cây nhị phân đầy đủ, nút cây nhị phân có thể nằm ở cây con bên phải hoặc bên trái.
- Cây nhị phân hoàn hảo: Tất cả các nút phải có 0 hoặc 2 nút và tất cả các nút lá phải ở cùng cấp độ hoặc chiều cao. Ví dụ trên về cấu trúc cây nhị phân đầy đủ không phải là Cây nhị phân hoàn hảo vì nút 6 và nút 1,2,3 không có cùng chiều cao. Nhưng ví dụ về Cây nhị phân hoàn chỉnh là cây nhị phân hoàn hảo.
- Cây nhị phân suy biến: Mỗi nút chỉ có thể có một nút con duy nhất. Tất cả các thao tác như tìm kiếm, chèn và xóa đều mất thời gian O(N).
- Cây nhị phân cân bằng: Ở đây cây nhị phân này, chênh lệch chiều cao của cây con trái và cây con phải nhiều nhất là 1. Vì vậy, khi thêm hoặc xóa một nút, chúng ta cần phải cân bằng lại chiều cao của cây. Loại Cây nhị phân tự cân bằng này được gọi là Cây AVL.
Có ba hoạt động cơ bản của BST. Những điều đó sẽ được thảo luận chi tiết dưới đây.
Triển khai cây nhị phân trong C và C++
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
struct Node
{
int value;
struct Node *left, *right;
}
struct Node *getEmptynode(int val)
{
struct Node *tempNode = (struct Node *)malloc(sizeof(struct Node));
tempNode->value = val;
tempNode->left = NULL;
tempNode->right = NULL;
return tempNode;
}
struct Node *successor(struct Node *node)
{
struct Node *present = node;
// going to the left most node
while (present != NULL && present->left != NULL)
{
present = present->left;
}
return present;
}
struct Node *insert(struct Node *node, int value)
{
if (node == NULL)
{
return getEmptynode(value);
}
if (value < node->value)
{
node->left = insert(node->left, value);
}
else
{
node->right = insert(node->right, value);
}
return node;
}
int searchInBST(struct Node *node, int value)
{
struct Node *current = node;
while (current->value != value)
{
if (current->value > value)
{
current = current->left;
}
else
{
current = current->right;
}
if (current == NULL)
{
return 0;
}
}
return 1;
}
void inorder(struct Node *root)
{
if (root != NULL)
{
inorder(root->left);
cout << root->value << " ";
inorder(root->right);
}
}
struct Node *deleteNode(struct Node *node, int value)
{
if (node == NULL)
{
return node;
}
if (value < node->value)
{
node->left = deleteNode(node->left, value);
}
else if (value > node->value)
{
node->right = deleteNode(node->right, value);
}
else
{
if (node->left == NULL)
{
struct Node *temp = node->right;
free(node);
return temp;
}
else if (node->right == NULL)
{
struct Node *temp = node->left;
free(node);
return temp;
}
struct Node *temp = successor(node->right);
node->value = temp->value;
node->right = deleteNode(node->right, temp->value);
}
return node;
}
int main()
{
struct Node *root = NULL;
root = insert(root, 8);
root = insert(root, 4);
root = insert(root, 12);
root = insert(root, 2);
root = insert(root, 6);
root = insert(root, 10);
root = insert(root, 14);
root = insert(root, 1);
root = insert(root, 3);
root = insert(root, 5);
root = insert(root, 7);
root = insert(root, 9);
root = insert(root, 11);
root = insert(root, 13);
root = insert(root, 15);
cout << "InOrder Traversal after inserting all nodes: " << endl;
inorder(root);
root = insert(root, -10);
cout << "\nInOrder Traversal after inserting -10 : " << endl;
inorder(root);
cout << "\nSearching -5 in the BST: " << searchInBST(root, -5) << endl;
cout << "Searching -10 in the BST: " << searchInBST(root, -10) << endl;
root = deleteNode(root,8);
cout<<"After deleting node 8, inorder traversal: "<<endl;
inorder(root);
root = deleteNode(root,-10);
cout<<"\nAfter deleting node -10, inorder traversal: "<<endl;
inorder(root);
}
Đầu ra:
InOrder Traversal after inserting all nodes: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 InOrder Traversal after inserting -10 : 10 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 Searching -5 in the BST: 0 Searching -10 in the BST: 1 After deleting node 8, inorder traversal: -10 1 2 3 4 5 6 7 9 10 11 12 13 14 15 After deleting node -10, inorder traversal: 1 2 3 4 5 6 7 9 10 11 12 13 14 15
Triển khai cây nhị phân trong Python
class Node:
def __init__(self,value):
self.left = None
self.right = None
self.value = value
def insert(root,value):
if root == None:
return Node(value)
if value< root.value:
root.left = insert(root.left,value)
else:
root.right = insert(root.right,value)
return root
def searchInBST(root,value):
current = root
while current.value != value:
if current.value > value:
current = current.left
else:
current = current.right
if current == None:
return "Not found"
return "Found"
def inorder(root):
if root != None:
inorder(root.left)
print(root.value,end=" ")
inorder(root.right)
def successor(root):
present = root
while present != None and present.left != None:
present = present.left
return present
def deleteNode(root,value):
if root == None:
return root
if value < root.value:
root.left = deleteNode(root.left, value)
elif value>root.value:
root.right = deleteNode(root.right, value)
else:
if root.left == None:
temp = root.right
root = None
return temp
elif root.right == None:
temp = root.left
root = None
return temp
temp = successor(root.right)
root.value = temp.value
root.right = deleteNode(root.right, temp.value)
return root
root = Node(8)
root = insert(root, 4)
root = insert(root, 12)
root = insert(root, 2)
root = insert(root, 6)
root = insert(root, 10)
root = insert(root, 14)
root = insert(root, 1)
root = insert(root, 3)
root = insert(root, 5)
root = insert(root, 7)
root = insert(root, 9)
root = insert(root, 11)
root = insert(root, 13)
root = insert(root, 15)
print("InOrder Traversal after inserting all nodes: ")
inorder(root)
root = insert(root, -10)
print("\nInOrder Traversal after inserting -10 : ")
inorder(root)
print("\nSearching -5 in the BST: ",searchInBST(root, -5))
print("Searching -5 in the BST: ",searchInBST(root, -10))
root = deleteNode(root,8)
print("After deleting node 8, inorder traversal:")
inorder(root)
root = deleteNode(root,-10)
print("\nAfter deleting node -10, inorder traversal:")
inorder(root)
Đầu ra:
InOrder Traversal after inserting all nodes 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 InOrder Traversal after inserting -10 : -10 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 Searching -5 in the BST: Not found Searching -5 in the BST: Found After deleting node 8, inorder traversal: -10 1 2 3 4 5 6 7 9 10 11 12 13 14 15 After deleting node -10, inorder traversal: 1 2 3 4 5 6 7 9 10 11 12 13 14 15
Ứng dụng của cây nhị phân
Dưới đây là một số ứng dụng phổ biến của Cây nhị phân:
- Sắp xếp dữ liệu nút theo thứ tự được sắp xếp
- Được sử dụng trong các đối tượng nút bản đồ và tập hợp trong thư viện ngôn ngữ lập trình.
- Tìm kiếm các phần tử trong cấu trúc dữ liệu
» Tìm hiểu hướng dẫn tiếp theo của chúng tôi về Thuật toán kết hợp
