Binary Search Tree(BST) - Insertion And Deletion

 Binary Search Tree(BST) 

Insertion And Deletion

Binary Search tree is a Data structure in which the elements are saved in the form of nodes such that they satisfy the following conditions:

1. The left subtree of a node has a key less than or equal to its parent node's key.

2. The right sub-tree of a node has a key greater than to its parent node's key

Insertion Operation 

Whenever an element is to be inserted, first loate its proper location. Start searching from the root node, then if the data is less than the value, search for empty location in the left sub-tree and insert the data,otherwise, search for an empty location in right sub-tree and insert the data.

Deletion Operation

The deletion Operation is performed as per the following three cases:

CASE 1: NO CHILD

For deleting a node with no child, simply remove the node from the tree.

CASE 2: ONE CHILD

For deleting a node with one child, simply remove the node and replace it with its child.

CASE 3: TWO CHILD

Suppose the node that is to be deleted is X. Do not delete X, choose either its in-order successor or its in-order predeccessor node R.

Copy the value of R to X, then recursively call delete on R until reaching one of the first two nodes.

If you choose in-order successor of a node, as right sub-tree is not NULL, then its in-order successor is node with least value in its right sub-tree, which will have a maximum of 1 sub-tree, So deleting it would fall in one of the first two cases 

C Program implementing Insertion and Deletion in BST

#include<stdio.h> #include<stdlib.h> typedef struct BST { struct BST *left,*right; int data; }node; node *root; node* create(int data) { node* r=(node*)malloc(sizeof(node)); r->data=data; r->left=NULL; r->right=NULL; return r; } node* insert(node* r,int data) { if(r==NULL) { r=create(data); return r; } if(data>=r->data) r->right=insert(r->right,data); if(data<r->data) r->left=insert(r->left,data); return r; } void In(node *r) { if(r==NULL) return; else { In(r->left); printf("%d ",r->data); In(r->right); } } node *min(node*root) { if(root->left==NULL||root==NULL) return root; else return min(root->left); } node *del(node * root,int data) { if(root==NULL) return root; else if(data<root->data) root->left=del(root->left,data); else if(data>root->data) root->right=del(root->right,data); else { if(root->left==NULL&&root->right==NULL) { free(root); root=NULL; } else if(root->left==NULL) { node* temp=root; root=root->right; free(temp); } else if(root->right==NULL) { node *temp=root; root=root->left; free(temp); } else { node *temp=min(root->right); root->data=temp->data; root->right=del(root->right,temp->data); } return root; } } main() { int data,c; while(1) { printf("1-Insert 2-Delete 3-Inorder 4-Exit"); scanf("%d",&c); switch(c) { case 1: printf("\nEnter the data"); scanf("%d",&data); root=insert(root,data); break; case 2: printf("\nEnter the data"); scanf("%d",&data); root=del(root,data); break; case 3: In(root);break; default: exit(0); } } }

Share Share Tweet Share Share Share

LIKE?

SHARE If you find this useful, please share with your friends and Community.
CODE TOGETHER..GROW TOGETHER.