Advantages of Binary Search Trees over Hash Tables

by

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)

More Related Contents:

  1. How does a hash table work?
  2. Difference between binary tree and binary search tree
  3. Why hashmap lookup is O(1) i.e. constant time?
  4. Chained Hash Tables vs. Open-Addressed Hash Tables
  5. How do I prove or disprove that this function is Ω(n^1.5)?
  6. How do I express mutually recursive data structures in safe Rust?
  7. Why is std::map implemented as a red-black tree?
  8. Hash table runtime complexity (insert, search and delete)
  9. Firebase data structure and url
  10. Implement graph-like data structure in Rust
  11. lenses, fclabels, data-accessor – which library for structure access and mutation is better
  12. How do you validate a binary search tree?
  13. How Do I Choose Between a Hash Table and a Trie (Prefix Tree)?
  14. Quadtree for 2D collision detection
  15. Data structure: insert, remove, contains, get random element, all at O(1)
  16. Are duplicate keys allowed in the definition of binary search trees?
  17. What is a hash table and how do you make it in C? [closed]
  18. Searching a number in a rotated sorted Array
  19. How to implement a binary search tree in Python?
  20. Efficient implementation of immutable (double) LinkedList
  21. Efficient (and well explained) implementation of a Quadtree for 2D collision detection [closed]
  22. In Order Successor in Binary Search Tree
  23. What is the left-child, right-sibling representation of a tree? Why would you use it?
  24. Test whether a list contains a specific value in Clojure
  25. Difference between “Complete binary tree”, “strict binary tree”,”full binary Tree”?
  26. Why are hash table expansions usually done by doubling the size?
  27. Linked List vs Vector
  28. Why are entries in addition order in a .Net Dictionary?
  29. Data structure for quick time interval look up
  30. How to fix remove in RedBlackTree implementation?

Leave a Comment