I'm currently implementing a red-black binary search tree for geometric interval search. I'm saving in the tree segments containing a startpoint and a endpoinit where the startpoint is the key entry to the tree. My concern is to be able to save into the tree segments which have the duplicate starting point (or if you prefer, which have the same key). It's a kind of C++ multimap for geometric search. The solution I came up with is: for each entry who has duplicate keys, save a list (or vector) of segments with corresponding duplicate keys. The problems I see with this approach are twofold: 1. It will reduces the efficiency of the search if there are a large number of duplicate keys. 2. I'll have to use more memory to store the duplicate keys.
My question is: is there another way to implement this more efficiently?
I'd recommend not to use a normal binary search tree! Instead, have a look at interval trees: I suspect this structure suits you needs better.