What is binary Search tree?
BST is the node-based binary tree data structure. A binary tree is a tree that has almost 2 children. The Binary search tree differs from the Binary tree in the aspect that:-
- The left child of the node is always smaller than the node.
- the right child of the node is always greater than the node.
- the left subtree and right subtree are also binary trees.
The above properties of Binary Search Tree provide an ordering among keys so that the operations like search, minimum and maximum can be done fast. This enables us to search an element in O(log n) time.
We make BST using the linked list that has two pointers one to point to the left child and another to point to the right child.
There is also a concept called balancing. we call a tree balanced if for all nodes the difference between the heights of left and right subtrees is not greater than one.
What is Hash Table?
Hash Table is a data structure that stores data in an associative manner. So there is a Hash function that decides what would be the key and what values will be associated with that key. If during hashing more than 1 value is associated with the same key, they are linked to form a chain. This is called chaining.
The hash function is very important in Hash Table because it decides the chaining and complexity.
Searching usually takes 0(1) time in the Hash table if you ignore the chaining.
Now to our main topic.....
What are the advantages of self-balancing BST over Hash Table?
First of all, let us understand what are the advantages of Hash Table over self-balancing BST.
| Function | self-balancing BST | Hash Table |
|---|---|---|
| Searching | O(log n) | O(1) |
| Insert | O(log n) | O(1) |
| Delete | O(log n) | O(1) |
Here you can clearly notice Hash Table has the upper hand over the BST in searching inserting and deleting an element. But self-balancing BST is advantageous over Hash Table over these points.
- All the operations in Self-balancing BST take O(log n) time but for Hash Table, O(1) is the average time some operations could be very costly, especially related to table resizing.
- We can get all keys in sorted order by just doing Inorder Traversal of BST. This is not a natural operation in Hash Tables and requires extra effort.
- BSTs are easy to implement and we could easily implement our customized BST. But we need to rely on provided libraries for Hash Table.
Plus Hash Maps are bulky and require a lot of space while BSTs are light.
That's all from me today. Happy coding.