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; 
};

enter image description here

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?

• Useless: How have you got as far as having a picture of a tree without knowing what your ordering relation is? Before you worry about deletion, you should at least know how the binary search will work, and that should also answer your question.
• Christian Gabor: It is ordered by the scores of the node. Inserting just has to do with comparing the scores at each node, but deletion by score might remove the wrong node with the same score.
• Mike Robinson: And may I kindly comment – "Actum Ne Agas: Do Not Do A Thing Already Done" – except perhaps at University. If this is not merely a homework exercise, there is no particular reason why you should be troubling yourself with this. It's called "a 'container class' ... just pick one." (Pure-C source code is readily available, too.) Therefore, while such matters might arguably be "academically interesting," today, they are certainly nothing more than that – a pragmatic curiosity, already well-solved by others.
• user1118321: I don't understand what you're having trouble with. Can you clarify. If you know you want to delete the node with id = 2 and score = 7, search the tree until you find one with score = 7. If it's id is 2 delete it, otherwise keep looking. What is the part you are having trouble with?

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.