what is a binary tree?
A binary tree is a tree structure in which each element or node will have two children and not more than two. They are popularly called as left and right elements. A binary tree will have three things,
- pointer to left child
- pointer to right child
Presenting it step-by-step.
First, you have to define the notion of a Binary Tree. It is basically a collection of Nodes which is the smallest element of the Binary Tree that itself points to two Nodes at max.
The left Node holds a value that is less than that of the Parent Node. The right Node holds a value that is bigger than that of the Parent Node.
Nota bene! Each Node can point to only two Child Nodes, including the root of the Binary Tree that is also a Node. Thus, the term “Binary Tree”.
So, the structure of a Node is: a value, left Child Node, right Child Node.
Updating a Binary Tree
In order to attach a new Node to the Parent Node we look at the value of the former.
- If the value is greater than that of the Parent Node, the new Node becomes the right Child Node of the Parent.
- If the value is less than that of the Parent Node, the new Node becomes the left Child Node of the Parent.
- If the right Child Node and the left Child Node already exist, we attach the new Node to the existing Child Node.
Searching a Binary Tree
Traversing the Binary Tree is simple.
- If the required value is equal to the value of the Root Node, return True.
- If the required value is greater than the value of the Root Node, search the right Child Node of the Root Node.
- If the required value is less than the value of the Root Node, search the left Child Node of the Root Node.
- If still no success, search the Children of the Children recursively.
- If we reach the end of the Binary Tree – in other words, if there are no remaining Nodes to check – raise an Exception, which terminates the recursion.
Applications of binary tree
- Binary Search Tree – Used in many search applications where data is constantly entering/leaving, such as the
setobjects 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.