# Binary Search Tree without Natural Ordering

This is kind of a multi-part question.

Is it possible to do a binary search tree if the data does not possess natural ordering? Would you be forced to impose artificial ordering to such data? Like images? Or executable files? Or video? or sound files? Items which do not possess an obvious alphabetic or numerical order (my idea of 'natural' total ordering).

Or would it just be better to use a hashmap at that point?

• To the computer, a "natural" "obvious" or "reasonable" ordering is in no way different from an absurd, technocratic, arbitrary ordering. All that counts is that it's computable. Commented Apr 27, 2016 at 15:03
• Aren't binary search trees based on ordering the data (numerically or alphabetically) left to right? Or comparable. I suppose comparability is the key, even if it is arbitrarily assigned.
Commented Apr 27, 2016 at 15:03
• All that matters is that you can provide a function of the form `bool lessThan( T left, T right )` built-in types just have this provided by the system Commented Apr 27, 2016 at 15:06
• I assume that, by natural ordering, you're referring to the phenomenon of a binary tree degrading into a linked list if the insertion data is already sorted. Automatically-balancing binary trees solve this problem by rotating and reorienting subtrees until the height of all branches is the same (give or take 1 level). Commented Apr 27, 2016 at 15:09
• Yes, the structure of the tree is based on the ordering of the keys. Commented Apr 27, 2016 at 15:20

There's orderable data (which may be unordered), but it can be sorted by a variety of sorting algorithms. All of these sorting algorithms depend on the ability to perform a basic comparison ordering test between arbitrary given elements. Such a comparison must return the relative ordering of any two of the elements, for example, usually as -1 for less, 0 for equal, and 1 for greater. There is only one possible answer for the sorted result as a whole (barring duplicates).

There is also related data as you would have in a graph, possibly a directed graph, but not necessarily so. Given a graph we know something about the relative positions of the nodes via their connecting edges. However, there is no total ordering of all the nodes, just that some nodes are know to be before or after other nodes. We can perform a topological sort to order the nodes, but the bottom line is that there are many correct answers, so usually a topo sort will just pick one. A cyclic graph can have cycles, so again the ordering is (even more) arbitrary. Often we'll then look to other properties, for example, to choose the head element of a cycle to determine a good ordering for the domain.

Then there is unrelated data, where all we can do is compare for equality. For those, hashing is a reasonable data structure for storage and retrieval. There is no notion of sorting at all.

We should also consider that the same list of entities can be sorted by different properties or qualities. For example, files can be sorted by their size, which will provide a total ordering. They could be sorted by their timestamps. These may be useless for your domain, but still the point is to think about the various properties available for sorting, categorizing, etc...

• Thanks, this was my general feeling, but I did not know for certain. I am going to wait and give others a chance to answer before marking.
Commented Apr 27, 2016 at 15:23
• do note that on a real system you will always be able to come up with `some` scheme that provides an ordering (e.g. by size or by binary representation), but whether there is one that is helpful to the problem domain gives the three categorizations of this answer Commented Apr 27, 2016 at 15:30
• Yea, which is why I included the artificial ordering bit. Otherwise a search of the tree wouldn't be improved over a hashmap.
Commented Apr 27, 2016 at 15:31

Is it possible to do a binary search tree if the data does not possess natural ordering?

I don't know what the word "natural" means in your context; it seems vague.

Moreover, images, videos, executables and sound files all seem perfectly obviously orderable to me. Order them by byte ordinal comparison, in the event of a tie, the shorter file is smaller. Why do you think this is not a natural way to put something in order? That's how you put strings in order, so why not sound files? A sound file is just a string of bytes, so order it as a string of bytes.

Is it possible to do a binary search tree if the data does not possess a total ordering?

No. Binary search trees require a total ordering.

What is a total order?

A total order simply means that you must provide a comparison operator that it can determine equality, greater than or less than on every pair of elements. And moreover, all the rules that you think of as obviously true for ordering must be met, such as:

• A always equals A (reflexivity)
• If A = B then B = A (symmetry of equality)
• If A = B and B = C then A = C (transitivity)
• If A < B and B < C then A < C (transitivity)
• If A < B then B > A (antisymmetry of inequality)
• ...

and so on. If you cannot meet these rules then you cannot do a binary search and consistently get correct results. If you can meet these rules, then you can.

Or would it just be better to use a hashmap at that point?

Better by what criterion? You haven't said what operations you intend to perform on this data structure other than searching. Hash maps are very good at some tasks that binary trees are bad at, and vice versa.

• In practice, I think the typical binary tree would be ordered by a simple key of some sort, and not the binary content of an image, executable or sound file. Those items would be considered "payloads" for the tree nodes, retrievable using the simple key. Commented Apr 27, 2016 at 16:40
• @RobertHarvey: Sure, that works too. My point was that there is no reason to suppose that an ordinal comparison of bytes is "natural" for strings containing bytes interpreted as text but "unnatural" for strings containing bytes interpreted as sound. Consider by contrast, say, a set of objects representing types in a type system. They are not strings of text, they are not strings of bytes, heck, they need not even have names or be printable, and there is no natural, obvious way to impose an ordering on them. I can think of lots of things that are unnatural to order; bytes aren't among them. Commented Apr 27, 2016 at 16:54
• To sum up: Any value your program can encounter is just a string of bits, and all strings of bits have at least one total ordering, called dictionary order. So even if your data doesn't have a natural ordering, its representation in bits does. Commented Apr 28, 2016 at 3:44
• @KevinJ.Chase: That's not quite what I'm saying. I'm saying that files on disk are very clearly strings of bytes. Many programming languages do not make it easy to extract a string of bytes from an arbitrary data type. Commented Apr 28, 2016 at 3:46
• So, in order for binary search trees to work well (lowest search time), they need to be totally, transitively, and antisymmetrically ordered? Because as I understand it, the median value has to be the root in order to minimize search times.