What are the applications of binary trees?

Question

I am wondering what the particular applications of binary trees are. Could you give some real examples?

Thanks.

Answer 1

Three are a lot of applications. Following PDF file describes several allocations.

http://esminfo.prenhall.com/computing/fordtopp/closerlook/pdf/FordToppCh17.pdf

Answer 2

In C++ STL, and many other standard libraries in other languages, like Java and C#. Binary search trees are used to implement set and map.

Answer 3

The main application is binary search trees. These are a data structure in which searching, insertion, and removal are all very fast (about log(n) operations)

Answer 4

They can be used as a quick way to sort data. Insert data into a binary search tree at O(log(n)). Then traverse the tree in order to sort them.

Answer 5

A binary tree, in its raw form, is actually useful for little more than educating students about data structures :-) ^*a

That's because, unless the data is coming in in a relatively random order, the tree can easily degenerate into its worst-case form, which is a linked list, since simple binary trees are not balanced.

A good case in point: I once had to fix some software which loaded its data into a binary tree for manipulation and searching. It wrote the data out in sorted form:

Alice
Bob
Chloe
David
Edwina
Frank

so that, when reading it back in, ended up with the following tree:

  Alice
 /     \
=       Bob
       /   \
      =     Chloe
           /     \
          =       David
                 /     \
                =       Edwina
                       /      \
                      =        Frank
                              /     \
                             =       =

which is the degenerate form. If you go looking for Frank in that tree, you'll have to search all six nodes before you find him.

Binary trees become truly useful when you balance them. This involves rotating sub-trees through their root node so that the height difference between any two sub-trees is less than or equal to 1. Adding those names above one at a time into a balanced tree would give you the following sequence:

1.   Alice
    /     \
   =       =

 

2.   Alice
    /     \
   =       Bob
          /   \
         =     =

 

3.        Bob
        _/   \_
   Alice       Chloe
  /     \     /     \
 =       =   =       =

 

4.        Bob
        _/   \_
   Alice       Chloe
  /     \     /     \
 =       =   =       David
                    /     \
                   =       =

 

5.           Bob
        ____/   \____
   Alice             David
  /     \           /     \
 =       =     Chloe       Edwina
              /     \     /      \
             =       =   =        =

 

6.              Chloe
            ___/     \___
         Bob             Edwina
        /   \           /      \
   Alice     =      David        Frank
  /     \          /     \      /     \
 =       =        =       =    =       =

You can actually see whole sub-trees rotating to the left as the entries are added and this gives you a balanced binary tree in which the worst case lookup is O(log N) rather than O(N) as the degenerate form gives. At no point does the highest NULL (=) differ from the lowest by more than one level. And, in the final tree above, you can find Frank by only looking at three nodes (Chloe, Edwina and, finally, Frank).

Of course, they become even more useful when you make them balanced multi-way trees rather than binary tress. That means that each node holds more than one item (technically, they hold N items and N+1 pointers, a binary tree being a special case of a 1-way multi-way tree with 1 item and 2 pointers).

With a three-way tree, you end up with:

  Alice Bob Chloe
 /     |   |     \
=      =   =      David Edwina Frank
                 /     |      |     \
                =      =      =      =

This is typically used in maintaining keys for an index of items. I've written database software optimised for the hardware where a node is exactly the size of a disk block (say, 512 bytes) and you put as many keys as you can into a single node. The pointers in this case were actually record numbers into a fixed-length-record direct-access file separate from the index file (so record number X could be found by just seeking to X * record_length).

For example, if the pointers are 4 bytes and the key size is 10, the number of keys in a 512-byte node is 36. That's 36 keys (360 bytes) and 37 pointers (148 bytes) for a total of 508 bytes with 4 bytes wasted per node.

The use of multi-way keys introduces the complexity of a two-phase search (multi-way search to find the correct node combined with a small sequential search to find the correct key in the node) but the advantage in doing less disk I/O more than makes up for this.

I see no reason to do this for an in-memory structure, you'd be better off sticking with a balanced binary tree and keeping your code simple.

Also keep in mind that the advantages of O(log N) over O(N) don't really appear when your data sets are small. If you're using a multi-way tree to store the fifteen people in your address book, it's probably overkill. The advantages come when you're storing something like every order from your hundred thousand customers over the last ten years.

The whole point of big-O notation is to indicate what happens as the N approaches infinity. Some people may disagree but it's even okay to use bubble sort if you're sure the data sets will stay below a certain size, as long as nothing else is readily available :-)

---

^*a Actually, that's not quite true since, as other answers have pointed out, there are uses for non-balanced trees as well. But it is funny and, since the vast majority of binary trees are either balanced or small (where balancing doesn't matter so much), I'll stand by my comment (let the voters decide).

