Binary Search Tree ( BST) and operations
A binary search tree (BST) is a data structure that organizes elements in a hierarchical structure, allowing for efficient search, insertion, and deletion operations. Here are the key properties and operations associated with a binary search tree:
Properties of a Binary Search Tree:
Binary Tree Structure:
Each node in the tree has at most two children: a left child and a right child.
The left subtree of a node contains only nodes with values less than the node's value.
The right subtree of a node contains only nodes with values greater than the node's value.
Ordering Property:
For any node n, all nodes in its left subtree have values less than n, and all nodes in its right subtree have values greater than n.
No Duplicates:
A binary search tree does not allow duplicate values.
Example: Figure shows a binary search tree. Notice that this tree is obtained by inserting the values 13, 3, 4, 12, 14, 10, 5, 1, 8, 2, 7, 9, 11, 6, 18 in that order, starting from an empty tree.
Operations on a Binary Search Tree:
Insertion:
To insert a new value into the tree, compare it to the current node's value.
If the value is less than the current node, go to the left subtree; if greater, go to the right subtree.
Repeat this process until an empty spot is found, then insert the new value as a leaf.
Insertion in a BST is also a straightforward operation. If we need to insert an element x, we first search for x. If x is present, there is nothing to do. If x is not present, then our search procedure ends in a null link. It is at this position of this null link that x will be included.
Algorithm
If the current node is null, create a new node with the given key and return it.Compare the key with the current node's key.
If the key is less than the current node's key, recursively insert into the left subtree.
If the key is greater than the current node's key, recursively insert into the right subtree.
Return the modified node.
pseudo code:
struct Node* insert(struct Node* node, int key) {
// Base case: if the tree is empty, create a new node
if (node == NULL) {
return createNode(key);
}
// Compare the key with the current node's key
if (key < node->key) {
// Recursively insert into the left subtree
node->left = insert(node->left, key);
} else if (key > node->key) {
// Recursively insert into the right subtree
node->right = insert(node->right, key);
}
// Return the modified node
return node;
}
Search:
To search for a value in the tree, compare it to the current node's value.
If the value is equal to the current node's value, the search is successful.
If the value is less than the current node, search in the left subtree; if greater, search in the right subtree.
Search is straightforward in a BST. Start with the root and keep moving left or right using the BST property. If the key we are seeking is present, this search procedure will lead us to the key. If the key is not present, we end up in a null link
Algorithm
If the root is null or the key is equal to the root's key, return the root (key found).
If the key is smaller than the root's key, recursively search in the left subtree.
If the key is greater than the root's key, recursively search in the right subtree.
Pseudo code
struct Node* search(struct Node* root, int key) {
// Base cases: the key is not present or the root is null
if (root == NULL || root->key == key) {
return root;
}
// Key is smaller than the root's key, search in the left subtree
if (key < root->key) {
return search(root->left, key);
}
// Key is greater than the root's key, search in the right subtree
return search(root->right, key);
}
Traversal:
In-order Traversal: Visit the left subtree, then the current node, and finally the right subtree. This results in a sorted list of values.
Pre-order Traversal: Visit the current node, then the left subtree, and finally the right subtree.
Post-order Traversal: Visit the left subtree, then the right subtree, and finally the current node.
Note that inorder traversal of a binary search tree always gives a sorted sequence of the values. This is a direct consequence of the BST property. This provides a way of sorting a given sequence of keys: first, create a BST with these keys and then do an inorder traversal of the BST so created.
- Minimum and Maximum:
Find the maximum value by traversing the right subtree until a leaf is reached.
Note that the highest valued element in a BST can be found by traversing from the root in the right direction all along until a node with no right link is found (we can call that the rightmost element in the BST).
The lowest valued element in a BST can be found by traversing from the root in the left direction all along until a node with no left link is found (we can call that the leftmost element in the BST).
pseudo code
int findMinimum(struct Node* root) {
// Base case: the leftmost leaf node contains the minimum value
while (root->left != NULL) {
root = root->left;
}
return root->key;
}
int findMaximum(struct Node* root) {
// Base case: the rightmost leaf node contains the maximum value
while (root->right != NULL) {
root = root->right;
}
return root->key;
}
Deletion:
To delete a node with a specific value:If the node is a leaf or has only one child, remove the node and replace it with its child.
If the node has two children, find the node's in-order successor (the smallest node in its right subtree), replace the node's value with the successor's value, and then delete the successor.
Deletion Example:
Note:Average case complexity of Search, Insert, and Delete Operations is O(log n), where n is the number of nodes in the tree.
If we repeatedly insert a sorted sequence of values to form a BST, we obtain a completely skewed BST. The height of such a tree is n - 1 if the tree has n nodes. Thus, the worst case complexity of searching or inserting an element into a BST having n nodes is O(n).
These operations ensure that a binary search tree maintains its properties, providing efficient access and manipulation of data with logarithmic time complexity for balanced trees. It's important to note that if the tree becomes unbalanced, the time complexity of operations may degrade to linear, and techniques like AVL trees or red-black trees can be used to maintain balance.
C Program Implementation BST Tree operations
/*****************************************************************************/
#include <stdio.h>
#include <stdlib.h>
struct Node {
int key;
struct Node* left;
struct Node* right;
};
struct Node *root=NULL,*temp=NULL;
struct Node* createNode(int key) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->key = key;
newNode->left = newNode->right = NULL;
return newNode;
}
struct Node* insert(struct Node* node, int key) {
// Base case: if the tree is empty, create a new node
if (node == NULL) {
return createNode(key);
}
// Compare the key with the current node's key
if (key < node->key) {
// Recursively insert into the left subtree
node->left = insert(node->left, key);
} else if (key > node->key) {
// Recursively insert into the right subtree
node->right = insert(node->right, key);
}
// Return the modified node
return node;
}
void inOrderTraversal(struct Node* node) {
if (node != NULL) {
// Traverse the left subtree
inOrderTraversal(node->left);
// Visit the current node
printf("%d---",node->key);
// Traverse the right subtree
inOrderTraversal(node->right);
}
}
void preOrderTraversal(struct Node* node) {
if (node != NULL) {
// Visit the current node
printf("%d---",node->key);
// Traverse the left subtree
preOrderTraversal(node->left);
// Traverse the right subtree
preOrderTraversal(node->right);
}
}
void postOrderTraversal(struct Node* node) {
if (node != NULL) {
// Traverse the left subtree
postOrderTraversal(node->left);
// Traverse the right subtree
postOrderTraversal(node->right);
// Visit the current node
printf("%d---",node->key);
}
}
struct Node* search(struct Node* root, int key) {
// Base cases: the key is not present or the root is null
if (root == NULL || root->key == key) {
return root;
}
// Key is smaller than the root's key, search in the left subtree
if (key < root->key) {
return search(root->left, key);
}
// Key is greater than the root's key, search in the right subtree
return search(root->right, key);
}
int findMinimum(struct Node* root) {
// Base case: the leftmost leaf node contains the minimum value
while (root->left != NULL) {
root = root->left;
}
return root->key;
}
int findMaximum(struct Node* root) {
// Base case: the rightmost leaf node contains the maximum value
while (root->right != NULL) {
root = root->right;
}
return root->key;
}
struct Node* inordersucc(struct Node* node) {
while (node->left != NULL) {
node = node->left;
}
return node;
}
// Function to delete a key from a BST
struct Node* deleteNode(struct Node* root, int key) {
if (root == NULL) {
return root;
}
if (key < root->key) {
root->left = deleteNode(root->left, key);
} else if (key > root->key) {
root->right = deleteNode(root->right, key);
} 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 = inordersucc(root->right);
root->key = temp->key;
root->right = deleteNode(root->right, temp->key);
}
return root;
}
int main()
{
int op,key;
do
{
printf("\n.menu\n1.insert\n2.preorder\n3.postorder\n4.inorder\n5.delete\n6.search\n7.Minimum\n8.Maximum\n9.exit\nenter option\n");
scanf("%d",&op);
switch(op)
{
case 1:printf("Enter the key:");
scanf("%d",&key);
if (root==NULL)
root=insert(root,key);
else
insert(root,key);
break;
case 2:printf("Preorder Traversal\n");
preOrderTraversal(root);
break;
case 3:printf("Postorder Traversal\n");
postOrderTraversal(root);
break;
case 4:
printf("Inorder traversal\n");
inOrderTraversal(root);
break;
case 5:
printf("Enter the key to delete:");
scanf("%d",&key);
root = deleteNode(root, key);
printf("In-Order Traversal after deleting %d: ", key);
inOrderTraversal(root);
break;
case 6:
printf("Enter the key to search:");
scanf("%d",&key);
temp=search(root,key);
if (temp==NULL)
printf("Key not Found \n");
else
printf("key found \n");
break;
case 7:printf("Minimum key element is =%d\n",findMinimum(root));
break;
case 8:printf("Maximum key element is =%d\n",findMaximum(root));
break;
}
}
while(op!=9);
return 0;
}
Example: University Questions
Show the structure of the binary search tree after adding each of the following values in the order 2,5,1,7,10,9,11,6.. What is the height of the created Tree.
Comments
Post a Comment