UNIT III NON-LINEAR DATA STRUCTURES - TREE

Tree ADT-tree traversals-Binary Tree ADT-expression Trees-Application of tree-binary search-tree

ADT- threaded Tree-AVL tree-B-Tree- B+ Tree-Heap-Application of heap

TREE : A tree is a finite set of one or more nodes such that there is a specially designated node
called the root, and zero or more non-empty sub trees T1, T2....Tk, each of whose roots are connected
by a directed edge from Root R.

A simple tree.

ROOT : A node which doesn't have a parent. In the above tree root node is A.
NODE : Item of Information. A, B, C, D,E etc
LEAF : A node which doesn't have children is called leaf or Terminal node. Eg E, F, G, H, I, D
SIBLINGS : Children of the same parents are said to be siblings, eg E, F, G, H are siblings.
PATH : A path from node n, to nk is defined as a sequence of nodes n1, n2,n3....nk such that ni is
the parent of ni+1. for i<=i<k. There is exactly only one path from each node to root.
Eg. A-HA-B-H
LENGTH : The length is defined as the number of edges on the path.
Eg. A-C length=1
A-Hlength=2
DEGREE : The number of subtrees of a node is called its degree.
Eg degree of A=3
Degree of B=4
Degree of H=0
The degree of the tree is the maximum degree of any node in the tree. Eg.
Degree of the tree = 4.
LEVEL:
Root node Alevel 1
B, C, D level 2
E, F, G, H, I level 3
DEPTH:For any node n, the depth of n is the length of unique path from root to n. Depth
of F=2
Depth of B=1
Depth of I=2
Depth of A=0
The depth of the root node is always 0.
HEIGHT:
Length of the longest path from n to leaf.
1
Height of C=1
Height of D=0
Height of A=2
The height of the leaf node is always 0.

BINARY TREE

Binary tree is a finite ordered collection of elements in which one element is designated as root and the
remaining elements are partitioned in to two disjoint sets called left and right sub tree.
Binary Tree is a tree in which no node can have more than two children.
Maximum number of nodes at level i of a binary tree is 2i-1.
A binary tree is a tree which is either empty, or one in which every node: has no children; or

• has just a left child; or

• has just a right child; or
• has both a left and a right child.
Types of Binary tree
• Complete binary tree
• Full binary tree
Complete binary tree: The number of nodes in the complete binary tree are in the range 2h to 2h+1-1.

Full binary tree: The number of nodes in the full binary tree is 2h+1-1, where h is the height of the
tree. All full binary trees are complete binary tree. But the vise versa is not true.

Tree node declaration: struct

TreeNode
{
Element type Element;
Struct TreeNode *Left ;
Struct TreeNode *Right;
};
2
REPRESENTATION OF A BINARY TREE
There are two ways for representing binary tree, they are
* Linear Representation
* Linked Representation

Linear Representation
The elements are represented using arrays. For any element in position i, the left child is in position
2*i+1, the right child is in position 2*(i + 1), and the parent is in position (i/2). I is the position of
the parent.

A B C D E F G - - -
0 1 2 3 4 5 6 7 8 9
Disadvantage of linear representation
Wastage of memory space.

Linked Representation
The elements are represented using pointers. Each node in linked representation has three fields, namely,
* Pointer to the left subtree
* Data field
* Pointer to the right subtree
In leaf nodes, both the pointer fields are assigned as NULL.

3
 TREE TRAVERSAL
It is a procedure by which each node in the tree is processed exactly once in a systematic manner.
Types of traversal.
There are three different traversal of binary tree.

In order traversal
Process the left sub tree
Process the root
Process the right sub tree
Ex: DBEAC

Post order traversal

Process the left sub tree
Process the right sub tree
Process the root
Ex: DEBCA

Pre order traversal

Process the root
Process the left sub tree
Process the right sub tree
Ex: ABDEC

Example 1: Find the In-order, Pre-order and post-order traversal of given tree

