Recently, I was coding a comparator function for use in a set backed by a binary search tree, and the set kept saying that it didn't contain elements that I had previously added to it. I eventually realized that the ordering I had implemented in the comparator was to blame, which got me thinking:

How would a binary search tree change if its elements were ordered by different orders (partial, total, strict, etc...)?

Documentation on the C++ STL set says that the ordering must be strict and weak otherwise behavior is 'undefined', but I'd be interested to hear if anyone could give a more in-depth analysis.

  • 4
    $\begingroup$ I'm not sure what kind of answer you're looking for, but what happens if you insert an element from a partial order that isn't comparable to the root. What do you do then ? $\endgroup$ – Suresh Venkat Dec 4 '11 at 23:24
  • 1
    $\begingroup$ related?: cstheory.stackexchange.com/questions/8923/… $\endgroup$ – Sasho Nikolov Dec 5 '11 at 2:22
  • $\begingroup$ There are specialised data-structures for different order types... albeit BSTs don't fit into this category. $\endgroup$ – A T Mar 5 '12 at 16:21

Your Answer

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

Browse other questions tagged or ask your own question.