Binary Search Tree

In a binary tree, every node can have maximum of two children but there is no order of nodes based on their values. In binary tree, the elements are arranged as they arrive to the tree, from top to bottom and left to right.

A binary tree has the following time complexities...

1. Search Operation - O(n)
2. Insertion Operation - O(1)
3. Deletion Operation - O(n)


To enhance the performance of binary tree, we use special type of binary tree known as Binary Search Tree. Binary search tree mainly focus on the search operation in binary tree. Binary search tree can be defined as follows...

Binary Search Tree is a binary tree in which every node contains only smaller values in its left subtree and only larger values in its right subtree.
A Binary Search Tree (BST) is a tree in which all the nodes follow the below-mentioned properties −
  • The left sub-tree of a node has a key less than or equal to its parent node's key.
  • The right sub-tree of a node has a key greater than to its parent node's key.
Thus, BST divides all its sub-trees into two segments; the left sub-tree and the right sub-tree and can be defined as −

left_subtree (keys)  ≤  node (key)  ≤  right_subtree (keys)

Representation

BST is a collection of nodes arranged in a way where they maintain BST properties. Each node has a key and an associated value. While searching, the desired key is compared to the keys in BST and if found, the associated value is retrieved.

Following is a pictorial representation of BST −
We observe that the root node key (27) has all less-valued keys on the left sub-tree and the higher valued keys on the right sub-tree.


Operations on a Binary Search Tree
The following operations are performed on a binary earch tree...
  • Search
  • Insertion
  • Deletion
Search Operation in BST

In a binary search tree, the search operation is performed with O(log n) time complexity. The search operation is performed as follows...
  • Step 1: Read the search element from the user
  • Step 2: Compare, the search element with the value of root node in the tree.
  • Step 3: If both are matching, then display "Given node found!!!" and terminate the function
  • Step 4: If both are not matching, then check whether search element is smaller or larger than that node value.
  • Step 5: If search element is smaller, then continue the search process in left subtree.
  • Step 6: If search element is larger, then continue the search process in right subtree.
  • Step 7: Repeat the same until we found exact element or we completed with a leaf node
  • Step 8: If we reach to the node with search value, then display "Element is found" and terminate the function.
  • Step 9: If we reach to a leaf node and it is also not matching, then display "Element not found" and terminate the function.
Insertion Operation in BST

In a binary search tree, the insertion operation is performed with O(log n) time complexity. In binary search tree, new node is always inserted as a leaf node. The insertion operation is performed as follows...
  • Step 1: Create a newNode with given value and set its left and right to NULL.
  • Step 2: Check whether tree is Empty.
  • Step 3: If the tree is Empty, then set set root to newNode.
  • Step 4: If the tree is Not Empty, then check whether value of newNode is smaller or larger than the node (here it is root node).
  • Step 5: If newNode is smaller than or equal to the node, then move to its left child. If newNode is larger than the node, then move to its right child.
  • Step 6: Repeat the above step until we reach to a leaf node (e.i., reach to NULL).
  • Step 7: After reaching a leaf node, then isert the newNode as left child if newNode is smaller or equal to that leaf else insert it as right child.
         100                               100
        /   \        Insert 40            /    \
      20     500    --------->          20     500 
     /  \                              /  \  
    10   30                           10   30
                                              \   
                                              40
Deletion Operation in BST

In a binary search tree, the deletion operation is performed with O(log n) time complexity. Deleting a node from Binary search tree has follwing three cases...
  • Case 1: Deleting a Leaf node (A node with no children)
  • Case 2: Deleting a node with one child
  • Case 3: Deleting a node with two children

Case 1: Deleting a leaf node

We use the following steps to delete a leaf node from BST...
  • Step 1: Find the node to be deleted using search operation
  • Step 2: Delete the node using free function (If it is a leaf) and terminate the function.
Case 2: Deleting a node with one child

We use the following steps to delete a node with one child from BST...
  • Step 1: Find the node to be deleted using search operation
  • Step 2: If it has only one child, then create a link between its parent and child nodes.
  • Step 3: Delete the node using free function and terminate the function.

Case 3: Deleting a node with two children

We use the following steps to delete a node with two children from BST...
  • Step 1: Find the node to be deleted using search operation
  • Step 2: If it has two children, then find the largest node in its left subtree (OR) the smallest node in its right subtree.
  • Step 3: Swap both deleting node and node which found in above step.
  • Step 4: Then, check whether deleting node came to case 1 or case 2 else goto steps 2
  • Step 5: If it comes to case 1, then delete using case 1 logic.
  • Step 6: If it comes to case 2, then delete using case 2 logic.
  • Step 7: Repeat the same process until node is deleted from the tree.
1) Node to be deleted is leaf: Simply remove from the tree.
              50                            50
           /     \         delete(20)      /   \
          30      70       --------->    30     70 
         /  \    /  \                     \    /  \ 
       20   40  60   80                   40  60   80

2) Node to be deleted has only one child: Copy the child to the node and delete the child
              50                            50
           /     \         delete(30)      /   \
          30      70       --------->    40     70 
            \    /  \                          /  \ 
            40  60   80                       60   80

3) Node to be deleted has two children: Find inorder successor of the node. Copy contents of the inorder successor to the node and delete the inorder successor. Note that inorder predecessor can also be used.
              50                            60
           /     \         delete(50)      /   \
          40      70       --------->    40    70 
                 /  \                            \ 
                60   80                           80
The important thing to note is, inorder successor is needed only when right child is not empty. In this particular case, inorder successor can be obtained by finding the minimum value in right child of the node.

Example

Construct a Binary Search Tree by inserting the following sequence of numbers...
10,12,5,4,20,8,7,15 and 13

Above elements are inserted into a Binary Search Tree as follows...

0 comments:

Post a Comment