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.

Binary Tree

  • 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:
  1. All nodes must have at most two children. (Binary tree)
  2. 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

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

B 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:
  1. Every node in the B tree has at most (maximum) m children.
  2. 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.
  3. The root node has at least two children if it is not a terminal (leaf) node.
  4. 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.

2–3 Tree

  • In a 2-3 tree, each interior node has either two or three children.
  1. Nodes with two children are called 2-nodes. The 2-nodes have one data value and two children
  2. 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).