A tree is recursively defined as a set of one or more nodes where one node is designated as the root of the tree and all the remaining nodes can be partitioned into non-empty sets each of which is a sub-tree of the root.
There are many types of trees in non linear data structure.
Comparison of various trees in non-linear data structure.
- A binary tree is a data structure that is defined as a collection of elements called nodes.
- In a binary tree, the topmost element is called the root node, and each node has 0,1, or at the most 2 children.
A node that has zero children is called a leaf node or a terminal node. Every node contains a data element, a left pointer which points to the left child, and a right pointer which points to the right child. The root element is pointed by a ‘root’ pointer.
If root = NULL, then it means the tree is empty.
Binary Search Tree
A binary search tree, also known as an ordered binary tree, is a variant of binary trees in which the nodes are arranged in an order.
- A tree is called binary search tree if it satisfy following two conditions:
- All nodes must have at most two children. (Binary tree)
- In a binary search tree, all the nodes in the left sub-tree have a value less than that of the root node. Correspondingly, all the nodes in the right sub-tree have a value either equal to or greater than the root node.
Since the nodes in a binary search tree are ordered, the time needed to search an element in the tree is greatly reduced.
- AVL tree is a self-balancing binary search tree invented by G.M.Adelson-Velsky and E.M.Landisin 1962. The tree is named AVL in honour of its inventors.
- In an AVL tree, the heights of the two sub-trees of a node may differ by at most one. Due to this property, the AVL tree is also known as a height-balanced tree.
- A B tree is designed to store sorted data and allows search, insertion, and deletion operations to be performed in logarithmic amortized time. A B-tree of order m (the maximum number of children that each node can have) is a tree with all the properties of an M-way search tree. In addition it has the following properties:
- Every node in the B tree has at most (maximum) m children.
- Every node in the B tree except the root node and leaf nodes has at least (minimum) m/2 children. This condition helps to keep the tree bushy so that the path from the root node to the leaf is very short, even in a tree that stores a lot of data.
- The root node has at least two children if it is not a terminal (leaf) node.
- All leaf nodes are at the same level.
Example: B tree of order 4
An internal node in the B tree can have n number of children, where 0 <= n <= m. It is not necessary that every node has the same number of children, but the only restriction is that the node should have at least m/2 children. As B tree of order 4 is given in above Fig.
- In a 2-3 tree, each interior node has either two or three children.
- Nodes with two children are called 2-nodes. The 2-nodes have one data value and two children
- Nodes with three children are called 3-nodes. The 3-nodes have two data values and three children (left child, middle child, and a right child)
- This means that a 2-3 tree is not a binary tree. In this tree, all the leaf nodes are at the same level (bottom level).