Table of Contents
hide
Introduction of Binary Search Tree
- They are also called Ordered Binary Trees as each node in BST is placed according to a specific order.
Definition
- A binary search tree is a non-linear, non-cyclic data structure and is an extension/type of binary tree that may be empty, or each node has at most two children.
- A binary search tree is either empty or it contains a root node together with two binary search trees called the left subtree and the right subtree of the root.
Characteristics
- A BST is said to be perfectly balanced if for every internal node, there are equal number of nodes in its left and right sub-trees.
- Degenerate Binary Search Tree is a BST in which all the elements are arranged in one side only i.e., either left or right side only.
- Each node in the BST is itself a BST i.e., BST is naturally recursive in nature.
Properties
- Each node in BST has <= 2 children.
- The left subtree of a node contains only nodes with keys lesser than the node’s key i.e. All keys in left subtree are smaller than node’s key.
- The right subtree of a node contains only nodes with keys greater than the node’s key i.e. All keys in right subtree are larger than node’s key.
- The left and right subtree each must also be a binary search tree.
Implementation/Representation of BST
- The node of a typical BST can be represented as –
struct bst
{
string data; int value; //root node
string data; int value; //root node
struct bst * left; // left subtree
struct bst * right; // right subtree
};
};
Operation in BST
- There are some common operations usually seen in a typical BST. These are –
- Creation of new/fresh BST.
- Traversing/Printing the node values in BST.
- Insertion of a new node in the existing BST.
- Deletion of one/more node from an existing BST.
- Finding/Searching specific node value from an existing BST.
Algorithm for Deletion of the node from an existing BST:-
- A binary search tree (BST) is a binary tree data structure where each node has at most two children, and the values in the left subtree of a node are less than or equal to the node’s value, while the values in the right subtree are greater than the node’s value.
- Deleting a node from a BST involves maintaining the property of BST while removing the desired node.
- The step-by-step algorithm for deleting a node from a BST is as follows:
Step 1: Start at the root of the tree.
Step 2: Search for the node to delete:
- If the node to delete has a value less than the current node’s value, move to the left subtree.
- If the node to delete has a value greater than the current node’s value, go to the right subtree.
- If the current node’s value is equal to the value of the node to delete, we have found the node to delete.
Step 3: Once we have found the node to delete, there are three conditions/cases to consider:
a. Node having no children (leaf/terminal node):
- Remove the node from the tree.
b. Node with one child either left or right:
- Replace the root node to delete with its only child. If it has the left child, replace it with the left child value; if it has the right child, replace it with the right child value.
c. Node with two children:
- When the node with two children is deleted, its place is filled with either a left subtree(the largest node) value or a right subtree (the smallest)value and re-adjusting using the BST rule.
Traversal/Printing in BST
- Traversal is a visit to every node in the BST and perform some specific
operation on it to get the stored values. - There are three universal steps occur in BST traversal in different order. These are –
1. Visit the root node.
2. Traverse its left (associated) subtree.
3. Traverse its right (associated) subtree - There are 3 common types of traversals in BST. These are –
(a) Pre-Order Traversal
The order of traversal in pre-order traversal is-
1. Visit the root node first.
2. Now, Traverse its left (associated) subtree.
3. Then, Traverse its right (associated) subtree
(b) In-Order Traversal
The order of traversal in In-order traversal is-
1. Traverse the left (associated) subtree first.
2. Now, visit the root node.
3. Then, traverse the right (associated) subtree
(c) Post-Order Traversal
The order of traversal in post-order traversal is-
1.Traverse the left (associated) subtree first.
2. Now, traverse the right (associated) subtree.
3. Then, visit the root node.
Level-Order Traversal:
- Here, each node of the BST is traversed level by level (top to bottom) in order of its appearance/location.
- In each level, traversing order is from left to right.
Advantages
- Searching is very effective and becomes very easy due to arrangement of data one-sided i.e., smaller than root is in left side and higher in right side.
- The arrangement of all the nodes of BST in a specific order.
- BST has an efficient & effective working when compared to arrays and linked lists.
- Insertion and deletion operations are comparatively faster than other data structures like linked lists and arrays.
Disadvantages
- An imbalanced or degenerated form of BST has less usability and more complex.
Use/Applications
Some major/important applications of BST are as follows: –
- BST is used to implement multilevel indexing structure in database applications to handle a large no. of data items.
- BST is also used in applications that require a sorted list as input like the online stores.
- BST is used to implement Huffman coding algorithm.
- BSTs are also used to evaluate the expression by constructing expression trees.
- BST is also used in the construction of digital dictionary.
- BST can also be used to implement various efficient searching algorithms.
0 Comments