Why use binary search trees when hash tables exist?

Hash tables perform lookup, insertion, and deletion in O(1) time (expected and amortized) while the different variants of binary search tree (BST) - treap, splay, AVL, red-black - offer at best O(log n).

So, in a course on data structures, is the study of BST's of any value except as a historical note?

• Possible duplicate of Hash table versus binary search lookup for unchanging data Commented Mar 16, 2018 at 17:44
• @Discretelizard Maybe so, but that question is so incredibly long that I doubt anyone would be prepared to read it just to find out whether they should use a BST or hash table. Sure, the answers are fairly short but you kinda need to read the question, too, to make sure those answers aren't dealing with some special case that doesn't apply to you. Also, that question is such a marathon to read that it probably won't get very high-quality answers, just because most people will be put off answering it at all. Commented Mar 16, 2018 at 19:15
• @DavidRicherby Sounds like that question should be improved, then! I'll have a look at it. It seems to be a case of 'partial answer in question, please check my partial answer'. Commented Mar 16, 2018 at 19:45
• Closely related question; duplicate? Commented Apr 8, 2018 at 10:12
• Personal note: People who say things like "hashtables are better than binary search trees, you should always use them" don't know what they are talking about. It's always about trade-offs in algorithmics. Commented Apr 8, 2018 at 10:15

The most obvious answer is that trees can be traversed in their natural order very efficiently. If you need to visit every element of a dictionary in alphabetical order, a tree can support this directly, where a hash table cannot.

Another answer is that trees can be made immutable - where insertion and deletion only involve recreating a small number of elements back to the root, whereas hash tables can only be completely duplicated.

A related answer for mutable data is that trees can be modified concurrently, only requiring locking single nodes, whereas hash tables have to be locked as a whole if concurrent processes are to get consistent results.

• Nice list - I would add that space usage can be smaller for trees at least in some scenarios.
– usul
Commented Apr 8, 2018 at 3:00
• Along the same lines, hash tables have fixed capacity. Commented Apr 8, 2018 at 10:13

Binary search trees (BSTs) of various sorts and their variations are widely used data structures today, so they are hardly a "historical note". For example, both the .NET Framework and the Java Standard Library provide a tree-based implementation of a dictionary. A red-black tree no less in the latter case.

One of the reasons for this is that tree-based implementations more easily provide desirable functionality. It's not a surprise that the .NET Dictionary type is a hash table, but the SortedDictionary type is a tree. Providing values in order or doing range queries is something that is awkward with hash tables. Making hash tables persistent (as in allowing old "versions" to be used, not as in on-disk) is also fairly awkward, but it is much more straightforward for trees. Most functional mapping data structures are based on trees, though usually quite a bit fancier than red-black trees and possibly also incorporating hashing as in hash array mapped tries (HAMTs).

Even if you don't need those extra features, sometimes "expected" isn't enough. Those "expectations" are based on assumptions that an adversary can exploit. It's not necessary to use trees to avoid the mentioned issue, but sometimes more predictable behavior than "expected" and "amortized" is necessary.

Finally, many data structures incorporate BSTs or at least ideas from BSTs. For example, most databases use variations on B-trees which are basically "non-binary" search trees. As a pedagogical aspect, proving things about red-black trees, say, is likely an easier exercise than proving things about PATRICIA trees or HAMTs but still exercises many of the concepts that are being taught.

• "Those "expectations" are based on assumptions that an adversary can exploit." -- It's worse: those assumptions never hold in practice! Writing good hash functions is notoriously difficult, data is never uniform, etc. Balanced BSTs are more reliable in this regard. Commented Apr 8, 2018 at 10:14

You are right now thinking of a data structure from which just three operations are expected,

1. Insertion
2. Lookup
3. Deletion

But if you extend these range of operations, to let's say finding number of elements greater than a certain value, one can see how BST's can be useful. A BST can still manage this operation in $\log n$ time but a hash table can't.

Hence in a course of data structure, a BST is very important because it can be extended to support other operations while retaining good complexity while a hash table can't.

The two disadvantages of hash tables: 1. They don't support ordering. Search trees naturally support processing all items in sorted order, or processing all items in some range. 2. The speed will depend on the speed of the hashing function, which may be rather slow.

One brutal approach that I have seen recently is a datastructure that just uses an unsorted array up to a certain size, and then switches to hashing. Very nice when you have applications that often have dictionaries with one or two keys only.