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?

  • 1
    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.
    – Useless
    Nov 6 '18 at 23:26
  • 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. Nov 7 '18 at 1:01
  • 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. Nov 7 '18 at 1:22
  • 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? Nov 7 '18 at 3:54

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.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.