Pre-order Traversal : + – a b * c d
In-order Traversal : a-b+c*d
Post-order Traversal : ab-cd*+

Example 2: Find the In-order, Pre-order and post-order traversal of given tree
4
Pre-order Traversal : A, B, D, G, H, L, E, C, F, I, J, K
In-order Traversal : G, D, H, L, B, E, A, C, I, F, K, J
Post-order Traversal : G, L, H, D, E, B, I, K, J, F, C, A

Example 3: Find the In-order, Pre-order and post-order traversal of given tree

Pre-order Traversal : A, B, D, C, D, E, F, G, H, I
In-order Traversal : B, D, A, E, H, G, I, F, C
Post-order Traversal : D, B, H, I, G, F, E, C, A

ROUTINE FOR PRE ORDER TRAVERSAL. void

preorder(struct tree* t)
{
if(t==NULL) return;
else { cout<<"\t"<<t-
>data; preorder(t-
>left); preorder(t-
>right); }
}

ROUTINE FOR POST ORDER TRAVERSAL.

void postorder(struct tree* t)

{
5
 if(t==NULL)
return; else {
postorder(t->left);
postorder(t->right);
cout<<"\t"<<t->data; }
}

ROUTINE FOR IN ORDER TRAVERSAL

void inorder(struct tree* t)

{
if(t==NULL)
return;
else
{ inorder(t->left);
cout<<"\t"<<t->data;
I norder(t->right);
}
}
EXPRESSION TREE

Expression Tree is a binary tree in which the leaf nodes are operands and the interior nodes are
operators. Like binary tree, expression tree can also be traversed by inorder, preorder and postorder
traversal.

Constructing an Expression Tree

Let us consider postfix expression given as an input for constructing an expression tree by performing the
following steps :
1. Read one symbol at a time from the postfix expression.
2. Check whether the symbol is an operand or operator.
(a) If the symbol is an operand, create a one - node tree and push a pointer on to the stack.
(b) If the symbol is an operator pop two pointers from the stack namely T1 and T2 and
form a new tree with root as the operator and T2 as a left child and T1 as a right child. A
pointer to this new tree is then pushed onto the stack.

6
Construct an expression for the given postfix expression AB+C*DE-/+G+

BINARY SEARCH TREE

Binary search tree is a binary tree in which for every node X in the tree, the values of all the keys
in its left subtree are smaller than the key value in X, and the values of all the keys in its right
subtree are larger than the key value in X.

DECLARATION OF A NODE IN BINARY SEARCH TREE struct

tree
{ int data; struct
tree *lchild; struct
tree *rchild;
};
7
struct tree *insert(struct tree *t, int element)

ROUTINE FOR CREATION OPERATION IN BINARY SEARCH TREE

struct tree * create(struct tree *t, int element)

{
t=(struct tree *)malloc(sizeof(struct tree));
t->data=element; t->lchild=NULL;
t->rchild=NULL;
return t;
}

ROUTINE FOR INSERTION OPERATION IN BINARY SEARCH TREE

To insert the element X into the tree, check with the root node T
* If X is less than the root, traverse to the left subtree recursively and insert at the left.
* If X is greater than the root, traverse to the right subtree recursively and insert at the right.

Example 1 Create a binary search tree using the following data elements: 45, 39, 56, 12, 34, 78, 32,
10, 89, 54, 67, 81

{
if(t==NULL)
{
t=(struct tree *)malloc(sizeof(struct tree));
8
 t->data=element; t->lchild=NULL;
t->rchild=NULL;
return t;
} else
{ if(element<t->data)
{ t->lchild=insert(t->lchild,element);
} else if(element>t->data)
{ t->rchild=insert(t->rchild,element);
}
else if(element==t->data)
{
printf("element already present\n");
} return
t;
}
}
ROUTINE FOR FINDING THE ELEMENT IN BINARY SEARCH TREE struct
tree * find(struct tree *t, int element)
{
if(t==NULL) return
NULL;
if(element<t->data) return(find(t->lchild,element));
else if(element>t->data) return(find(t->rchild,element));
else return t;
}
ROUTINE FOR FINDING THE MINIMUM ELEMENT IN BINARY SEARCH TREE
Traverse the node from root to left recursively until left is NULL. The node whose left is NULL
is the node with minimum value.

