0

I'm trying to make a search tree that can store duplicate keys and have different values for said keys.

Basically, I have hashcode in the form of a bit string. The value is that bit string, and the key is the number of 1's that appear in the bit string.

For example, I could have two bit strings:

bitstring1 = "00001111";
bitstring2 = "11110000";

So they have identical keys:

key1 = 4;
key2 = 4;

Is it possible to implement this into a search tree?

fps
  • 33,623
  • 8
  • 55
  • 110
Nick
  • 13
  • 4
  • Why don't you use a `Map`? It is hard to understand why you need a search tree for this. – fps Nov 23 '17 at 21:27
  • I have to use a tree, my instructor said something about a B+ tree but it looks incredibly complicated. – Nick Nov 23 '17 at 21:30
  • OK, please clarify that on the question: that this is an assignment and your instructor told you you *had to* use a B+ tree. – fps Nov 23 '17 at 21:32

1 Answers1

0

One possibility is a binary search tree in which the nodes contain a list of values that match the key. That's a very simple addition to a standard binary search tree, but could become inefficient if there are a lot of values for a key because each access would require an O(n) (where n is the number of values for that key) sequential search of that key's values.

If lookups are much more frequent than additions or deletions, you could make the values list sorted. Insertions and deletions would still require that sequential scan, but lookups could do binary search. Depending on the application, this is a good compromise.

Another possibility is to make that list of values another binary search tree. So your nodes would contain a binary tree of values. That would be more efficient than a sorted list, but it would cost more memory.

Jim Mischel
  • 131,090
  • 20
  • 188
  • 351