Binary Search Tree with ID and Duplicate Values

Question

I'm having trouble finding resources for this implementation I'm trying to figure out. I want to save nodes in a binary search tree (self balancing) containing an ID and value

struct Score
{  
  int id;
  int score;    
};

If I want to delete (id=2, score=7), how can I delete this node without deleting id=6 or id=5? If I search for the deletion node by score value, then I collide with the other nodes.

I was thinking of keeping a separate data structure to keep track of the locations. Should I keep a hash table that saves the pointers to the parent nodes of each id?

Answer 1

A binary search tree cannot have duplicate keys. Yet your score is not unique. Possible solutions:

• do not order by score, but by a (score, id) tuple. I.e., the ID can be used to break ties.
• each node represents a set of elements rather than a single element.

In your particular case, the key duplication is not fatal if you are writing your own tree implementation: instead of blindly deleting by key (score) you can easily add the check that the ID also matches. However, you will have to remember that child nodes may have equal keys and must also be searched. This gives up the benefits of using a BST, and I stronly encourage you to use an alternative solution (such as ordering by score–id tuple) instead.