TREES- Binary Trees, Binary Search Trees, AVL Trees
A Tree is a finite set of one or more nodes such that
i) There is a specially designated node called the Root.
ii) The remaining nodes are partitioned into n > = 0 disjoint sets T1 T2 T3…. Tn. Where each of these sets is a Tree.
A node stands for the item of information plus the branches to other items.
The number of subtrees of a node is called its degree. Nodes that have degree ZERO are called Leaf nodes or Terminal nodes.
There are many applications for trees . One of the popular uses is the directory structure in many common operating systems including UNIX, DOS and Windows.
Binary Trees
Binary tree is a tree in which no node can have more than two children. Binary tree is either empty, or it consists of a node called the root together with two binary trees called the left sub-tree and the right sub-tree.
A Binary tree is a tree in which no node can have more than two children.
To construct a binary tree with one node is to make that node its root and to make both left and right sub trees empty.
With two nodes in the tree, one of them will be the root and the other will be in a sub tree. Thus either the left or the right sub tree must be empty, and the other will contain exactly one node.
Binary tree with three nodes.
Consider the following Binary Tree.
Each element of a binary tree is called Node of the tree. Node ‘A’ is the root of the tree and node ‘B’ is the root of its left subtree. Node ‘A’ is said to be the father of node ‘B’ and node ‘B’ is said to be the left son of node ‘A’. A node that have no sons is called a Leaf. D,E and F are leaf nodes of the above binary tree.
Level: The level of a node in a binary tree is defined as follows: The root of the tree has level 0 and the level of any other node in the tree is one more than the level of the father.
Depth: The depth of a binary tree is the maximum level of any leaf in the tree. This equals the length of the longest path from the root to any leaf. The depth of the above tree is 3.
Strictly Binary Tree: If every non leaf node in a binary tree has non empty left and right sub-trees, then the tree is termed as a strictly binary tree.
A strictly binary tree with ’n’ leaves always contains 2*n-1 nodes
Complete Binary Tree:
We can clearly say that any level ‘L’ of a binary tree ‘T’, there should be at most 2L nodes. A tree is said to be complete if all its levels except possibly the last, have the maximum number of possible nodes and if all the nodes at last level appear as far lest as possible.
A complete binary tree of depth d is the binary tree of depth d that contains exactly 2L nodes at each level ‘L’ between o and d.
Level 0 contains 20 nodes i.e. 1 node
Level 1 contains 21 nodes i.e. 2 nodes
Level 2 contains 22 nodes i.e. 4 nodes
Level 3 contains 23 nodes i.e. 8 nodes
Total no of nodes in a complete binary tree of depth D is the sum of the number of nodes at each level between 0 to D i.e.,
20 + 21 + 22 + ……… + 2D
The above complete binary tree of depth 3 contains 15 nodes, which is shown as follows.
20 + 21 + 22 + 23
1 + 2 + 4 + 8
15
by induction
20 + 21 + 22 + 23 + ……… + 2d = 2D+1–1
Total no of leaves = 23 = 23 = 8
Total no of non-leaves = 2d -1= 23 –1 = 8 –1 = 7
Total no of nodes = 2d + 2d –1
= 2 X 2d –1
= 2d+1 –1
= 23+1–1
= 24 –1
= 16–1
= 15
Implementation: The declaration of tree nodes is similar in structure to that for doubly linked lists, in that a node is a structure consisting of the key information plus two pointers ( left and right) to other nodes.
Binary trees have many important uses not associated with searching. One of the principal use of binary trees is in the area of compiler design.
struct node
{
int data;
struct node *left, *right;
};
typedef struct node treenode;Expression Trees: (a + b * c ) + ((d * e + f) *g)
Figure shows an example of an expression tree. The leaves of an expression tree are operands and non-leaf nodes are operators
Traversal of binary tree:
One of the most important operations on a binary tree is traversal, moving through all the nodes of the binary tree, visiting each one in turn.
We can traverse the binary tree in many ways.
- Preorder VLR
- Inorder LVR
- Postorder LRV
With preorder traversal, the node is visited before the subtrees.
With inorder traversal, the node is visited between the subtrees.
With postorder traversal, the node is visited after the subtrees.
In all cases left is visited before right.
Consider the following binary tree.
To traverse a non-empty binary tree in preorder, we perform the following three operations.
(i) Visit the root
(ii) Traverse the left subtree in preorder
(iii) Traverse the right subtree in preorder
To traverse a non-empty binary tree in inorder, we perform the following three operations.
(i) Traverse the left subtree in inorder.
(ii) Visit the root.
(iii) Traverse the right subtree in inorder.
To traverse a non-empty binary tree in postorder, we perform the following three operations.
(i) Traverse the left subtree in postorder.
(ii) Traverse the right subtree in postorder.
(iii) Visit the root.
treenode *p
{
if ( p != NULL)
{
printf (“%d”, p->data);
preorder (p->left);
preorder ( p->right);
}
}inorder (p) /* Function to traverse a binary tree in inorder */
treenode *p;
{
if (p != NULL)
{
inorder (p->left);
printf(“%d”, p->data);
inorder (p->right);
}
}postorder (p) /* Function to traverse a binary tree in postorder */
treenode *p;
{
if (p!= NULL)
{
postorder(p->left);
postorder(p->right);
printf(“%d”, p->data);
}
}
Expression Trees:
Binary Search Tree:
Def: A Binary search tree is a binary tree that is either empty or in which every node contains a key and satisfies the following conditions.
1. The key in the left child of a node (if it exists) is less than the key in its parent node.
2. The key in the right child of a node is greater than the key in its parent node.
3. The left and right subtrees of the root are again binary search trees.
No two entries in a binary search tree may have equal keys.
Because of the recursive definition of trees, it is common to write these routines recursively. The average depth of a binary search tree is 0 (log N).
Creating a binary search tree:
The buildtree routine is conceptually simple. To insert X into tree T proceed down the tree right from root node. If X is found, do nothing. Otherwise insert X at the last spot on the path traversed.
Each time we compare X with the value and if it is greater than the node value, we check is the right node is NULL or not. If it is NULL we add this node as right node of the current node. If the right node is not NULL, we go to that node and again we compare X with the value of that node.
If X is less than the node value, we check is the left node is NULL or not. If it is NULL we add this node as left node of the current node. If the left node is not NULL, we go to that node and again we compare X with the value of that node. Repeat this process until you add the node with value X to the binary search tree.
buildtree(p,x)
treenode *p;
int x;
{
treenode *q;if ( x > p->data )
if (p->right == NULL)
{
q=(treenode *)malloc(sizeof(treenode));
q->data=x;
q->left=NULL;
q->right=NULL;
p->right=q;
}
else
buildtree(p->right,x);
elseif ( x < p->data )
if (p->left == NULL)
{
q=(treenode *)malloc(sizeof(treenode));
q->data=x;
q->left=NULL;
q->right=NULL;
p->left=q;
}
else
buildtree(p->left,x);
else
printf("Duplicate node \n");
}
Finding the number of leafs in a binary search tree:
We know how to traverse a binary search tree. Traversing is nothing but visiting each and every node of the Binary search tree. We have 3 traversal techniques. In all the 3 traversal techniques we visit all the nodes of the binary search tree.
Now while visiting the nodes check whether the node is a leaf or not. A node is called leaf node if the left and right links of the node are pointing to NULL.
You can take any traversal technique. Instead of visiting the node compare whether the left and right links are NULL or not. If the left and right links are NULL then you can increase the count of leaf nodes. By the end of the traversal you can get the count of leaf nodes.
/*---------------- Counting LEAF nodes */
leafcount(p,cnt)
treenode *p;
int *cnt;
{
if (p!=NULL)
{
leafcount(p->left,cnt);
leafcount(p->right,cnt);
if ((p->left==NULL)&&(p->right==NULL))
(*cnt)++;
}
}In the above function we have taken the postfix type of traversal. To count the number of leaf nodes we have used a variable cnt and assign 0. Instead of printf statement we are comparing the left and right links for NULL . If both pointing to NULL count will be increased.
Finding height / depth of a binary search tree:
int max(a,b)
int a,b;
{
if (a>b)
return(a);
else
return(b);
}/*---------------------------------to find height of BST*/
int height(p)
treenode *p;
{
if (p==NULL)
return(-1);
else
return(1+max(height(p->left),height(p->right)));
}
Solution:
The first letter in preorder must be the root. So ‘A’ is our root. By the definition of inorder, all nodes preceeding ‘A’ must occur in the left subtree and all nodes succeeding ‘A’ must occur in right subtree.
At this stage by seeing the preorder ‘B’ comes before ‘D’. So ‘B’ is the next root and from the inorder we see ‘B’ has an empty right subtree and ‘D’ is in it’s left subtree.
The Post Order Traversal : DBECA
Program to create a Binary Search Tree and To traverse the Binary Search Tree in inorder, preorder and postorder, To count the leaf nodes, To find the height of BST
#include <stdio.h>
#include <conio.h>
//#include <alloc.h>
struct node
{
int data;
struct node *left;
struct node *right;
};
typedef struct node treenode;/*------------------------------ Function to create a binary tree */
/* ------------------------------Adds a node to a Binary tree */
buildtree(p,x)
treenode *p;
int x;
{
treenode *q;if ( x > p->data )
if (p->right == NULL)
{
q=(treenode *)malloc(sizeof(treenode));
q->data=x;
q->left=NULL;
q->right=NULL;
p->right=q;
}
else
buildtree(p->right,x);
elseif ( x < p->data )
if (p->left == NULL)
{
q=(treenode *)malloc(sizeof(treenode));
q->data=x;
q->left=NULL;
q->right=NULL;
p->left=q;
}
else
buildtree(p->left,x);
else
printf("Duplicate node \n");
}/*---------------- Preorder Traversal */
preorder(p)
treenode *p;
{
if (p!=NULL)
{
printf("%d ",p->data);
preorder(p->left);
preorder(p->right);
}
}
/*---------------- Inorder Traversal */
inorder(p)
treenode *p;
{
if (p!=NULL)
{
inorder(p->left);
printf("%d ",p->data);
inorder(p->right);
}
}
/*---------------- Postorder Traversal */
postorder(p)
treenode *p;
{
if (p!=NULL)
{
postorder(p->left);
postorder(p->right);
printf("%d ",p->data);
}
}
/*---------------- Counting LEAF nodes */
leafcount(p,cnt)
treenode *p;
int *cnt;
{
if (p!=NULL)
{
leafcount(p->left,cnt);
leafcount(p->right,cnt);
if ((p->left==NULL)&&(p->right==NULL))
(*cnt)++;
}
}
int max(a,b)
int a,b;
{
if (a>b)
return(a);
else
return(b);
}/*---------------------------------to find height of BST*/
int height(p)
treenode *p;
{
if (p==NULL)
return(-1);
else
return(1+max(height(p->left),height(p->right)));
}void main()
{
treenode *root;
char opt;
int x,cnt,ht;
//clrscr();
printf ("enter the root value ");
scanf("%d",&x);
root=(treenode *)malloc(sizeof(treenode));
root->data=x;
root->left=NULL;
root->right=NULL;
printf("another node y/n? ");
fflush(stdin);
opt=getchar();
while (opt!='n')
{
printf ("enter a node value ");
scanf("%d",&x);
buildtree(root,x);
printf("another node y/n? ");
fflush(stdin);
opt=getchar();
}
printf("\nPreorder Traversal \n");
preorder(root);
printf("\nInorder Traversal \n");
inorder(root);
printf("\nPostorder Traversal \n");
postorder(root);
cnt=0;
leafcount(root,&cnt);
printf("\nTotal number of leaf nodes = %d\n",cnt);
ht=height(root);
printf("Height of the binary search tree = %d\n",ht);
getch();
}
Output:
enter the root value 3
another node y/n? y
enter a node value 2
another node y/n? y
enter a node value 5
another node y/n? y
enter a node value 6
another node y/n? nPreorder Traversal
3 2 5 6
Inorder Traversal
2 3 5 6
Postorder Traversal
2 6 5 3
Total number of leaf nodes = 2
Height of the binary search tree = 2
Representation of Binary Trees using Arrays
Each node is sequentially arranged from top to bottom and from left to right. Let us understand this matter by numbering each node. The numbering will start from root node and then remaining nodes will give ever increasing numbers in level wise direction. The nodes on same level will be numbered from left to right.
AVL Trees
Tree is one of the most important data structure that is used for efficiently performing operations like insertion, deletion and searching of values. However, while working with a large volume of data, construction of a well-balanced tree for sorting all data is not feasible. Thus only useful data is stored as a tree, and the actual volume of data being used continually changes through the insertion of new data and deletion of existing data. You will find in some cases where the NULL link to a binary tree to special links is called as threads and hence it is possible to perform traversals, insertions, deletions without using either stack or recursion. In this chapter, you will learn about the Height balance tree which is also known as the AVL tree.
What is AVL Tree:
AVL tree is a binary search tree in which the difference of heights of left and right subtrees of any node is less than or equal to one. The technique of balancing the height of binary trees was developed by Adelson, Velsky, and Landis and hence given the short form as AVL tree or Balanced Binary Tree.
What if the input to binary search tree comes in a sorted (ascending or descending) manner? It will then look like this −
It is observed that BST’s worst-case performance is closest to linear search algorithms, that is Ο(n). In real-time data, we cannot predict data pattern and their frequencies. So, a need arises to balance out the existing BST.
Named after their inventor Adelson, Velsky and Landis, AVL trees are height balancing binary search tree. AVL tree checks the height of the left and the right sub-trees and assures that the difference is not more than 1.
This difference is called the Balance Factor.
Consider the following trees. Here we see that the first tree is balanced and the next two trees are not balanced −
In the second tree, the left subtree of C has height 2 and the right subtree has height 0, so the difference is 2. In the third tree, the right subtree of A has height 2 and the left is missing, so it is 0, and the difference is 2 again. AVL tree permits difference (balance factor) to be only 1.
BalanceFactor = height(left-subtree) − height(right-subtree)If the difference in the height of left and right sub-trees is more than 1, the tree is balanced using some rotation techniques.
AVL Rotations
To balance itself, an AVL tree may perform the following four kinds of rotations −
· Left rotation
· Right rotation
· Left-Right rotation
· Right-Left rotation
The first two rotations are single rotations and the next two rotations are double rotations. To have an unbalanced tree, we at least need a tree of height 2. With this simple tree, let’s understand them one by one.
Left Rotation
If a tree becomes unbalanced, when a node is inserted into the right subtree of the right subtree, then we perform a single left rotation −
In our example, node A has become unbalanced as a node is inserted in the right subtree of A’s right subtree. We perform the left rotation by making A the left-subtree of B.
Right Rotation
AVL tree may become unbalanced, if a node is inserted in the left subtree of the left subtree. The tree then needs a right rotation.
As depicted, the unbalanced node becomes the right child of its left child by performing a right rotation.
Left-Right Rotation
Double rotations are slightly complex version of already explained versions of rotations. To understand them better, we should take note of each action performed while rotation. Let’s first check how to perform Left-Right rotation. A left-right rotation is a combination of left rotation followed by right rotation.
Right-Left Rotation
The second type of double rotation is Right-Left Rotation. It is a combination of right rotation followed by left rotation.
An AVL tree can be defined as follows:
Let T be a non-empty binary tree with TL and TR as its left and right subtrees. The tree is height balanced if:
· TL and TR are height balanced
· hL — hR <= 1, where hL — hR are the heights of TL and TR
The Balance factor of a node in a binary tree can have value 1, -1, 0, depending on whether the height of its left subtree is greater, less than or equal to the height of the right subtree.
Advantages of AVL tree
Since AVL trees are height balance trees, operations like insertion and deletion have low time complexity. Let us consider an example:
If you have the following tree having keys 1, 2, 3, 4, 5, 6, 7 and then the binary search tree will be like the second figure:
To insert a node with a key Q in the binary tree, the algorithm requires seven comparisons, but if you insert the same key in AVL tree, from the above 1st figure, you can see that the algorithm will require three comparisons.
Representation of AVL Trees
Struct AVLNode
{
int data;
struct AVLNode *left, *right;
int balfactor;
};Algorithm for Insertion
Step 1: First, insert a new element into the tree using BST’s (Binary Search Tree) insertion logic.
Step 2: After inserting the elements you have to check the Balance Factor of each node.
Step 3: When the Balance Factor of every node will be found like 0 or 1 or -1 then the algorithm will proceed for the next operation.
Step 4: When the balance factor of any node comes other than the above three values then the tree is said to be imbalanced. Then perform the suitable Rotation to make it balanced and then the algorithm will proceed for the next operation.
Algorithm for Deletion
We will try to understand this algorithm using an example but before that let’s go over the major steps of this algorithm. Note that this algorithm is a bottom-up algorithm and hence height restoration of the tree proceeds from leaves to root.
This algorithm is basically a modification of the usual BST deletion algorithm.
The steps of this algorithm are :
1. Use general BST deletion algorithm to delete given key from the AVL tree.
2. After deletion, update the height of the current node of the AVL tree.
3. Now check the ‘balance’ at the current node by getting the difference of height of left sub-tree and height of right sub-tree.
3a. If ‘balance’ > 1 then that means the height of the left sub-tree is greater than the height of the right sub-tree. This indicates left-left or left-right case. To confirm if this is left-left or left-right case, we check the balance of left sub-tree of current node. If it greater than 0 then that confirms left-left case, if it less than 0 then that confirms left-right case. If it is equal to 0, then this we can either consider this as a left-left case or as a left-right case. In this implementation, we consider this as left-left case for efficiency. For left-left case, we do a right rotation at the current node. For the left-right case, we do a left rotation at left child of current node followed by a right rotation at the current node itself.
3b. If ‘balance’ < -1 then that means the height of the right sub-tree is greater than the height of the left sub-tree. This indicates right-right or right-left case. In this case, if balance of right sub-tree of current node is less than 0 then this confirms right-right case, if it is greater than 0 then this confirms right-left case. If it is equal to 0, then we can either consider this as a right-right case or a right-left case. In this implementation, we will consider this as a right-right case. In right-right case, we do a left rotation at the current node. In right-left case, we do a right rotation at the right child of current node followed by left rotation at the current node itself.
As you can confirm this tree satisfies height balance property for AVL tree.
Program for AVL Tree in C
//----------------------------------------------------------------------
// Program to create, insert, delete and print AVL tree
//----------------------------------------------------------------------
#include<stdio.h>
typedef struct node
{
int data;
struct node *left,*right;
int ht;
}node;node *insert(node *,int);
node *Delete(node *,int);
void preorder(node *);
void inorder(node *);
int height( node *);
node *rotateright(node *);
node *rotateleft(node *);
node *RR(node *);
node *LL(node *);
node *LR(node *);
node *RL(node *);
int BF(node *);int main()
{
node *root=NULL;
int x,n,i,op;do
{
printf("\n1)Create:");
printf("\n2)Insert:");
printf("\n3)Delete:");
printf("\n4)Print:");
printf("\n5)Quit:");
printf("\n\nEnter Your Choice:");
scanf("%d",&op);switch(op)
{
case 1: printf("\nEnter no. of elements:");
scanf("%d",&n);
printf("\nEnter tree data:");
root=NULL;
for(i=0;i<n;i++)
{
scanf("%d",&x);
root=insert(root,x);
}
break;case 2: printf("\nEnter a data:");
scanf("%d",&x);
root=insert(root,x);
break;case 3: printf("\nEnter a data:");
scanf("%d",&x);
root=Delete(root,x);
break;
case 4: printf("\nPreorder sequence:\n");
preorder(root);
printf("\n\nInorder sequence:\n");
inorder(root);
printf("\n");
break;
}
}while(op!=5);return 0;
}node * insert(node *T,int x)
{
if(T==NULL)
{
T=(node*)malloc(sizeof(node));
T->data=x;
T->left=NULL;
T->right=NULL;
}
else
if(x > T->data) // insert in right subtree
{
T->right=insert(T->right,x);
if(BF(T)==-2)
if(x>T->right->data)
T=RR(T);
else
T=RL(T);
}
else
if(x<T->data)
{
T->left=insert(T->left,x);
if(BF(T)==2)
if(x < T->left->data)
T=LL(T);
else
T=LR(T);
}T->ht=height(T);
return(T);
}node * Delete(node *T,int x)
{
node *p;
if(T==NULL)
{
return NULL;
}
else
if(x > T->data) // insert in right subtree
{
T->right=Delete(T->right,x);
if(BF(T)==2)
if(BF(T->left)>=0)
T=LL(T);
else
T=LR(T);
}
else
if(x<T->data)
{
T->left=Delete(T->left,x);
if(BF(T)==-2) //Rebalance during windup
if(BF(T->right)<=0)
T=RR(T);
else
T=RL(T);
}
else
{ //data to be deleted is found
if(T->right!=NULL)
{ //delete its inorder succesor
p=T->right;while(p->left!= NULL)
p=p->left;
T->data=p->data;
T->right=Delete(T->right,p->data);
if(BF(T)==2)//Rebalance during windup
if(BF(T->left)>=0)
T=LL(T);
else
T=LR(T);\
}
else
return(T->left);
}
T->ht=height(T);
return(T);
}int height(node *T)
{
int lh,rh;
if(T==NULL)
return(0);if(T->left==NULL)
lh=0;
else
lh=1+T->left->ht;if(T->right==NULL)
rh=0;
else
rh=1+T->right->ht;
if(lh>rh)
return(lh);
return(rh);
}node * rotateright(node *x)
{
node *y;
y=x->left;
x->left=y->right;
y->right=x;
x->ht=height(x);
y->ht=height(y);
return(y);
}node * rotateleft(node *x)
{
node *y;
y=x->right;
x->right=y->left;
y->left=x;
x->ht=height(x);
y->ht=height(y);return(y);
}node * RR(node *T)
{
T=rotateleft(T);
return(T);
}node * LL(node *T)
{
T=rotateright(T);
return(T);
}node * LR(node *T)
{
T->left=rotateleft(T->left);
T=rotateright(T);return(T);
}node * RL(node *T)
{
T->right=rotateright(T->right);
T=rotateleft(T);
return(T);
}int BF(node *T)
{
int lh,rh;
if(T==NULL)
return(0);if(T->left==NULL)
lh=0;
else
lh=1+T->left->ht;if(T->right==NULL)
rh=0;
else
rh=1+T->right->ht;return(lh-rh);
}void preorder(node *T)
{
if(T!=NULL)
{
printf("%d(Bf=%d)",T->data,BF(T));
preorder(T->left);
preorder(T->right);
}
}void inorder(node *T)
{
if(T!=NULL)
{
inorder(T->left);
printf("%d(Bf=%d)",T->data,BF(T));
inorder(T->right);
}
}
Output:
1)Create:
2)Insert:
3)Delete:
4)Print:
5)Quit:Enter Your Choice:1Enter no. of elements:5Enter tree data:12
13
14
15
161)Create:
2)Insert:
3)Delete:
4)Print:
5)Quit:Enter Your Choice:2Enter a data:111)Create:
2)Insert:
3)Delete:
4)Print:
5)Quit:Enter Your Choice:4Preorder sequence:
13(Bf=0)12(Bf=1)11(Bf=0)15(Bf=0)14(Bf=0)16(Bf=0)Inorder sequence:
11(Bf=0)12(Bf=1)13(Bf=0)14(Bf=0)15(Bf=0)16(Bf=0)1)Create:
2)Insert:
3)Delete:
4)Print:
5)Quit:Enter Your Choice:5
