Advertisement
Advertisement


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?

2014/07/12
1
328
7/12/2014 8:19:22 PM

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

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 implementing efficient priority-queues, which in turn are used for scheduling processes in many operating systems, Quality-of-Service in routers, and A* (path-finding algorithm used in AI applications, including robotics and video games). Also used in heap-sort.
  • 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.

The reason that binary trees are used more often than n-ary trees for searching is that n-ary trees are more complex, but usually provide no real speed advantage.

In a (balanced) binary tree with m nodes, moving from one level to the next requires one comparison, and there are log_2(m) levels, for a total of log_2(m) comparisons.

In contrast, an n-ary tree will require log_2(n) comparisons (using a binary search) to move to the next level. Since there are log_n(m) total levels, the search will require log_2(n)*log_n(m) = log_2(m) comparisons total. So, though n-ary trees are more complex, they provide no advantage in terms of total comparisons necessary.

(However, n-ary trees are still useful in niche-situations. The examples that come immediately to mind are quad-trees and other space-partitioning trees, where divisioning space using only two nodes per level would make the logic unnecessarily complex; and B-trees used in many databases, where the limiting factor is not how many comparisons are done at each level but how many nodes can be loaded from the hard-drive at once)

433
5/23/2017 11:54:59 AM


The organization of Morse code is a binary tree.

binary-tree

morse-code

2017/08/15

A binary tree is a tree data structure in which each node has at most two child nodes, usually distinguished as "left" and "right". Nodes with children are parent nodes, and child nodes may contain references to their parents. Outside the tree, there is often a reference to the "root" node (the ancestor of all nodes), if it exists. Any node in the data structure can be reached by starting at root node and repeatedly following references to either the left or right child. In a binary tree a degree of every node is maximum two.

Binary Tree

Binary trees are useful, because as you can see in the picture, if you want to find any node in the tree, you only have to look a maximum of 6 times. If you wanted to search for node 24, for example, you would start at the root.

  • The root has a value of 31, which is greater than 24, so you go to the left node.
  • The left node has a value of 15, which is less than 24, so you go to the right node.
  • The right node has a value of 23, which is less than 24, so you go to the right node.
  • The right node has a value of 27, which is greater than 24, so you go to the left node.
  • The left node has a value of 25, which is greater than 24, so you go to the left node.
  • The node has a value of 24, which is the key we are looking for.

This search is illustrated below: Tree search

You can see that you can exclude half of the nodes of the entire tree on the first pass. and half of the left subtree on the second. This makes for very effective searches. If this was done on 4 billion elements, you would only have to search a maximum of 32 times. Therefore, the more elements contained in the tree, the more efficient your search can be.

Deletions can become complex. If the node has 0 or 1 child, then it's simply a matter of moving some pointers to exclude the one to be deleted. However, you can not easily delete a node with 2 children. So we take a short cut. Let's say we wanted to delete node 19.

Delete 1

Since trying to determine where to move the left and right pointers to is not easy, we find one to substitute it with. We go to the left sub-tree, and go as far right as we can go. This gives us the next greatest value of the node we want to delete.

Delete 3

Now we copy all of 18's contents, except for the left and right pointers, and delete the original 18 node.

Delete 4


To create these images, I implemented an AVL tree, a self balancing tree, so that at any point in time, the tree has at most one level of difference between the leaf nodes (nodes with no children). This keeps the tree from becoming skewed and maintains the maximum O(log n) search time, with the cost of a little more time required for insertions and deletions.

Here is a sample showing how my AVL tree has kept itself as compact and balanced as possible.

enter image description here

In a sorted array, lookups would still take O(log(n)), just like a tree, but random insertion and removal would take O(n) instead of the tree's O(log(n)). Some STL containers use these performance characteristics to their advantage so insertion and removal times take a maximum of O(log n), which is very fast. Some of these containers are map, multimap, set, and multiset.

Example code for an AVL tree can be found at http://ideone.com/MheW8

2012/07/27

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)


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.

2010/02/04

  • 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.
2010/02/01

Source: https://stackoverflow.com/questions/2130416
Licensed under: CC-BY-SA with attribution
Not affiliated with: Stack Overflow
Email: [email protected]