## General programming

Moderators: None (Apply to moderate this forum)
Number of posts: 2784

This Forum Only

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);
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 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
}

}
}

{
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;
}
}

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;
}

## Recent Jobs

Official Programmer's Heaven Blogs
Web Hosting | Browser and Social Games | Gadgets

Popular resources on Programmersheaven.com
Assembly | Basic | C | C# | C++ | Delphi | Flash | Java | JavaScript | Pascal | Perl | PHP | Python | Ruby | Visual Basic