Data Structures and Algorithms - Old Questions
5. Write about applications of Binary trees.
A binary tree is a finite set of elements that are either empty or is partitioned into three disjoint subsets.
- The first subset contains a single element called the root of the tree.
- The other two subsets are themselves binary trees called the left and right sub-trees of the original tree.
Each element of a binary tree is called a node of the tree.
The following figure shows a binary tree with 9 nodes where A is the root.
Applications of Binary Trees
1. 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.
2. Binary Space Partition - Used in almost every 3D video game to determine what objects need to be rendered.
3. Binary Tries - Used in almost every high-bandwidth router for storing router-tables.
4. 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.
5. 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.
6. Huffman Coding Tree - 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.
7. Syntax Tree - Constructed by compilers and (implicitly) calculators to parse expressions.
8. Treap - Randomized data structure used in wireless networking and memory allocation.
9. 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.