In computer science Binary search tree or BST is one of most common data structure used. A Binary search tree is a binary tree which follow the below properties
One of the most advantage of Binary search tree is , sorting and searching operations are very efficient. Worst case complexity of searching using BST method is O(log(n)) where n is no. of nodes. And worst case for sorting using BST is O(n), Where as traditional sorting algorithms like bubble sort or quick sort the worst case is O(n*n). In the average case for the sorting in BST, the complexity reduces to (log(n)).
Operations on Binary Search Tree:
Applications of the binary search tree:
- left sub tree of the node should contain less than or equal to node
- right sub tree of the node should contain the greater than to the node
- both left and right subtrees should also be a binary search tree
 |
| Binary Search Tree |
One of the most advantage of Binary search tree is , sorting and searching operations are very efficient. Worst case complexity of searching using BST method is O(log(n)) where n is no. of nodes. And worst case for sorting using BST is O(n), Where as traditional sorting algorithms like bubble sort or quick sort the worst case is O(n*n). In the average case for the sorting in BST, the complexity reduces to (log(n)).
Operations on Binary Search Tree:
- Searching
- inserting
- deleting
- sort
- traversal
Applications of the binary search tree:
- Dictionaries
- sets
- multi sets
- associate array
1 comment:
Great readingg this
Post a Comment