problem with the code of Insertion in a 2-3 tree??

[bilbatori]

Hi,

I've been trying to identify the error in this code of insertion in a 2-3 Tree. I do know its something with the search function...Can some one figure out whats wronge with the code??

bool Two3::Insert(int val)
{
	int x=val;
	bool done=false;//inserted or not??
	
	if (IsEmpty())//empty tree creating the root
	{
		Two3Node* create=new Two3Node;
		create->DataL=x;
		root=create;
		done=true;
	}
	//search for a terminal node
	
	Two3Node* prev=NULL;//will be the parent
	Two3Node* curr=NULL;//will be the InsertionPoint
	
	curr=root;
	bool found=true;// will end the loop if a same key is encountered in search;
	stack<Two3Node*> S;// stack is empty
	do// ======================> condition issue
	{
		prev=curr;
		
		S.push(prev);//maintaining stack of ancestors
		
		if(curr->DataL==x || curr->DataR==x)
		{
			cout<<"\n While searching for a leaf node same key is encountered\n";
			found=false;
		}
		else if(x<curr->DataL)
		{
			curr=curr->Lch;
		}
		else if(x>curr->DataR)
		{
			curr=curr->Rch;
		}
		else if (x>curr->DataL && x<curr->DataR)
		{
			curr=curr->Midch;
		}
	}while (curr && found && !S.empty());
	//when the loop terminates our curr is 
	//null 
	//or found is false OR the stack got empty
	
	curr=prev;//curr was null when loop terminated tracking it back to the leaf node
	prev=S.pop();//pops the leaf node
	prev=S.pop();//pops parent stored for the leaf node;

	if(found)
	{
		// NOW i need to check if current is a 3-node or a 2-node	
		//CASE 1 (curr = 2 Node && curr = terminal node)
		if (NodeType(curr) && IsLeaf(curr))
		{
			if (x< curr->DataL)
			{
				curr->DataR=curr->DataL;
				curr->DataL=x;
				done= true;
			}
			else if (x > curr->DataL)
			{
				curr->DataR=x;
				done= true;
			}
		}//end if curr 2node
		
		// curr = 3-node 
		else if(!NodeType(curr))
		{
			//split child level
			int a,b,c;
			a=min(curr->DataL,curr->DataR,x);
			b=mid(curr->DataL,curr->DataR,x);
			c=largest(curr->DataL,curr->DataR,x);
			
			Two3Node* newNode= new Two3Node;
			newNode->DataL=c;
			//leave a in curr
			curr->DataL=a;
			curr->DataR=maxVal;
			
			//will be used if the parent is a 3-node
			Two3Node* n1=new Two3Node;
			n1->DataL=b;
			
			//insert b in parent of curr	
			//2a. Parent is a 2-Node
			if (NodeType(prev))
			{
				if(b< prev->DataL)
				{//Value b is less than left key
					prev->DataR=prev->DataL;
					prev->DataL=b;
					prev->Rch=prev->Midch;
					prev->Midch=newNode;
					delete n1;
					done=true;
				}
				if(b> prev->DataL)
				{//Value b is more than left key
					prev->DataR=b;
					prev->Rch=newNode;
					delete n1;
					done= true;
				}
			}//end if Parent is a 2-Node
			
			//parent is a 3-node
			else if (!NodeType(prev))
			{
				int x,y,z;
				x=min(prev->DataL,prev->DataR,b);
				y=mid(prev->DataL,prev->DataR,b);
				z=largest(prev->DataL,prev->DataR,b);
				
				if (prev->Lch==curr)
				{
					Two3Node* new2=new Two3Node;
					new2->DataL=z;
					new2->Lch=prev->Midch;
					new2->Midch=prev->Rch;
					
					n1->Lch=curr;
					n1->Midch=newNode;
					
					prev->DataL=b;//b made the left key
					prev->DataR=maxVal;
					prev->Lch=n1;
					prev->Midch=new2;
					prev->Rch=NULL;
					done=true;
				}
				else if(prev->Midch==curr)
				{
					Two3Node* new2=new Two3Node;
					new2->DataL=z;
					new2->Lch=newNode;
					new2->Midch=prev->Rch;
					
					n1->Lch=prev;
					n1->Midch=new2;
					
					
					prev->DataR=maxVal;
					prev->Rch=NULL;
					done= true;
				}
				else if(prev->Rch==curr) 
				{
					Two3Node* new2=new Two3Node;
					new2->DataL=y;
					new2->Lch=prev;
					new2->Midch=n1;
					
					n1->Lch=curr;
					n1->Midch=newNode;
					
					prev->DataR=maxVal;
					prev->Rch=NULL;
					done=true;
				}
			}//end if parent a 3node
		}//end if curr a 3node
	}//end of found
	else
		cout<<"\nCannot be added\n";

	return done;
}