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 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.

Answer 2

For example, binary trees are used for Heap sorting (Binary Heap). This is way for very fast sorting data so that the biggest (or lowest) item always is at the front. This is used for example in AI (A* algorithm).

Answer 3

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 an order-0.5 tree, 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 nose 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 the same but insertion and deletion were a little more complicated, involving 'rotating' of subtrees through the sub-tree root where necessary.

This was then followed by multi-way trees then, finally, balanced multi-way trees which were basically the same as binary trees but with the added complexity of a sequential search, insert or delete withing 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.

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 subtree 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 4

An advantage of binary trees over 'n-ary' trees is that traversing them often boils down to a simple yes/no decision problem, as in binary space partitioning.

Answer 5

I am not going to be too much techi here.. because the question is why Binary Tree is give so much importance in DataStructure. Binary Tree ,, means tree based on T/F, Yes/No etc. Mean to say the combination of Duo. Practically we face the situation where we need to decide yes or no.. True or False. Binary tree represents such a situation. The softwares we work on,, are the solutions which gonna use the data-structures internally used to solve the real life scenarios.. That's why binary tree coming into picture and is commonly used and even important too. Rest of the trees are further refinements or the added complexities to match them with the typical situations. For starting Binary tree is always important.

Answer 6

Because tree data structures are often used to organize ordered elements, e.g: a > b > c. If your items that are inserted in the trees are ordered, all you need are two branches at each node to divide elements that are larger into the left sub-tree, and elements that are smaller into the right sub-tree.

This is why binary trees are so much more prevalent that m-ary trees. It has nothing to do with the ease of making a yes/no decision versus a m-ary decision!

Answer 7

Adding to the all answers above, a tree of any arity can be represented by a binary tree (where left link goes to the first child of the node, and the right link goes to the next "brother").