1) GENERAL TREES
A general tree (sometimes called a tree) is defined as a non-empty finite set T of elements, called nodes, such that:
- The tree contains the root element
- The remaining elements of the tree form an ordered collection of zero or more disjoint trees T1, T2, ...., Tm
2) BINARY SEARCH TREE
When we place constraints on how data elements can be stored in the tree, the items must be stored in such a way that the key values in left subtree of the root are less than the key value of the root, and the key values of all the nodes in the right subtree of the root are greater than the key value of the root. When this relationship holds in all the nodes in the tree than the tree is called binary search tree.
3) EXTENDED BINARY TREE OR 2-TREES
A binary tree can be convertd to an extended binary tree by adding new nodes to its leaf nodes, and to the nodes that have only one child. These new nodes are added in such a way that all the nodes in the resultant tree have either zero or two children. The extended tree is also known as a 2-tree. The nodes of the original tree are called internal nodes and the new nodes that are added to binary tree, to make it extended binary tree, are called external nodes.
Few points to be remembered about extended binary trees are :
- If a tree has n nodes then number of branches it has n-1
- Every node in a tree has exactly one parent except the root node
- A single path connects any two nodes of a tree
- For a binary tree of height h the maximum number of nodes can be 2h+1 - 1
- Any binary tree with n internal nodes has (n+1) external nodes.
4) THREADED BINARY TREE
When a binary tree is represented using pointers the empty subtrees are set to NULL, i.e, 'left' pointer of a node whose left child is an empty subtree is normally set to NULL. Similarly, the right 'right' pointer of a node whose right child is empty subtree is also set to NULL. Thus, a large number of pointers are set to NULL. These null pointers can be used in different ways. Assume that the 'left' pointer of a node 'n' is set to NULL as the left child of 'n' is an empty subtree, then the 'left' pointer of 'n' can be set to point to the inorder predecessor of 'n'. Similarly, if the 'right' child of node 'm' is empty the 'right' pointer of 'm' can be set to point to the inorder successor of 'm'.
5) AVL TREES
If the heights of both left and right subtrees are given then searching in binary tree is efficient. When we frequently make insertions and deletions in a binary search tree, it is likely to get unbalanced. The efficiency of searching is ideal if the difference between the heights of left and right subtrees of all the nodes in a binary search tree is the most one. Such a binary tree is called an AVL tree or Height Balanced Tree.
6) 2-3 TREES
The insertion and deletion in an AVL tree involves many rotations to make it a balanced tree. This makes the entire operation complicated. To eliminate this complication, a data structure called 2-3 tree can be used.
A node of a binary search tree or an AVL tree can hold only one value; on the other hand 2-3 tree can have at most two values per node. To improve the efficiency of operations performed on a tree we need to reduce the height of the tree. Therefore, B tree is a balanced search tree data structure designed for use with large data sets in secondary storage.
Heap is a complete binary tree. There are two types of heaps. If the value present at any node is greater than all its children, then the tree is called the max-heap or descending heap. In the case of of min-heap or ascending heap the value present at any node is smaller than all its children.
Forest is a set of several trees that are not linked to each other. Forest can be represented as a binary tree.
10) RED BLACK TREES
In a red-black tree data structures, we adopt a colouring convention for the vertices in a binary search tree. Specifically, each vertex in a red-black tree is coloured with either red or black.
A red-black tree is an augmented binary search tree in which the arrangement of vertices obeys the following constraints.
- (Black rule) : Every leaf is coloured black.
- (Red rule) : If a vertex is red, then both of its children are black.
- (Path rule) : Every path from the root to a leaf contains the same number of black vertices.