Advantages Of Binary Search Tree Over Hash Table
Advantages Of Binary Search
Tree Over Hash Table
In programming,
we have come across BST and Hash Table applications very often. But most of the
times we prefer to use hash table even if the space complexity increases.
But in this
article, we will be looking into the advantages and places where we prefer to
use Binary Search Tree over Hash Table.
Let us first
revisit BST and Hash table.
Ø What is Binary Search Tree ?
A BST is a type
of tree data structure where for every node, all
the nodes to the left of this node have value lesser than the current node’s
value and all the nodes to the right of this node has value greater than the
current node’s value along with the fact that both left subtree and right
subtree are Binary Search Trees.
Ø Example:
One application
of this is basically when we get a stream of incoming data and we want to
arrange them systematically in a sorted order in efficient way. As BST
insertion takes time.
Even Searching for a key in Binary
Search Tree takes 0 (logn) time
Ø What is Hash Table ?
Ø Adavantages Binary Search Tree vs Hash Table
So now we have arrived at the point where we know the proper uses of these two data structures, so we can now discuss when to prefer Binary Search Trees. Let us go back to our BST created by our programme.
v When we have to find nearest successor, Least Common Ancestors etc. types of problems where we require the property of BST, we cannot use Hash Table as it will complicate and increase the time complexity.
v In Binary Search Trees we don’t have to deal with collisions due to same keys inserted again and again whereas the average time complexity of a hash table arises due to collision handling of the hash functions.v Hash Table and hash maps generally are cumbersome to customize as we directly use the library functions for those whereas BST is quite easily customisable and hence scalable.
Multilevel
Hashing that is common in Database
Storage Architectures uses this for indexing with huge memory blockage.
- Hash Table has moreover lesser security in smaller architectures as the hash function is susceptible to manipulation and if used to make unnecessary collisions which will, in turn, result in more time complexity.
- Hash Tables are time-consuming when we have to do range queries whereas Binary Search Trees can efficiently handle range queries.
- With Self-Balancing BSTs, all operations are guaranteed to work in O(Logn) time. But with Hashing, Θ(1) is average time and some particular operations may be costly, especially when table resizing happens.
- Hash Tables are not good for indexing as we can see above multilevel indexing will waste a lot of
extra memory and hence most of the time B & B+ trees are
used in database architectures.
If we want to find the predecessor or successor of
a node in a hash table, we have to maintain a parent of every node and then
traverse to all those nodes one by one which will take more time than which is
the used time complexity of Binary Search Tree in this case.
Data
Migration in terms of Hash Table is very
costly as the whole static memory has to be transferred even if some keys don’t
contain any values whereas Binary Search Trees can literally build the whole
tree in logarithmic time and multiplied by the number of elements being
inserted which is more efficient.
Ø Conclusion
Hence, we can see that in most of the practical situations we use a
Binary Search Tree rather than a Hash Table to reduce the space complexity and
easy scalability of the data structure. Hope this article is useful to aspire
developers and programmers.
THANK YOU!
Comments
Post a Comment