7
$\begingroup$

I am currently bushing up on my data structures and basic algorithms, part of that is the Binary Tree. I do understand the algorithms, and how to implement a binary search tree and such. I do so how smart it is that we can do lookups in O(log n) time.

I am however having a hard time finding an example of when I would use a binary tree, where a hash tables would not do the same/better job. I have been doing some searching around and found that it is used for 3D graphis, something about what items are to be displayed, i do however have a hard time relating to this.

Can any one give me an example where it would be better to user a binary tree over a hash table?

|cite|improve this question
$\endgroup$
14
$\begingroup$

Hash tables can only tell you if an element is present or not.

Here are somethings you can do with a binary tree that you can't do wiht a hash table.

  • sorted traversal of the tree
  • find the next closest element
  • find all elements less than or greater than a certain value

See this wikipedia article on K-d trees for an example of a real world data structure that makes use of the special properties of binary trees. http://en.wikipedia.org/wiki/K-d_tree

|cite|improve this answer
$\endgroup$
  • 1
    $\begingroup$ Also, have worst-case sub-linear runtime guarantees. $\endgroup$ – Raphael♦ Sep 29 '14 at 7:27
11
$\begingroup$

One application domain where binary trees are better, or more easily adjustable than certain alternatives, are persistent data structures (which are often used in (purely) functional programming).

A persistent data structure is a data structure that preserves the previous version of itself when it is modified. (Data structures that do not have this property are called ephemeral.) One benefit of this kind of data structure is that it allows sharing of parts of the data structure - since the structure itself is guaranteed not to change, it is safe to share it freely between other data structures and even threads without worrying about it changing. Another subjective benefit is that these data structures are easier to reason about.

Conceptually, you could have an immutable data type that is a list of numbers, e.g., $L_1 = \{3,4,5\}$. Then you could introduce a new value that adds two numbers to the front of this list: $L_2 = cons(1,cons(2,L_1)) = \{1,2,3,4,5\}$. What happened to $L_1$? Nothing - $L_1 = \{3,4,5\}$, still. Did $L_2$ copy those three elements and put it into its own list, then? Ideally not - the values in list $L_1$ belongs to $L_2$, also:

$ \overbrace{ 1, 2, \underbrace{3,4,5}_{L_1} }^{L_2} $

There are data structures that are more well-suited for implementing persistent lists like the one above. In the same vein, binary trees are more well-suited for implementing persistent data structures with certain properties, than other data structures or strategies. And the structural sharing shown in the example with the two lists carry over to binary trees - you can imagine that several versions of a tree can share sub-trees that they have in common.

Like I said, some data structures are easier to amend to be persistent. You mention hash table, which is typically (if not even necessarily) an ephemeral data structure. It seems less obvious how one can adjust a common implementation strategy for a hash table to be persistent. Consider that a hash table is often implemented with an array (specifically, arrays that are implemented as a continuous part of memory). Arrays are nice since they provide random access to elements, which is an important property since you ideally want to have $O(1)$ average access to elements in the hash table. But arrays aren't that nice when it comes to building persistent data structures. The gist of it is that, while you can make an immutable array data type, by the nature of arrays, you risk having to do a lot of copying - If the aforementioned List type was implemented with arrays, you would risk having to create a whole new array with five elements, instead of sharing part of it. And what if you want to modify something in the middle of the array? The most obvious - and seemingly unavoidable - answer is, again, copying.

Persistent data structures do not avoid having to do copying, in general. But certain data structures make copying less frequent. This is a desirable property when you demand that a data structure has to be immutable.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ The problems with persistent arrays that you mention in your second-to-last paragraph are probably why Clojure implements its random-access vectors with big, flat trees instead of using Java arrays. They have $\mathcal{O}(\log_{32} (n))$ access time instead of $\mathcal{O}(1)$, but they can share structure easily. $\endgroup$ – tsleyson Sep 28 '14 at 20:02
  • 1
    $\begingroup$ I once used purely functional red-black trees in a Java program to store a large number of similar bitsets, which dramatically reduced memory usage and allowed me to quickly compute their Jaccard similarity coefficient. Such trees can also be efficiently compared for (in)equality by maintaining a hash - e.g. by having each node store the XOR of hashes of its branches; this is trivial to maintain under rotations. $\endgroup$ – jkff Sep 30 '14 at 5:01
4
$\begingroup$

A binary tree has many applications, especially if we include all binary trees and not just binary search trees. Heaps are implemented as binary trees where the top most element is either a min or max value of all elements, which is very useful for a scenario that calls for a priority queue.

Hashmaps are very efficient in a set type of operation where one is simply checking for existence of an element. But they are weaker when it comes to performing non-existence checking operations on ordered or sorted data. Furthermore, while it would be possible with tweaking of the hash algorithms, binary trees seem to better support the notion of partial key searches. For example, one could try to use a binary tree of strings to answer which words begin with "an". Granted a trie would be a better data structure for that type of scenario.

|cite|improve this answer
$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.