CODEWITHSUNDEEP
c
MLquest
MLquest

Reputation: 19

Binary search tree with two conditions

I have a classic binary search tree, if cond < 0 addleft else addright. But some of my entries are "flagged" and I want them to be prioritized over "non-flagged" so that when I access the tree it first gives "flagged" entries in an ascending order and then the "non-flaged." Currently I have what I call a "tree root" where I check if the entry is "flagged" and send it to the appropriate tree. It works, but I would rather get rid of it and merge the "flagged" and "non-flagged" trees if possible. How would I go about it?

Upvotes: 0

Views: 63

Answers (1)

Sam Henke
Sam Henke

Reputation: 399

You could regard your tree as a BST with respect to a different comparison operator. Something like the following:

int compare(/* type */ a, /* type */ b) {
  if (a->is_flagged && !b->is_flagged) return -1;
  else if (!a->is_flagged && b->is_flagged) return 1;
  else return a->value < b->value;
}

This essentially does a lexicographical ordering. It regards all flagged elements as less than every non-flagged element, and only considers the value if the flagged status is the same for both items.

Upvotes: 2

Related Questions