A binary search tree (BST) is a type of binary tree data structure that follows a specific ordering property. In a BST, the values in the left subtree of a node are smaller than the value at the node, and the values in the right subtree are larger. This property enables efficient searching, insertion, and deletion operations.
Let's consider an example to illustrate the concept of a binary search tree. Suppose we have a set of numbers: [8, 3, 10, 1, 6, 14, 4, 7, 13]. We can construct a binary search tree from these numbers as follows:
```
8
/ \
3 10
/ \ \
1 6 14
/ \ /
4 7 13
```
In this example, the number 8 is chosen as the root of the tree. Then, we insert the remaining numbers one by one while maintaining the binary search tree property.
The tree starts with the root node containing the value 8. The number 3 is less than 8, so it becomes the left child of 8. Next, the number 10 is greater than 8, so it becomes the right child of 8.
Continuing this process, the number 1 is less than 8 and 3, so it becomes the left child of 3. The number 6 is greater than 3 but less than 8, so it becomes the right child of 3. Similarly, the numbers 4 and 7 become the left and right children of 6, respectively.
The numbers 14 and 13 are greater than 8 and 10, so they become the right children of 10 and 14, respectively.
Now that we have constructed the binary search tree, we can perform various operations on it:
1. Searching: To search for a value in a BST, we start at the root and compare the target value with the current node. If they match, we have found the value. If the target is less than the current node, we move to the left subtree. If the target is greater, we move to the right subtree. We continue this process until we find the value or reach a null node.
2. Insertion: To insert a new value into a BST, we compare it with the nodes starting from the root. If the value is less than the current node, we move to the left subtree. If it is greater, we move to the right subtree. We repeat this process until we find an appropriate null position where we can insert the new value.
3. Deletion: Deleting a node from a BST involves various cases. If the node to be deleted is a leaf (has no children), we can simply remove it. If the node has one child, we replace the node with its child. If the node has two children, we find either the maximum value in its left subtree (called the predecessor) or the minimum value in its right subtree (called the successor). We swap the node's value with the predecessor/successor, and then delete the predecessor/successor node.
Binary search trees provide an efficient way to store and search for data in sorted order. They have a time complexity of O(log n) for average case and O(n) for the worst case (when the tree becomes unbalanced).
Here's an example implementation of a binary search tree (BST) in C, including the operations of searching, insertion, and deletion:
#include <stdio.h>
#include <stdlib.h>
// Structure for a node in BST
struct Node {
int data;
struct Node* left;
struct Node* right;
};
// Function to create a new node
struct Node* createNode(int value) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = value;
newNode->left = NULL;
newNode->right = NULL;
return newNode;
}
// Function to insert a value into BST
struct Node* insert(struct Node* root, int value) {
if (root == NULL) {
return createNode(value);
}
if (value < root->data) {
root->left = insert(root->left, value);
} else if (value > root->data) {
root->right = insert(root->right, value);
}
return root;
}
// Function to search for a value in BST
struct Node* search(struct Node* root, int value) {
if (root == NULL || root->data == value) {
return root;
}
if (value < root->data) {
return search(root->left, value);
}
return search(root->right, value);
}
// Function to find the minimum value in BST
struct Node* minValueNode(struct Node* node) {
struct Node* current = node;
while (current && current->left != NULL) {
current = current->left;
}
return current;
}
// Function to delete a value from BST
struct Node* deleteNode(struct Node* root, int value) {
if (root == NULL) {
return root;
}
if (value < root->data) {
root->left = deleteNode(root->left, value);
} else if (value > root->data) {
root->right = deleteNode(root->right, value);
} else {
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;
}
struct Node* temp = minValueNode(root->right);
root->data = temp->data;
root->right = deleteNode(root->right, temp->data);
}
return root;
}
// Function to traverse the BST in-order
void inorderTraversal(struct Node* root) {
if (root != NULL) {
inorderTraversal(root->left);
printf("%d ", root->data);
inorderTraversal(root->right);
}
}
// Driver code
int main() {
struct Node* root = NULL;
// Insertion
root = insert(root, 8);
root = insert(root, 3);
root = insert(root, 10);
root = insert(root, 1);
root = insert(root, 6);
root = insert(root, 14);
root = insert(root, 4);
root = insert(root, 7);
root = insert(root, 13);
// In-order traversal
printf("In-order traversal: ");
inorderTraversal(root);
printf("\n");
// Searching
int searchValue = 6;
struct Node* searchResult = search(root, searchValue);
if (searchResult != NULL) {
printf("Value %d found in the BST.\n", searchValue);
} else {
printf("Value %d not found in the BST.\n", searchValue);
}
// Deletion
int deleteValue = 6;
root = deleteNode(root, deleteValue);
printf("After deleting %d: ", deleteValue);
inorderTraversal(root);
printf("\n");
return 0;
}
OUTPUT:
In-order traversal: 1 3 4 6 7 8 10 13 14
Value 6 found in the BST.
After deleting 6: 1 3 4 7 8 10 13 14
Process returned 0 (0x0) execution time : 0.042 s
Press any key to continue.
In this example, we first create a structure called Node to represent a node in the BST. The createNode function is used to create a new node with a given value. The insert function inserts a value into the BST, maintaining the ordering property. The search function searches for a value in the BST. The minValueNode function finds the node with the minimum value in a given subtree. The deleteNode function deletes a value from the BST while maintaining the ordering property. The inorderTraversal function traverses the BST in-order.
In the main function, we create a BST and perform various operations. We insert values into the BST, perform an in-order traversal, search for a value, delete a value, and then perform another in-order traversal to see the updated tree.
Please note that this is a simplified example for educational purposes, and it doesn't include error handling or balanced tree algorithms. In practice, you may want to handle additional cases and ensure the tree remains balanced for optimal performance.
0 Comments