struct tree *findmin(struct tree *t)

{
if(t==NULL) return
NULL;
else if(t->lchild==NULL) return t;
else return(findmin(t->lchild));
}
ROUTINE FOR FINDING THE MAXIMUM ELEMENT IN BINARY SEARCH TREE
Traverse the node from root to right recursively until right is NULL. The node whose right is NULL is
the node with maximum value.

struct tree *findmax(struct tree *t)

{ if(t!=NULL)
{ while(t->rchild!=NULL) t=t-
>rchild; } return t; }
ROUTINE FOR DELETING AN ELEMENT IN BINARY SEARCH TREE
To delete an element, consider the following three possibilities.
Case 1: Node to be deleted is a leaf node (ie) No children.
Case 2: Node with one child.
9
 Case 3: Node with two children.
Node with no children (Leaf node)
If the node is a leaf node, it can be deleted immediately. Delete
node 78

Node with one child

If the node has one child, it can be deleted by adjusting its parent pointer that points to its child node.

Delete node 54

Node with two children

The general strategy is to replace the data of the element to be deleted with its smallest element of
the right subtree and recursively delete that node.

Delete node 56

10
struct tree * del(struct tree *t, int element)
{
if(t==NULL) printf("element not
found\n");
else if(element<t->data) t->lchild=del(t->lchild,element);
else if(element>t->data)
t->rchild=del(t->rchild,element);
else if(t->lchild&&t->rchild)
{ temp=findmin(t->rchild); t-
>data=temp->data;
t->rchild=del(t->rchild,t->data);
} else
{ temp=t; if(t-
>lchild==NULL) t=t-
>rchild;
else if(t->rchild==NULL) t=t->lchild;
free(temp);
}
return t;
}
Drawbacks of Binary search tree

• It employs recursive approach which requires more stack space.

• BST is not a balanced tree because it does not follow the concept of the balance factor.

AVL TREE
AVL Tree is invented by Adelson - Velsky and Landis in 1962. The tree is named AVL in honour of its
inventors.

11
AVL Tree is a self-adjusting height balanced binary search tree in which each node is associated with
a balance factor.
Balance factor= height (left sub-tree)-height (right sub-tree)
Tree is said to be balanced if balance factor of each node is -1, 0 and +1. Otherwise, the tree will be
unbalanced and need to be balanced.
DECLARATION OF A NODE struct
avltree
{
int data;
struct avltree *left,*right;
int height;
}*t;
INSERTING A NEW NODE IN AN AVL TREE
In an AVL tree, the insertion operation is performed with O(log n) time complexity. In AVL Tree,
new node is always inserted as a leaf node. The insertion operation is performed as follows...
Step 1: Insert the new element into the tree using Binary Search Tree insertion logic Step
2: After insertion, check the Balance Factor of every node.
Step 3: If the Balance Factor of every node is 0 or 1 or -1 then go for next operation.
Step 4: If the Balance Factor of any node is other than 0 or 1 or -1 then tree is said to be imbalanced. Then,
perform the suitable Rotation to make it balanced. And go for next operation. struct avltree *insertion(struct
avltree *t,int x)
{
if(t==NULL)
{
t=(struct avltree*)malloc(sizeof(struct avltree));
t->data=x;
t->left=t->right=NULL;
t->height=0;
}
else if(x<t->data)
{
t->left=insertion(t->left,x);
if((height(t->left)-height(t->right))==2)
{
if(x<t->left->data)
t=singlerotationwithleft(t);
else
t=doublerotationwithleft(t);
}
}
else if(x>t->data)
{
t->right=insertion(t->right,x);
if((height(t->right)-height(t->left)) ==2)
{
if(x>t->right->data)
t=singlerotationwithright(t);
else
12
 t=doublerotationwithright(t);
}
}
t->height=max(height(t->left),height(t->right))+1;
return t;
}

The following are the rotation operations

• Case 1 - Single Rotation with Left
• Case 2 - Single Rotation with Right
• Case 3 - Double Rotation with Left
• Case 4 - Double Rotation with Left

Case 1 (Single Rotation with Left)

The insertion was into the left subtree of the left child of α.

struct avltree *singlerotationwithleft(struct avltree *k2)

{
struct avltree *k1; k1=k2-
>left; k2->left=k1->right;
k1->right=k2;
k2->height=max(height(k2->left),height(k2->right))+1; k1->height=max(height(k1-
>left),height(k2))+1;
return k1;
}

Consider the AVL tree given in Fig. and insert 18 into it.

13
Case 2 (Single Rotation with Right)
The insertion was into the right subtree of the left child of α.

struct avltree *singlerotationwithright(struct avltree *k1)

{
struct avltree *k2; k2=k1-
>right; k1->right=k2->left;
k2->left=k1;
k1->height=max(height(k1->right),height(k1->left))+1;
k2->height=max(height(k2->right),height(k1))+1;
return k2;
}
Consider the AVL tree given in Fig. and insert 89 into it.

14
Case 3 (Double Rotation with Left)
The insertion was into the left subtree of the right child of α. Double rotation with left is equal to single
rotation with right and the single rotation with left.
struct avltree *doublerotationwithleft(struct avltree *k3)
{
k3->left=singlerotationwithright(k3->left);
return singlerotationwithleft(k3);
}

Case 4 (Double Rotation with Left)

The insertion was into the right subtree of the right child of α. Double rotation with right is equal to
single rotation with left and the single rotation with right.
struct avltree *doublerotationwithright(struct avltree *k1)
{
k1->right=singlerotationwithleft(k1->right);
return singlerotationwithright(k1);
}

15
Construct an AVL tree by inserting the following elements in the given order. 63, 9, 19, 27,
18, 108, 99, 81.
k2->left=k1;
k1->height=max(height(k1->right),height(k1->left))+1;
k2->height=max(height(k2->right),height(k1))+1;
return k2;
}

