Menu
What are the advantages of binary search trees over hash tables?
Hash tables can look up any element in Theta(1) time and it is just as easy to add an element....but I'm not sure of the advantages going the other way around.
302
MySQL picked BTree because it is more flexible than Hash (because it can handle ranges), while not being significantly slower than Hash. Arguably, BTree is slower to O(1) due to caching of blocks. Non-leaf nodes tend to be cached and stay in RAM, even if the leaf nodes come and go (for large tables).
Advantages of Binary Search Tree:BST is fast in insertion and deletion when balanced. BST is efficient. We can also do range queries – find keys between N and M (N <= M). BST code is simple as compared to other data structures.
But with Hashing, Θ(1) is average time and some particular operations may be costly i.e, O(n2 ), especially when table resizing happens. In BST we can do range searches efficiently but in Hash Table we cannot do range search efficienly. BST are memory efficient but Hash table is not.
However, in the average case scenario, hash lookup is significantly faster than binary search. In real applications, we mainly consider an average case scenario in order to test and compare the performance of different methods. Therefore, hash lookup is a better choice in such cases.
Almost always, yes. If you run into a lot of collisions, then those times might grow up to O(n). These times also depend on your hashing function.
Throughout this answer, n is the number of keys in the dictionary. The short answer is that hash tables are faster in most cases, but can be very bad at their worst. Search trees have many advantages, including tame worst-case behavior, but are somewhat slower in typical cases.
One advantage that no one else has pointed out is that binary search tree allows you to do range searches efficiently.
In order to illustrate my idea, I want to make an extreme case. Say you want to get all the elements whose keys are between 0 to 5000. And actually there is only one such element and 10000 other elements whose keys are not in the range. BST can do range searches quite efficiently since it does not search a subtree which is impossible to have the answer.
While, how can you do range searches in a hash table? You either need to iterate every bucket space, which is O(n), or you have to look for whether each of 1,2,3,4... up to 5000 exists. (what about the keys between 0 and 5000 are an infinite set? for example keys can be decimals)
112
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
