12

I understand the structure of binary trees and how to traverse them. However, I am struggling to realize their actual uses, purposes in programs and programming. When I think about 'real life' examples of hierarchical data they almost certainly have more than 2 children. For example, in a family tree, a mother may often have more than two children.

Are 'binary trees' really only useful to store linearly related data due to the faster processing times over arrays and lists? Alternatively, do they serve a specific purpose in storing hierarchical data? If so, what examples are there of the application of binary trees. What data is such that a node has at most 2 children?

migrated from stackoverflow.com Jun 29 '15 at 18:45

This question came from our site for professional and enthusiast programmers.

25

No, binary trees are not for storing hierarchical data in the sense you're thinking of. The primary use case for n-ary trees, where n is a fixed number, is fast search capability, not a semantic hierarchy.

Remember the old game where one person thinks of a number between 1 and 100, and the other has to guess it in as few guesses as possible, and if you guess wrong the person thinking of the number has to tell you if you're too high or too low? It gets boring after a while because you quickly figure out that you should always start at 50, then go to 25 or 75, and keep dividing the range to be searched in half with each new guess after that, and eventually you can guess any number in at most 7 guesses, guaranteed.

It may not make for a fun game, but that property is what makes binary (and other n-ary) trees useful: you can use them to search a very large data set in a very small amount of time.

  • Excellent answer thank you so much. So, binary tree's are really just another structure for storing data like you would in an array or a list, but with the added benefit of fast search capabilities? – sw123456 Jun 29 '15 at 18:54
  • 1
    @sw123456: That's right. As with any engineering, it comes with tradeoffs, (uses more--and more fragmented--memory than an array with the same number of elements, O(n) access to element #n of the data set rather than O(1) access, etc,) but fast search is definitely the major benefit of binary trees. – Mason Wheeler Jun 29 '15 at 19:01
  • @sw123456 Glad I could help explain it :) – Mason Wheeler Jun 29 '15 at 19:06
  • 3
    Access to elements are O(log(n)) when the tree is balanced. O(n) will be the worst case when it is degenerated (most nodes with just one bracket). – Mandrill Jun 30 '15 at 0:40
  • @sw123456 Network routing uses a slight modification of a binary tree called a Trie (created for more efficiency for the problem domain). It does actually store hierarchy information as routers travers the tree bit-by-bit when looking up an IP address to find where it should forward the packet to. IP addresses are also by nature hierarchical, so in traversing an IP to find the longest prefix match, the router is traversing the IP hierarchy, subnet IPs, etc. It's not obvious semantically, but the relationship is there. Routers use this structure for lookup efficiency, as Mason answered. – Chris Cirefice Jun 30 '15 at 13:24
3

Any tree structure, where a node can have unlimited numbers of children, can be implemented using a binary tree.

For each node in your tree, replace it with a node with a right and left pointer. The left pointer goes to the first of the node's children. The right node goes to the next sibling of the node. All the children of a given node are in a linked list joined by their right pointers, with the head of the list pointed to by the left pointer of their parent.

Your complicated, n-ary tree has become a simple, binary tree.

I am sure this is in Knuth, Vol. 1 somewhere.

  • This is a really interesting implementation. Am i right in thinking that because each child node was the start of a linked list, the tree would no longer be O(log)n) if balanced or O(n) if not, due to the fact that visiting each node would start off a linear search? This implementation would result in much slower search times? But on the upside, the search times would be quicker than that of a standard linear structure? Have I understood this correctly? – sw123456 Jul 3 '15 at 12:39
  • @sw123456, If the original tree was balanced, the resulting binary tree almost certainly would not be. I believe everything else would depend on the fan out of the tree, how many children does any given node have. A linear search would only occur when finding out which of a given node's children to follow. But I am not sure you could avoid that in any other implementation of an n-ary tree. – Justsalt Jul 8 '15 at 13:07
2

Binary trees why use them?

In programming you work a lot with collections of same type data.

The two basic ways of storing this data are : linked lists and arrays.

They both come with up and downsides: In a linked list it's easy to add elements at any position or remove elements. But access to a specific element is harder, because you have to go through the list until you're at the element you want.

  • It doesn't search efficiently but inserting and deleting is easy.

With an array access to a specific element is easy, but it's harder to insert or delete an element because inserting means: extend array by one, shift all elements before the insert position 1 to the right and insert the element.

  • It searches efficiently (if sorted) but inserting and deleting is hard.

So both the linked list and the array have downsides.

Binary trees are made to tackle both problems of the array and the linked list:

  1. Easy insert and delete
  2. Easy searching

So binary tree are made for when you have lots of data which changes regularly.

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.