A binary tree is a tree data structure in which each node has up to two child nodes that create the branches of the tree. The two children are usually referred to as the left and right nodes. Parent nodes are nodes with children, while child nodes can contain references to their parents. The topmost node of the tree is called the root node, the node to the left of the root is the left node which can serve as the root for the left sub-tree and the node to the right of the root is the right node which can serve as the root for the right sub-tree.
Why binary trees?
- Binary trees can be used to store data in a hierarchical order.
- Insertion and deletion operation is quicker in trees when compared to arrays and linked lists.
- Any number of nodes can be stored using a binary tree and the size is dynamic.
- Accessing elements in trees are faster when compared to linked lists and slower when compared to arrays.
Types of binary trees
Binary trees can be classified as follows
- Complete binary tree: All the levels are completely filled except possibly the last level and the nodes in the last level are as left as possible.
- Full binary tree: All the nodes of a binary tree possesses either 0 or 2 children.
- Perfect binary tree: It is a full binary tree all the nodes contains exactly two children other than the leaf nodes.
Applications of binary trees
The following are the applications of binary trees:
Binary Search Tree - Used in many search applications that constantly show and hide data, such as data. For example, map and set objects in many libraries.
Binary Space Partition - Used in almost any 3D video game to determine which objects need to be rendered.
Binary Tries - Used in almost every high-bandwidth router to store router tables.
Syntax Tree - Constructed by compilers and (implicit) calculators to parse expressions.
Hash Trees - Used in P2P programs and special image signatures that require a hash to be validated, but the entire file is not available.
Heaps - Used to implement efficient priority queues and also used in heap sort.
Treap - Randomized data structure for wireless networks and memory allocation.
T-Tree - Although most databases use a form of B-tree to store data on the drive, databases that store all (most) data often use T-trees.
Huffman Coding Tree (Chip Uni) - Used in compression algorithms, eg. For example, in .jpeg and .mp3.GGM Trees file formats - used in cryptographic applications to generate a tree with pseudo-random numbers.