Operation of Insertation , Deletion, Searching & Modification of data in Binary Search

How Binary Search Tree Works?

The tree always has a root node and further child nodes, whether on the left or right. The algorithm performs all the operations by comparing values with the root and its further child nodes in the left or right sub-tree accordingly.

Depends upon the element to be inserted, search, or deleted, after the comparison, the algorithm can easily drop the left or right subtree of the root node.

BST primarily offers the following three types of operations for your usage:

• Search: searches the element from the binary tree
• Insert: adds an element to the binary tree
• Delete: delete the element from a binary tree

Each operation has its own structure and method of execution/analysis, but the most complex of all is the Delete operation.

Search Operation

Always initiate analyzing tree at the root node and then move further to either the right or left subtree of the root node depending upon the element to be located is either less or greater than the root.

1. The element to be searched is 10
2. Compare the element with the root node 12, 10 < 12, hence you move to the left subtree. No need to analyze the right-subtree
3. Now compare 10 with node 7, 10 > 7, so move to the right-subtree
4. Then compare 10 with the next node, which is 9, 10 > 9, look in the right subtree child
5. 10 matches with the value in the node, 10 = 10, return the value to the user.

Algorithm for Searching in BST:

search(element, root)
     if !root
    	return -1
     if root.value == element
    	return 1
     if root.value < element
    	search(element, root.right)
      else
    	search(element, root.left)

Insert Operation

This is a very straight forward operation. First, the root node is inserted, then the next value is compared with the root node. If the value is greater than root, it is added to the right subtree, and if it is lesser than the root, it is added to the left subtree.

1. There is a list of 6 elements that need to be inserted in a BST in order from left to right
2. Insert 12 as the root node and compare next values 7 and 9 for inserting accordingly into the right and left subtree
3. Compare the remaining values 19, 5, and 10 with the root node 12 and place them accordingly. 19 > 12 place it as the right child of 12, 5 < 12 & 5 < 7, hence place it as left child of 7. Now compare 10, 10 is < 12 & 10 is > 7 & 10 is > 9, place 10 as right subtree of 9.

Algorithm for Inserting a Node in BST:

insert (element, root)
    Node x = root
    Node y = NULL
    while x:
    	y = x
    if x.value < element.value
        x = x.right
    else
        x = x.left
    if y.value < element
    	y.right = element
    else
    	y.left = element

Delete Operations

For deleting a node from a BST, there are some cases, i.e. deleting a root or deleting a leaf node. Also, after deleting a root, we need to think about the root node.

Say we want to delete a leaf node, we can just delete it, but if we want to delete a root, we need to replace the root’s value with another node. Let’s take the following example:

• Case 1- Node with zero children: this is the easiest situation, you just need to delete the node which has no further children on the right or left.
• Case 2 – Node with one child: once you delete the node, simply connect its child node with the parent node of the deleted value.
• Case 3 Node with two children: this is the most difficult situation, and it works on the following two rules
• 3a – In Order Predecessor: you need to delete the node with two children and replace it with the largest value on the left-subtree of the deleted node
• 3b – In Order Successor: you need to delete the node with two children and replace it with the smallest value on the right-subtree of the deleted node

1. This is the first case of deletion in which you delete a node that has no children. As you can see in the diagram that 19, 10 and 5 have no children. But we will delete 19.
2. Delete the value 19 and remove the link from the node.
3. View the new structure of the BST without 19

1. This is the second case of deletion in which you delete a node that has 1 child, as you can see in the diagram that 9 has one child.
2. Delete the node 9 and replace it with its child 10 and add a link from 7 to 10
3. View the new structure of the BST without 9

1. Here you will be deleting the node 12 that has two children
2. The deletion of the node will occur based upon the in order predecessor rule, which means that the largest element on the left subtree of 12 will replace it.
3. Delete the node 12 and replace it with 10 as it is the largest value on the left subtree
4. View the new structure of the BST after deleting 12

1. 1 Delete a node 12 that has two children
2. 2 The deletion of the node will occur based upon the In Order Successor rule, which means that the largest element on the right subtree of 12 will replace it
3. 3 Delete the node 12 and replace it with 19 as it is the largest value on the right subtree
4. 4 View the new structure of the BST after deleting 12

Algorithm for Deleting a Node:

delete (value, root):
    Node x = root
    Node y = NULL
# searching the node
    while x:
    	y = x
    if x.value < value
        x = x.right
    else if x.value > value
        x = x.left
    else if value == x
        break
# if the node is not null, then replace it with successor
    if y.left or y.right:
    	newNode = GetInOrderSuccessor(y)
    	root.value = newNode.value
# After copying the value of successor to the root #we're deleting the successor
    	free(newNode)
    else
    	free(y)

Note:

• BST is an advanced level algorithm that performs various operations based on the comparison of node values with the root node.
• Any of the points in a parent-child hierarchy represents the node. At least one parent or root node remains present all the time.
• There are a left subtree and right subtree. The left subtree contains values that are less than the root node. However, the right subtree contains a value that is greater than the root node.
• Each node can have either zero, one, or two children.
• A binary search tree facilitates primary operations like search, insert, and delete.
• Delete being the most complex have multiple cases, for instance, a node with no child, node with one child, and node with two children.
• The algorithm is utilized in real-world solutions like games, autocomplete data, and graphics.