Why are Binary Trees Important?

Question

Why we do we study binary trees specifically? As in a general m-way search tree is not given as importance as binary trees in DataStructure textbooks.

Does the use of a binary tree exceed m-way trees?

Answer 1

Binary trees are the simplest form of multi-way trees so they're easier to study in that sense.

Multi-way trees have nodes that consist of N keys and N+1 pointers, along the lines of:

               |    +-----+-----+-----+-----+    | k00 | k01 | k02 | k03 |    +-----+-----+-----+-----+   /      |     |     |      \ p00     p01   p02   p03     p04 

To find out which pointer to follow in a search, you compare the key you're looking for against the keys in the node. That example above is an order-2 multi-way tree (I'm defining order n as having 2n keys and 2n+1 pointers).

When you "degenerate" this structure to have the smallest node possible, you end up with one key and two pointers, your classical binary tree:

      |    +-----+    | k00 |    +-----+   /       \ p00       p01 

When I went to university (and I'll freely admit that it was a while ago), we studied binary trees first, simply because the algorithms were elegant. Search was a simple compare node and select one of two sub-trees. Insertion and deletion were also relatively easy.

Then we went on to balanced binary trees, where search was exactly the same but insertion and deletion were a little more complicated, involving 'rotating' of sub-trees through the sub-tree root where necessary to keep it balanced.

This was then followed by non-balanced multi-way trees to get the concept of searching within a node once you've found the correct node then, finally, balanced multi-way trees which were basically the same as binary trees but with that same added complexity of a sequential search, as well as insertion or deletion within the node and combining and spitting of nodes themselves.

At each of those steps you simply added a little more complexity to the algorithms. I don't recall too many people having trouble with that progression so maybe all the textbooks you mention are just at the starter level.

I've never really found multi-way trees to be more useful than binary trees except in one very specific situation. That's when you're reading nodes of the tree from a slow medium like disk and you've optimized for sector/cluster/block sizes.

We developed a multi-way tree implementation under OS/2 (showing my age here) which screamed along, by ensuring the nodes were identical in size to the underlying disk blocks. Even though this could result in some wasted space, the speed improvements were worth it.

For in-memory stuff, binary trees have all the advantages of multi-ways with none of the extra complications (having to combine sequential search of a node with sub-tree selection).

Binary trees boil down to "Should we move left or right?", multi-ways are "Where's the key in this node so that we can choose the sub-tree?".

Answer 2

Binary trees are a simple concept, they are easy to understand, easy to implement, and work well and fast -- I suppose this is enough for teaching and/or using them.