How do I determine which kind of tree data structure to choose?

Question

Ok, so this is something that's always bothered me. The tree data structures I know of are:

• Unbalanced binary trees
• AVL trees
• Red-black trees
• 2-3 trees
• B-trees
• B*-trees
• Tries
• Heaps

How do I determine what kind of tree is the best tool for the job? Obviously heaps are canonically used to form priority queues. But the rest of them just seem to be different ways of doing the same thing. Is there any way to choose the best one for the job?

Answer 1

Let’s pick them off one by one, shall we?

• Unbalanced binary trees

For search tasks, never. Basically, their performance characteristics will be completely unpredictable and the overhead of balancing a tree won’t be so big as to make unbalanced trees a viable alternative.

Apart from that, unbalanced binary trees of course have other uses, but not as search trees.

• AVL trees

They are easy to develop but their performance is generally surpassed by other balancing strategies because balancing them is comparatively time-intensive. Wikipedia claims that they perform better in lookup-intensive scenarios because their height is slightly less in the worst case.

• Red-black trees

These are used inside most of C++’ std::map implemenations and probably in a few other standard libraries as well. However, there’s good evidence that they are actually worse than B(+) trees in every scenario due to caching behaviour of modern CPUs. Historically, when caching wasn’t as important (or as good), they surpassed B trees when used in main memory.

• 2-3 trees
• B-trees
• B*-trees

These require the most careful consideration of all the trees, since the different constants used are basically “magical” constans which relate in weird and sometimes unpredictable way to the underlying hardware architecture. For example, the optimal number of child nodes per level can depend on the size of a memory page or cache line.

I know of no good, general rule to distinguish between them.

• Tries

Completely different. Tries are also search trees, but for text retrieval of substrings in a corpus. A trie is an uncompressed prefix tree (i.e. a tree in which the paths from root to leaf nodes correspond to all the prefixes of a given string).

Tries should be compared to, and offset against, suffix trees, suffix arrays and q-gram indices – not so much against other search trees because the data that they search is different: instead of discrete words in a corpus, the latter index structures allow a factor search.

• Heaps

As you’ve already said, they are not search trees at all.