<p>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:</p>

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

<p><a href="http://en.wikipedia.org/wiki/Standard_Template_Library#Containers" rel="nofollow">Documentation</a> on the <a href="http://www.cplusplus.com/reference/stl/set/" rel="nofollow">C++ STL set</a> 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.</p>

CC BY-SA 3.0
2011-12-04T23:24:26.857Z
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 ?
Suresh Venkat
CC BY-SA 3.0
2011-12-05T02:22:41.277Z
related?: http://cstheory.stackexchange.com/questions/8923/binary-search-generalizations-for-posets/8943#8943
Sasho Nikolov
CC BY-SA 3.0
2012-03-05T16:21:07.427Z
There are specialised data-structures for different order types... albeit BSTs don't fit into this category.
A T
<ds.data-structures><partial-order><order-theory>
What effect would using different types of orders have on a binary search tree?
DLaw
# What effect would using different types of orders have on a binary search tree?

(Asked by: username_0 on 2011-12-04)

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](http://en.wikipedia.org/wiki/Standard_Template_Library#Containers) on the [C++ STL set](http://www.cplusplus.com/reference/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.

**Tags:** ds.data-structures, partial-order, order-theory

> **Comments:**
> **username_1**: 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 ?  
> **username_2**: related?: http://cstheory.stackexchange.com/questions/8923/binary-search-generalizations-for-posets/8943#8943  
> **username_3**: There are specialised data-structures for different order types... albeit BSTs don't fit into this category.  

---

## 0 answers

