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 tôi duy trì 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 đứa trẻ.
- 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 thời gian ____.
Các thuộc tính tách một cây tìm kiếm nhị phân với cây nhị phân thông thường là
- Tất cả các nút của cây con trái nhỏ hơn nút gốc
- Tất cả các nút của cây con bên phải đều nhiều hơn nút gốc
- Cả hai 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 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 hoạt động 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ó các giá trị bên dưới gốc và mỗi cây con bên phải có các giá trị phía 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 phần cây con phù hợp; Chúng ta chỉ cần tìm kiếm ở 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 phần con phù hợp.
Algorithm:
If root == NULL
return NULL;
If number == root->data
return root->data;
If number < root->data
return search[root->left]
If number > root->data
return search[root->right]Hãy để chúng tôi cố gắng hình dung điều này với một sơ đồ.
Nếu giá trị được tìm thấy, chúng ta trả về giá trị để nó được truyền trong mỗi bước đệ quy như 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 struct*] bốn lần. Khi chúng tôi 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ị không được tìm thấy, cuối cùng chúng ta cũng đến được với đứa trẻ bên trái hoặc bên phải của một 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ị trí chính xác tương tự như tìm kiếm vì chúng tôi cố gắng duy trì quy tắc rằng cây con bên trái nhỏ hơn root và cây con bên phải lớn hơn root.
Chúng tôi tiếp tục đi vào 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 tôi đạt đến một điểm con bên trái hoặc bên phải là null, chúng tôi đặt nút mới ở đó.
Algorithm:
If node == NULL
return createNode[data]
if [data < node->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ó. Chúng ta hãy cố gắng hình dung cách chúng ta thêm một số vào một BST hiện có.
// 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.left = insertKey[root.left, key];
else 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.left = deleteRec[root.left, key];
else 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["\n\nAfter 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 < node->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 < root->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["\nAfter deleting 10\n"];
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 key 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 < node->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 < root->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