In the following code I want to make the tree height balanced whenever a new leaf node is created with the insertion value.here if the height of the two subtrees of a node differs by more than one level a rotation is needed for each node on the search path from leaf to root.here atmost one rotation is needed to rebalance the tree so processing stops after one rotation.
I also want to know if my code of insertion justifies the algorithm and works according to it and any suggestions for it's improvent.
//all data in a node are sorted in ascending order
#include <stdio.h>
#include <conio.h>
#include <malloc.h>
#define MAX_KEYS 100 //max no of keys per node
typedef struct ttreenode
{
ttreenode* lchild;
ttreenode* rchild;
ttreenode* parent;
int data[MAX_KEYS];
int currSize;
} ttreenode;
void insert (struct ttreenode**,int);
void add_val(struct ttreenode**,int,int);
int find_insert_position(struct ttreenode**,int);
void make_Leaf_Node(struct ttreenode**,int);
struct ttreenode* search_node(struct ttreenode*,int);
bool search(struct ttreenode**,int);
void insert(ttreenode** pNode, int val)
//insert a given value in proper node
{
if(*pNode == NULL)// Check for root
{
(*pNode) = (ttreenode*)malloc(sizeof(ttreenode));
(*pNode)->currSize = 1;
(*pNode)->data[0] = val;
(*pNode)->lchild = (*pNode)->rchild =(*pNode)->parent= NULL;
}
else// it is not the root
{
// Check for where to add
if(search_node(*pNode,val)!=NULL)
// got a bounding node
{
if((*pNode)->currSize-1 > 0)
// current node Contains keys
{
if((*pNode)->currSize-1 < MAX_KEYS)
{
// Space exists here,so try to Insert in this array.
int position=find_insert_position(pNode,val);
add_val( pNode,position,val);
// add the value in this node
}
else
{//no space here
int newInsertElem = (*pNode)->data[0];
//remove the min element of this node and inserts in its place the given value
(*pNode)->data[0] = val;
//make this removed min element new value of insertion and
// try to insert it in the leaf node of the search path
insert(&((*pNode)->lchild),newInsertElem);
}
// insert in the leaf of left subtree
}
else// Does not contain any key.Insert here
{
(*pNode)->data[0] = val;
(*pNode)->currSize++;
}
}
else
// no bounding node is found.ie search_node returns NULL;
{
if((*pNode)->currSize < MAX_KEYS)
// check for room for insertion in last node of search path
insert(&((*pNode)->lchild),val);
// insert in leaf of left subtree of the search path
else
// no room for insertion here
make_Leaf_Node(pNode,val);
//so, create proper new leaf node with this value
}
}
}
void add_val(ttreenode** pNode,int position,int val)
{
if(position!= -1)//found position of insertion
{
for(int i =(*pNode)->currSize-1; i>=position;i--)
(*pNode)->data[i]=(*pNode)->data[i-1];
//shift element to right starting from position to create room for insertion.
(*pNode)->data[i]=val;
(*pNode)->currSize++;
}
else
printf("the given value cannot be inserted in this node");
}
int find_insert_position(ttreenode** pNode,int val)
{
for (int i=0;i<(*pNode)->currSize-1;i++)
{
if ((*pNode)->data[i]>val && (*pNode)->data[i+1]<val)
//check where to insert
return i+1;
// return position from which elements are to be shifted to right.
else
break;
}
return -1;// insertion position not found
}
struct ttreenode* search_node(ttreenode*pNode,int val)
// searches for the bounding node for a given value
{
if(val<(pNode)-> data[0])// is the value less than min value?
{
search_node((pNode)->lchild,val); // then proceed to left
return ((pNode)->lchild);// got the node
}
else// is the value not less than min value?
{
if(val>(pNode)->data[(pNode)->currSize])
// is the value greater than max value?
{
search_node((pNode)->rchild,val); // then proceed to right
return ((pNode)->rchild) // got the node
}
else//is the value within the range of min and max?
return pNode;// this node is the bounding node.
}
return NULL;//no bounding node found
}
void make_Leaf_Node(struct ttreenode**pNode,int val)
{ //create a left leaf node and insert there
if(val<(*pNode)->data[0])
{//if the valueis less than the min value of the last node of search path?
((*pNode)->lchild)=(ttreenode*)malloc(sizeof(ttreenode));
((*pNode)->lchild)->lchild=((*pNode)->lchild)->rchild=NULL;
((*pNode)->lchild)->parent=(*pNode);
((*pNode)->lchild)->data[0]=val;
((*pNode)->lchild)->currSize=1;
}
if(val>(*pNode)->data[(*pNode)->currSize-1])
// create a right leaf node and insert there if
{//the value is greater than max value of last node of search path
((*pNode)->rchild)=(ttreenode*)malloc(sizeof(ttreenode));
((*pNode)->rchild)->lchild=((*pNode)->rchild)->rchild=NULL;
((*pNode)->rchild)->parent=(*pNode);
((*pNode)->rchild)->data[0]=val;
((*pNode)->rchild)->currSize=1;
}
}
bool search(struct ttreenode**pNode,int val)
//searches for a given value in the tree
{
if(*pNode == NULL)// Check for root
{
(*pNode) = (ttreenode*)malloc(sizeof(ttreenode));
(*pNode)->currSize = 1;
(*pNode)->data[0] = val;
(*pNode)->lchild = (*pNode)->rchild =(*pNode)->parent= NULL;
}
else
{// search for the bounding node
if(search_node(*pNode,val)!=NULL)//got the bounding node
{
if (! val)
return false;
if ((*pNode)->currSize <= 5)
{// Small number of keys, do a linear search.
if ((*pNode)->currSize == 0)
return false;
for (int i = 0; i < (*pNode)->currSize; i++)
{
if ((*pNode)->data[i] >= val)
break;
}
if ((*pNode)->data[i] == val)
return true;
else
return false;
}
// Do a binary search otherwise .
int lo = 0, hi = (*pNode)->currSize, mid=0;
while (lo <= hi)
{
mid = (lo + hi)/2;
if ((*pNode)->data[mid] == val)
return true;
if ((*pNode)->data[mid] < val)
lo = mid+1;
else
hi = mid-1;
}
}
else
return false;
}
return false;
}
