CODEWITHSUNDEEP
data-structuresbinary-search-treeordered-map
J. Newbie
J. Newbie

Reputation: 59

Utility of an ordered map using binary search tree

I am currently learning different data structures and I'm facing a little problem. What's the use of an ordered map implemented using a binary search tree? I mean, when is it good to do it so? A practical example would be great!

Upvotes: 2

Views: 694

Answers (1)

templatetypedef
templatetypedef

Reputation: 372982

There are a ton of different use cases for balanced BSTs and I can't possibly list all of them here, but here are a few good use cases:

  1. BSTs support range queries, where you can ask for all entries between two values, efficiently. Specifically, in a BST with n entries, if you perform a range query where k elements will be returned, the runtime is O(log n + k). Compare that to, say, using a hash table, where the runtime would be O(n). This can be used if you're interested in doing time series analysis of a set of data and want to explore data in certain ranges.

  2. BSTs support successor and precedecessor queries. Given a BST, you can ask for the smallest element greater than some value or for the largest element less than some value in time O(log n). Collectively, this lets you find the element in a BST that's closest to some target value in time O(log n), which can be useful if you're getting noisy data and want to map it to the closest entry in your data set. Compare this with hash tables, where this would take time O(n).

  3. BSTs are worst-case efficient. Many common types of binary search trees, like red/black trees and AVL trees, give worst-case guarantees on the costs of their operations. Contrast this with a hash table, where queries are expected to take constant time, but can degrade with a bad hash function or just due to bad luck. Additionally, every now and then a hash table has to rehash, which can take a while, but red/black trees and AVL trees don't have cases like these. (There are some types of balanced BSTs like splay trees and scapegoat trees that aren't worst-case efficient, but that's a different story.)

  4. BSTs give easy access to the minimum and maximum values in time O(log n), even if insertions and deletions are intermixed. Hash tables can't support these operations.

  5. BSTs support ordered iteration, so if you have an application where you want to view the data in sorted order, you get it "for free" with BSTs. One example of this would if, for example, you were loading student data and wanted to see the scores in sorted order. Hash tables don't support this - you'll have to pull out the data and sort it to get it back in sorted order.

  6. BSTs can be augmented. If you take an algorithms course, you'll probably learn about a technique called tree augmentation in which you can add extra information in each node of the BST to solve a ton of problems much faster than it would initially appear possible to do. For example, you can augment BSTs to instantly be able to read off the median element, or the closest pair of points, or to solve many algorithmic problems efficiently when the underlying data is changed. Hash tables don't support these operations.

  7. BSTs support efficient split and join. Red/black trees and splay trees have the interesting property that, given two trees where all the keys in one are less than the keys in the other, the trees can be combined together into a single tree in time O(log n) - much faster than visiting all elements of the tree! You can also split any red/black tree or splay tree into two smaller trees by partitioning the tree into "elements less than some value" or "elements more than some value" in time O(log n). It's not trivial to do it, but it's possible. The time bounds on the corresponding operations on a hash table are O(n).

If I think of anything else, I'll update this list. Hope this helps!

Upvotes: 2

Related Questions