Applications, Advantages and Disadvantages of Binary Search Tree

Binary Search Tree (BST) is a special binary tree that has the properties:

  •  The left subtree contains only the keys which are lesser than the key of the node.
  •  The right subtree contains only the keys which are greater than the key of the node.
  • The left and right subtree both should be binary search tree.

Operations on Binary Search tree:

The three basic operations of BST:

  1. Searching,
  2. Insertion, and
  3. Deletion

1. Searching in a BST:

Searching in BST involves the comparison of the key values. If the key value is equal to root key then, search successful, if lesser than root key then search the key in the left subtree and if the key is greater than root key then search the key in the right subtree.

Searching in BST algorithm:-

  • Check if tree is NULL, if the tree is not NULL then follow the following steps.
  • Compare the key to be searched with the root of the BST.
  • If the key is lesser than the root then search in the left subtree.
  • If the key is greater than the root then search in the right subtree.
  • If the key is equal to root then, return and print search successful.
  • Repeat step 3, 4 or 5 for the obtained subtree.

2. Insertion in a BST:

Insertion in BST involves the comparison of the key values. If the key value is lesser than or equal to root key then go to left subtree, find an empty space following to the search algorithm and insert the data and if the key is greater than root key then go to right subtree, find an empty space following to the search algorithm and insert the data.

3. Deletion in a BST:

Deletion in BST involves three cases:-

First, search the key to be deleted using searching algorithm and find the node. Then, find the number of children of the node to be deleted.

  • Case 1- If the node to be deleted is leaf node: If the node to be deleted is a leaf node, then delete it.
  • Case 2- If the node to be deleted has one child: If the node to be deleted has one child then, delete the node and place the child of the node at the position of the deleted node.
  • Case 3- If the node to be deleted has two children: If the node to be deleted has two children then, find the inorder successor or inorder predecessor of the node according to the nearest capable value of the node to be deleted. Delete the inorder successor or predecessor using the above cases. Replace the node with the inorder successor or predecessor.

Applications of Binary Search tree:

  • BSTs are used for indexing.
  • It is also used to implement various searching algorithms.
  • IT can be used to implement various data structures.

Real-time Application of Binary Search tree:

  • BSTs are used for indexing in databases.
  • It is used to implement searching algorithms.
  • BSTs are used to implement Huffman coding algorithm.
  • It is also used to implement dictionaries.

Advantages of Binary Search Tree:

  • BST is fast in insertion and deletion when balanced.
  • BST is efficient.
  • We can also do range queries – find keys between N and M (N <= M).
  • BST code is simple as compared to other data structures.

Disadvantages of Binary Search Tree:

  • The main disadvantage is that we should always implement a balanced binary search tree. Otherwise the cost of operations may not be logarithmic and degenerate into a linear search on an array.
  • Accessing the element in BST is slightly slower than array.
  • A BST can be imbalanced or degenerated which can increase the complexity.
By Julio MarchiPosted on