Functions, Benefits and Disadvantages of Binary Search Tree

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

•  The left subtree accommodates solely the keys that are lesser than the important thing of the node.
•  The precise subtree accommodates solely the keys that are higher than the important thing of the node.
• The left and proper subtree each ought to be binary search tree.

Operations on Binary Search tree:

The three fundamental operations of BST:

1. Looking out, 
2. Insertion, and 
3. Deletion

1. Looking out in a BST:

Looking out in BST includes the comparability of the important thing values. If the important thing worth is the same as root key then, search profitable, if lesser than root key then search the important thing within the left subtree and if the secret’s higher than root key then search the important thing in the proper subtree.

Looking out in BST algorithm:-

• Test if tree is NULL, if the tree will not be NULL then observe the next steps.
• Evaluate the important thing to be searched with the basis of the BST.
• If the secret’s lesser than the basis then search within the left subtree.
• If the secret’s higher than the basis then search in the proper subtree.
• If the important thing is the same as root then, return and print search profitable.
• Repeat step 3, 4 or 5 for the obtained subtree.

2. Insertion in a BST:

Insertion in BST includes the comparability of the important thing values. If the important thing worth is lesser than or equal to root key then go to left subtree, discover an empty area following to the search algorithm and insert the information and if the secret’s higher than root key then go to proper subtree, discover an empty area following to the search algorithm and insert the information.

3. Deletion in a BST:

Deletion in BST includes three circumstances:-

First, search the important thing to be deleted utilizing looking algorithm and discover the node. Then, discover the variety of kids 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 little one: If the node to be deleted has one little one then, delete the node and place the kid of the node on the place of the deleted node.
• Case 3- If the node to be deleted has two kids: If the node to be deleted has two kids then, discover the inorder successor or inorder predecessor of the node in accordance with the closest succesful worth of the node to be deleted. Delete the inorder successor or predecessor utilizing the above circumstances. Exchange the node with the inorder successor or predecessor. 

Functions of Binary Search tree:

• BSTs are used for indexing.
• It is usually used to implement numerous looking algorithms.
• IT can be utilized to implement numerous information buildings.

Actual-time Utility of Binary Search tree:

• BSTs are used for indexing in databases.
• It’s used to implement looking algorithms.
• BSTs are used to implement Huffman coding algorithm.
• It is usually used to implement dictionaries.

Benefits of Binary Search Tree:

• BST is quick in insertion and deletion when balanced.
• BST is environment friendly.
• We will additionally do vary queries – discover keys between N and M (N <= M).
• BST code is straightforward as in comparison with different information buildings.

Disadvantages of Binary Search Tree:

• The primary drawback is that we must always all the time implement a balanced binary search tree. In any other case the price of operations is probably not logarithmic and degenerate right into a linear search on an array.
• Accessing the ingredient in BST is barely slower than array.
• A BST could be imbalanced or degenerated which may improve the complexity.