I have taken two approaches. First is exactly what you suggest, that the "greater" pointer is greater than or equal to. When I'm traversing the tree, I want to find every value. Typically the node contains the index value and a pointer to the rest of the data associated with it, which is what's really of interest. What may or may not be important is whether you get them in the order in which they were added (stability). If you rebalance the tree, you probably won't.

The second option is to add a value to your keys to make them unique, but then you have to write lots of extra code to handle that. I don't recommend it, and I've never done it that way.

I hope this helps.