struct avltree *doublerotationwithleft(struct avltree *k3)

{
k3->left=singlerotationwithright(k3->left);
return singlerotationwithleft(k3);
}

struct avltree *doublerotationwithright(struct avltree *k1)

{
k1->right=singlerotationwithleft(k1->right);
return singlerotationwithright(k1);
}

int height(struct avltree *t)

{
if(t==NULL)
return -1;
else
return t->height;
}

static int max(int left,int right)

{
return left>right?left:right;

THREADED BINARY TREE

A threaded binary tree is the same as that of a binary tree but with a difference in storing the NULL
pointers. Consider the linked representation of a binary tree as given in Fig.

In the linked representation, a number of nodes contain a NULL pointer, either in their left
or right fields or in both. This space that is wasted in storing a NULL pointer can be efficiently
used to store some other useful piece of information.
For example, the NULL entries can be replaced to store a pointer to the in-order
predecessor or the in-order successor of the node. These special pointers are called threads and
binary trees containing threads are called threaded trees. In the linked representation of a threaded
binary tree, threads will be denoted using arrows.
16
Types
1. One-way threaded tree
2. Two way threaded tree

One-way threaded tree

A one-way threaded tree is also called a single-threaded tree. If the thread appears in the
left field, then the left field will be made to point to the in-order predecessor of the node. Such a
one-way threaded tree is called a left-threaded binary tree.

The in-order traversal of the tree is given as 8, 4, 9, 2, 5, 1, 10, 6, 11, 3, 7, 12

Two-way Threading
Node 5 contains a NULL pointer in its LEFT field, so it will be replaced to point to node 2,
which is its in-order predecessor. Similarly, the LEFT field of node 8 will contain NULL because
it has no in-order predecessor, the LEFT field of node 7 will point to node 3, the LEFT field of
node 9 will point to node 4, the LEFT field of node 10 will point to node 1, the LEFT field of node
11 will contain 6, and the LEFT field of node 12 will point to node 7.

17
Advantages of Threaded Binary Tree
• It enables linear traversal of elements in the tree.
• Linear traversal eliminates the use of stacks which in turn consume a lot of memory space and
computer time.
• It enables to find the parent of a given element without explicit use of parent pointers.
• Since nodes contain pointers to in-order predecessor and successor, the threaded tree enables
forward and backward traversal of the nodes as given by in-order fashion.
Thus, we see the basic difference between a binary tree and a threaded binary tree is that in
binary trees a node stores a NULL pointer if it has no child and so there is no way to traverse back.

B TREE

B tree is a specialized M-way tree that is widely used for disk access. B tree of order m can
have a maximum of m–1 keys and m pointers to its sub-trees. B tree may contain a large number
of key values and pointers to sub-trees. Storing a large number of keys in a single node keeps the
height of the tree relatively small.
B tree is designed to store sorted data and allows search, insertion, and deletion operations
to be performed in logarithmic amortized time. 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
1. Searching for an Element in a B Tree

Searching for an element in a B tree is similar to that in binary search trees. Consider the B tree
given in Fig. To search for 59

18
 Step 1. Begin at the root node. The root node has a value 45 which is less than 59.
Step 2. So, we traverse in the right sub-tree. The right sub-tree of the root node has two key values,
49 and 63. Since 49 < 59 < 63,
Step 3. Traverse the right sub-tree of 49, that is, the left sub-tree of 63. This sub-tree has three values,
54, 59, and 61. On finding the value 59, the search is successful.

2. Inserting a New Element in a B Tree

In a B tree, all insertions are done at the leaf node level. A new value is inserted in the B tree using the
algorithm given below.
Procedure:
Step 1. Search the B tree to find the leaf node where the new key value should be inserted. Step
2. If the leaf node is not full, that is, it contains less than m–1 key values, then insert the new
element in the node keeping the node’s elements ordered.
Step 3. If the leaf node is full, that is, the leaf node already contains m–1 key values, then
(a) insert the new value in order into the existing set of keys,
(b) split the node at its median into two nodes (note that the split nodes are half full), and (c) push
the median element up to its parent’s node. If the parent’s node is already full, then split the
parent node by following the same steps.
Example 1 Look at the B tree of order 5 given below and insert 8, 9, 39, and 4 into it.

Till now, we have easily inserted 8 and 9 in the tree because the leaf nodes were not full. But now,
the node in which 39 should be inserted is already full as it contains four values. Here we split the
19
nodes to form two separate nodes. But before splitting, arrange the key values in order (including
the new value). The ordered set of values is given as 21, 27, 36, 39, and 42. The median value is
36, so push 36 into its parent’s node and split the leaf nodes

Now the node in which 4 should be inserted is already full as it contains four key values. Here we
split the nodes to form two separate nodes. But before splitting, we arrange the key values in order
(including the new value). The ordered set of values is given as 4, 7, 8, 9, and 11. The median value
is 8, so we push 8 into its parent’s node and split the leaf nodes. But again, we see that the parent’s
node is already full, so we split the parent node using the same procedure.

3. Deleting an Element from a B Tree

Like insertion, deletion is also done from the leaf nodes. There are two cases of deletion. In the first
case, a leaf node has to be deleted. In the second case, an internal node has to be deleted. Let us
first see the steps involved in deleting a leaf node. Step 1. Locate the leaf node which has to be
deleted.
Step 2. If the leaf node contains more than the minimum number of key values (more than m/2 elements),
then delete the value.
Step 3. Else if the leaf node does not contain m/2 elements, then fill the node by taking an element either
from the left or from the right sibling.
(a) If the left sibling has more than the minimum number of key values, push its largest key
into its parent’s node and pull down the intervening element from the parent node to the leaf node
where the key is deleted.
(b) Else, if the right sibling has more than the minimum number of key values, push its smallest
key into its parent node and pull down the intervening element from the parent node to the leaf
node where the key is deleted.
Step 4. Else, if both left and right siblings contain only the minimum number of elements, then
create a new leaf node by combining the two leaf nodes and the intervening element of the parent
.

Example 1 Consider the following B tree of order 5 and delete values 93, 201, 180, and 72 from

20
it.

Example 2 Consider the B tree of order 3 given below and perform the following operations:
(a) insert 121, 87 and then (b) delete 36, 109.
21
Example 3. Create a B tree of order 5 by inserting the following elements: 3, 14, 7, 1, 8, 5, 11,
17, 13, 6, 23, 12, 20, 26, 4, 16, 18, 24, 25, and 19.

22
B+ TREES

23
 A B+ tree is a variant of a B tree which stores sorted data in a way that allows for efficient insertion,
retrieval, and removal of records, each of which is identified by a key. While a B tree can store
both keys and records in its interior nodes, a B+ tree, in contrast, stores all the records at the leaf
level of the tree; only keys are stored in the interior nodes.
The leaf nodes of a B+ tree are often linked to one another in a linked list. This has an added
advantage of making the queries simpler and more efficient.
Typically, B+ trees are used to store large amounts of data that cannot be stored in the main
memory. With B+ trees, the secondary storage (magnetic disk) is used to store the leaf nodes of
trees and the internal nodes of trees are stored in the main memory.
B+ trees store data only in the leaf nodes. All other nodes (internal nodes) are called index nodes
or i-nodes and store index values. This allows us to traverse the tree from the root down to the leaf
node that stores the desired data item. Figure shows a B+ tree of order 3.

Many database systems are implemented using B+ tree structure because of its simplicity. Since all
the data appear in the leaf nodes and are ordered, the tree is always balanced and makes searching
for data efficient.
A B+ tree can be thought of as a multi-level index in which the leaves make up a dense index and the
non-leaf nodes make up a sparse index.

The advantages of B+ trees can be given as follows:

1. Records can be fetched in equal number of disk accesses
2. It can be used to perform a wide range of queries easily as leaves are linked to nodes at the upper level
3. Height of the tree is less and balanced
4. Supports both random and sequential access to records
5. Keys are used for indexing
Comparison Between B Trees and B+ Trees
Sl. No B Tree B+ Tree
1. Search keys are not repeated Store redundant search key
2. Data is stored in internal or leaf nodes Data is stored only in leaf nodes
3. Searching takes more time as data may be Searching data is very easy as the data can be found
found in a leaf or non-leaf node in leaf nodes only
4. Deletion of non-leaf node is very complicated Deletion is very easy as the data can be found in leaf
nodes only
5. Leaf nodes cannot be stored using linked lists Leaf node data are ordered using sequential linked
lists
6. The structure and operations are complicated The structure and operations are simple

24
1. Inserting a New Element in a B+ Tree
The steps to insert a new node in a B+ Tree are summarized below Step
1: Insert the new node as the leaf node.
Step 2: If the leaf node overflows, split the node and copy the middle element to next index node.
Step 3: If the index node overflows, split that node and move the middle element to next index
page.

Example 1. Consider the B+ tree of order 4 given and insert 33 in it.

2 Deleting an Element from a B+ Tree

The steps to delete a node from a B+ tree are summarized below Step
1: Delete the key and data from the leaves.
Step 2: If the leaf node underflows, merge that node with the sibling and delete the key in between
them.
Step 3: If the index node underflows, merge that node with the sibling and move down the
key in between them.

Example 1: Consider the B+ tree of order 4 given below and delete node 15 from it.

25
26