Answer 6

your programs syntax, or for that matter many other things such as natural languages can be parsed using binary tree (though not necessarily).

Answer 7

Implementations of java.util.Set

Answer 8

• Binary trees are used in Huffman coding, which are used as a compression code.
• Binary trees are used in Binary search trees, which are useful for maintaining records of data without much extra space.

Answer 9

I dont think there is any use for "pure" binary trees. (except for educational purposes) Balanced binary trees, such as Red-Black trees or AVL trees are much more useful, because they guarantee O(logn) operations. Normal binary trees may end up being a list (or almost list) and are not really useful in applications using much data.

Balanced trees are often used for implementing maps or sets. They can also be used for sorting in O(nlogn), even tho there exist better ways to do it.

Also for searching/inserting/deleting Hash tables can be used, which usually have better performance than binary search trees (balanced or not).

An application where (balanced) binary search trees would be useful would be if searching/inserting/deleting and sorting would be needed. Sort could be in-place (almost, ignoring the stack space needed for the recursion), given a ready build balanced tree. It still would be O(nlogn) but with a smaller constant factor and no extra space needed (except for the new array, assuming the data has to be put into an array). Hash tables on the other hand can not be sorted (at least not directly).

Maybe they are also useful in some sophisticated algorithms for doing something, but tbh nothing comes to my mind. If i find more i will edit my post.

Other trees like f.e. B+trees are widely used in databases

Answer 10

One of the most common application is to efficiently store data in sorted form in order to access and search stored elements quickly. For instance, std::map or std::set in C++ Standard Library.

Binary tree as data structure is useful for various implementations of expression parsers and expression solvers.

It may be also to solve some of database problems, for example, indexing.

Generally, binary tree is a general concept of particular tree-based data structure and various specific types of binary trees can be constructed with different properties.

Answer 11

One interesting example of a binary tree that hasn't been mentioned is that of a recursively evaluated mathematical expression. It's basically useless from a practical standpoint, but it is an interesting way to think of such expressions.

Basically each node of the tree has a value that is either inherent to itself or is evaluated by recursively by operating on the values of its children.

For example, the expression (1+3)*2 can be expressed as:

    *
   / \
  +   2
 / \
1   3

To evaluate the expression, we ask for the value of the parent. This node in turn gets its values from its children, a plus operator and a node that simply contains '2'. The plus operator in turn gets its values from children with values '1' and '3' and adds them, returning 4 to the multiplication node which returns 8.

This use of a binary tree is akin to reverse polish notation in a sense, in that the order in which operations are performed is identical. Also one thing to note is that it doesn't necessarily have to be a binary tree, it's just that most commonly used operators are binary. At its most basic level, the binary tree here is in fact just a very simple purely functional programming language.

Answer 12

Even though the bounty is gone, since the accepted answer gives the extremely-false impression that binary-trees are not very useful, I will post another answer.

To squabble about the performance of binary-trees is meaningless - they are not a data structure, but a family of data structures, all with different performance characteristics. While it is true that unbalanced binary trees perform much worse than self-balancing binary trees for searching, there are many binary trees (such as binary tries) for which "balancing" has no meaning.

The reason that binary trees are used more often than n-ary trees for searching is that with every comparison in a (balanced) binary tree, you eliminate about half the tree from consideration. In contrast, with an n-ary tree, you can eliminate (n-1)/n of the tree using log(n) comparisons (using a binary search).

Applications of binary trees

• Binary Search Tree - Used in many search applications where data is constantly entering/leaving, such as the map and set objects in many languages' libraries.
• Binary Space Partition - Used in almost every 3D video game to determine what objects need to be rendered.
• Binary Tries - Used in almost every high-bandwidth router for storing router-tables.
• Hash Trees - used in p2p programs and specialized image-signatures in which a hash needs to be verified, but the whole file is not available.
• Heaps - Used in heap-sort; fast implementations of Dijkstra's algorithm; and in implementing efficient priority-queues, which are used in scheduling processes in many operating systems, Quality-of-Service in routers, and A* (path-finding algorithm used in AI applications, including video games).
• Huffman Coding Tree (Chip Uni) - used in compression algorithms, such as those used by the .jpeg and .mp3 file-formats.
• GGM Trees - Used in cryptographic applications to generate a tree of pseudo-random numbers.
• Syntax Tree - Constructed by compilers and (implicitly) calculators to parse expressions.
• Treap - Randomized data structure used in wireless networking and memory allocation.
• T-tree - Though most databases use some form of B-tree to store data on the drive, databases which keep all (most) their data in memory often use T-trees to do so.

And these are just the ones I can think of off the top of my head. If anyone knows any more, list them in the comments and I'll update the post.