CODEWITHSUNDEEP
javabinary-search-tree
user1377000
user1377000

Reputation: 1483

Duplicates in a Binary Search Tree

What's an elegant way of handling duplicates in a Binary Search Tree? Let's assume each key will have several different values associated. What I need to do is iterate over all values in order. So if I had 2 values A and B with key 1, and one value C with key 2, I would like to get pairs: (1,A), (1,B), (2,C), when calling something like TreeIterator.next();

I can think of:

Any other suggestions? As a general guideline, i would like the Tree implementation to be as abstract as possible.

Upvotes: 0

Views: 383

Answers (1)

Jon Skeet
Jon Skeet

Reputation: 1503889

It sounds like basically you do want a list of values for each key, yes. So the process of adding to the map is:

  • Does key exist?
    • If so, add value to the existing list.
    • If not, create a new node in the tree at the appropriate point (as normal) and start with a list of one value

When iterating over the map, your general pattern is:

  • Yield all values from the left node (smaller keys)
  • Yield all values for this node - (key, value1), (key, value2) etc
  • Yield all values from the right node (larger keys)

Of course, if you don't need to implement this yourself for learning purposes, you could use a ready-made multimap, such as Guava's TreeMultimap. If you are implementing it for self-education, I'd start off by implementing a "normal" binary search map, and then going on from there.

Upvotes: 1

Related Questions