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.
Let me answer a question I know how to answer instead:
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.