avl.h

独立于AVL库的存储媒体 虽现在有不少可用的AVL树库

{
	hndNode b, br;
	bool (hndNode::*pfnStepLeft)();
	bool (hndNode::*pfnStepRight)();	
	void (hndNode::*pfnSetLeftChildNull)();
	void (AVL<hndNode>::*pfnConnectRight)(hndNode&,hndNode&);
	void (AVL<hndNode>::*pfnConnectLeft)(hndNode&,hndNode&);

	
	if ( bInvert) {
	    pfnStepLeft = &hndNode::StepRight;
	    pfnStepRight = &hndNode::StepLeft;	    
	    pfnSetLeftChildNull = &hndNode::SetRightChildNull;
	    pfnConnectRight = &AVL<hndNode>::Connect_Left;
	    pfnConnectLeft  = &AVL<hndNode>::Connect_Right;
	}
	else {
		pfnStepLeft = &hndNode::StepLeft;
	    pfnStepRight = &hndNode::StepRight;	    		
	    pfnSetLeftChildNull = &hndNode::SetLeftChildNull;	    
	    pfnConnectRight = &AVL<hndNode>::Connect_Right;
	    pfnConnectLeft  = &AVL<hndNode>::Connect_Left;	    
	}
	
		
	b.SetToNode(nhndNode);
	verify( (b.*pfnStepLeft)() );
	br.SetToNode(b);


	if ( (br.*pfnStepRight)() ) {
	   	(this->*pfnConnectLeft)(nhndNode,br);	   	
	}
	else {
		(nhndNode.*pfnSetLeftChildNull)();
	}

	(this->*pfnConnectRight)(b,nhndNode);	

	b.SetBalanceFactor(0);
	nhndNode.SetBalanceFactor(0);
	
	if ( pnhndParent) {
	   	if ( bLocation) {	//in the right branch
			Connect_Right(*pnhndParent, b);
		}
		else {				//in the left branch
		 	Connect_Left(*pnhndParent, b);  
		}
	}
	else {
		m_pRoot->SetToNode(b);
		m_pRoot->SetParentNull();
	}


	if ( bInvert)
		m_ndgRRCount++;
	else
		m_ndgLLCount++;

}


template<class hndNode>
void AVL<hndNode>::LR(hndNode& nhndNode, hndNode* pnhndParent, bool bLocation, bool bInvert)
{

	hndNode b, c, tmp;
	bool (hndNode::*pfnStepLeft)();
	bool (hndNode::*pfnStepRight)();	
	void (AVL<hndNode>::*pfnConnectRight)(hndNode&,hndNode&);
	void (AVL<hndNode>::*pfnConnectLeft)(hndNode&,hndNode&);
	int k;
	
	if ( bInvert) {
	    pfnStepLeft = &hndNode::StepRight;
	    pfnStepRight = &hndNode::StepLeft;	    
	    pfnConnectRight = &AVL<hndNode>::Connect_Left;
	    pfnConnectLeft  = &AVL<hndNode>::Connect_Right;
	}
	else {
		pfnStepLeft = &hndNode::StepLeft;
	    pfnStepRight = &hndNode::StepRight;	    		
	    pfnConnectRight = &AVL<hndNode>::Connect_Right;
	    pfnConnectLeft  = &AVL<hndNode>::Connect_Left;	    
	}
	   

	verify ( b.SetToNode(nhndNode) );
	verify ( (b.*pfnStepLeft)() );
	verify ( c.SetToNode(b) );
	verify ( (c.*pfnStepRight)() );
	
	verify ( tmp.SetToNode(c) );
	
	if ( tmp.StepLeft() ) {
 	  	if ( bInvert) 
  	 		Connect_Right(nhndNode, tmp);
   		else
   			Connect_Right(b, tmp);
	}
	else {
 	  	if ( bInvert)
  	 		nhndNode.SetRightChildNull();
   		else
   			b.SetRightChildNull();
	}	
	
	verify ( tmp.SetToNode(c) );
	
	if ( tmp.StepRight() ) {
 	  	if ( bInvert) 
  	 		Connect_Left(b, tmp);
   		else
   			Connect_Left(nhndNode, tmp);	   
	}
	else {
 	  	if ( bInvert)
  	 		b.SetLeftChildNull();
   		else
   			nhndNode.SetLeftChildNull();	   
	}
	

	(this->*pfnConnectLeft)(c,b);
	(this->*pfnConnectRight)(c,nhndNode);
	
	k = c.GetBalanceFactor();
	
	if ( k ) {
		if ( bInvert) {
		   	if ( k == -1 ) {
	 	  	   	nhndNode.SetBalanceFactor(0);
	 	  	   	b.SetBalanceFactor(1);			 			  	   	
	 		}
	 		else {
		 	   	nhndNode.SetBalanceFactor(-1);
		 	   	b.SetBalanceFactor(0);	 		   
		 	}
		}
		else {
		   	if ( k == -1 ) {
	 	  	   	b.SetBalanceFactor(0);
	 	  	   	nhndNode.SetBalanceFactor(1);	
	 		}
		 	else {
		 	   	b.SetBalanceFactor(-1);
		 	   	nhndNode.SetBalanceFactor(0);
		 	}
 
		}
	}
	else {
	   	b.SetBalanceFactor(0);
	   	nhndNode.SetBalanceFactor(0);
	}
	
	c.SetBalanceFactor(0);
	
	
	if ( pnhndParent) {
	   	if ( bLocation) {	// in right branch
	   		Connect_Right(*pnhndParent, c);
	   	}
		else {				// in left branch
			Connect_Left(*pnhndParent, c);
		}
	}
	else {
		verify ( m_pRoot->SetToNode(c) );
		m_pRoot->SetParentNull();
	}
	


	if ( bInvert)
		m_ndgRLCount++;
	else
		m_ndgLRCount++;
	
	
}

template<class hndNode>
bool AVL<hndNode>::Insert( hndNode& nhndInsert, SearchResult* pSR, hndNode* pnhndDup, bool bReplace)
{
   	hndNode nodeImb;
   	hndNode nodeParent;
   	hndNode nodeTmp;
   	int k, idxImb, idxEnd;

	SetLastError();

   	nhndInsert.SetBalanceFactor(0);	   	   	
   	nhndInsert.SetLeftChildNull();
   	nhndInsert.SetRightChildNull();
   	
   	if ( !m_pRoot) {
		m_pRoot = new hndNode();

		if ( m_pRoot->SetToNode(nhndInsert) ) {
			
			m_pRoot->SetParentNull();
			
#ifdef ___AVL_LINKLIST_SUPPORT___			
			InsertToList(NULL, *m_pRoot, NULL);
#endif		
	   
		   	m_nHeight = 1;
	
			m_nNodeNumber++;		
		   	ReAllocSearchPath();
	   		
	   	   	return true;
		}	   
	 	
	 	return false;
   	}
   	

	if ( pSR) {	//retrieve from SearchResult structure if pSB is available.	
		verify( nodeParent.SetToNode(pSR->nhndSearch) );
		idxImb = pSR->nImbalanceIdx;
		verify( nodeImb.SetToNode(pSR->nhndImbalance) );
		idxEnd = pSR->nEndIdx;
	}
	else
   		verify ( nodeParent.SetToNode(nhndInsert) );
   	

	if ( (pSR && !pSR->bFound ) || !Search(nodeParent, &idxImb, &nodeImb, &idxEnd) ) {	//new node
	   	
	
		//start to insert
		k = nhndInsert.Compare(nodeParent);
	   	
	   	if ( k == 1) {
	   	   	Connect_Right(nodeParent, nhndInsert);
	 	}
	 	else {
			Connect_Left(nodeParent, nhndInsert);
		}
#ifdef ___AVL_LINKLIST_SUPPORT___			
		verify( nodeTmp.SetToNode(nodeParent) );
	   	if ( m_bSearchPath[idxEnd] ) {	//parent is at left
			if ( nodeTmp.StepToRightSibling() )
				InsertToList(&nodeParent, nhndInsert, &nodeTmp);
			else
				InsertToList(&nodeParent, nhndInsert, NULL);				
		}
		else {							//parent is at right
		 	if ( nodeTmp.StepToLeftSibling() )
		 		InsertToList(&nodeTmp, nhndInsert, &nodeParent);
		 	else
		 		InsertToList(NULL, nhndInsert, &nodeParent); 
	 	}
#endif

//
//		Rebalance the tree if necessary
//
//


		//Adjust balance factor
		verify( nodeTmp.SetToNode(nodeParent) );		   
		for ( k = idxEnd; k > idxImb; k--) {
			if ( m_bSearchPath[k] )
				nodeTmp.SetBalanceFactor(1);
			else
				nodeTmp.SetBalanceFactor(-1);

			nodeTmp.StepUp();
		}


		if ( idxImb >= 0 ) {	//need rebalance
			k = nodeImb.GetBalanceFactor();
			if ( (m_bSearchPath[idxImb] && k == 1) ||
				 (!m_bSearchPath[idxImb] && k == -1) ) {
					
				nodeTmp.StepUp();
			
				if ( m_bSearchPath[idxImb] ) {
				   	if ( m_bSearchPath[idxImb+1] ) {	//RR
						if ( idxImb)
							LL(nodeImb,&nodeTmp, m_bSearchPath[idxImb-1], true);
						else								
							LL(nodeImb,NULL,false,true);
				 	}
				 	else {								//RL
						if ( idxImb)
							LR(nodeImb,&nodeTmp, m_bSearchPath[idxImb-1], true);
						else								
							LR(nodeImb,NULL,false,true);			 		
			 		}
				}
				else {
				   	if ( m_bSearchPath[idxImb+1] ) {	//LR
						if ( idxImb)
							LR(nodeImb,&nodeTmp, m_bSearchPath[idxImb-1], false);
						else								
							LR(nodeImb,NULL,false,false);			   	   
				 	}
				 	else {								//LL
						if ( idxImb)
							LL(nodeImb,&nodeTmp, m_bSearchPath[idxImb-1], false);
						else								
							LL(nodeImb,NULL,false,false);
			 	
			 		}
		   
				}
			}
			else {
			   	nodeImb.SetBalanceFactor(0);
			}
		}
		else {
		   if (  idxEnd+2 > m_nHeight) 
		      	m_nHeight = idxEnd+2;
		}

		m_nNodeNumber++;
	  	ReAllocSearchPath();		      
		
	   	return true;
	}
	else if (pnhndDup && bReplace) {	//a node with the same key already exists.
		
		verify( pnhndDup->SetToNode(nodeParent) );
		nhndInsert.SetBalanceFactor( nodeParent.GetBalanceFactor());

		nodeTmp.SetToNode(nodeParent);	
		//connect parent
		if ( nodeTmp.StepUp() ) {	
			if ( m_bSearchPath[idxEnd-1])
				Connect_Right(nodeTmp, nhndInsert);
			else
				Connect_Left(nodeTmp, nhndInsert);
		}
		else {
			nhndInsert.SetParentNull();
			verify( m_pRoot->SetToNode(nhndInsert) );
		}

		//connect childs
		nodeTmp.SetToNode(nodeParent);
		if ( nodeTmp.StepRight() )
			Connect_Right(nhndInsert, nodeTmp);
		else
			nhndInsert.SetRightChildNull();

		nodeTmp.SetToNode(nodeParent);
		if ( nodeTmp.StepLeft() )
			Connect_Left(nhndInsert, nodeTmp);
		else
			nhndInsert.SetLeftChildNull();

#ifdef ___AVL_LINKLIST_SUPPORT___		
		nodeTmp.SetToNode(nodeParent);
		
		if ( nodeParent.StepToLeftSibling() ) {	//connect list
			if ( nodeTmp.StepToRightSibling() ) 
				InsertToList(&nodeParent, nhndInsert, &nodeTmp);
			else 
				InsertToList(&nodeParent, nhndInsert, NULL);
		}
		else {
			if ( nodeTmp.StepToRightSibling() ) 
				InsertToList(NULL, nhndInsert, &nodeTmp);
			else 
				InsertToList(NULL, nhndInsert, NULL);
		}
#endif
		SetLastError(AVL_Errors::S_REPLACED);
		return true;
	}
	else { //collision occured. no replace is performed.
		
		SetLastError(AVL_Errors::E_KEYCOLLISION);

		if ( pnhndDup )	//no replace, just return the existing collision node
			verify( pnhndDup->SetToNode(nodeParent) );
		
	}

	return false;		   
}


template<class hndNode>
bool AVL<hndNode>::Delete( hndNode& nhndDelete, SearchResult* pSR)
{
	hndNode 	nodeTmp, nodeParent, nodeReplace;
	int			idxEnd, k, bf;

		
		
	if ( pSR ) {
		
		assert( !nhndDelete.Compare(pSR->nhndSearch) );

		if ( pSR->bFound) {
			verify( nodeTmp.SetToNode( pSR->nhndSearch) );
			idxEnd = pSR->nEndIdx;
		}
		else
			return false;
	}
	else {
		verify ( nodeTmp.SetToNode(nhndDelete) );	
		if( !Search(nodeTmp, NULL, NULL, &idxEnd) ) 
			return false;
	}

	SetLastError();

	verify( nhndDelete.SetToNode(nodeTmp) ); 
 	verify( nodeParent.SetToNode(nodeTmp) );
 	verify( nodeReplace.SetToNode(nodeTmp) );	

#ifdef ___AVL_LINKLIST_SUPPORT___		
	RemoveFromList(nodeTmp);
#endif
	
	
	if ( !nodeReplace.StepRight() ) {
		idxEnd--;	//set idx to the start-point for rebalancing
		if ( nodeParent.StepUp() ) {
			if ( m_bSearchPath[idxEnd] ) {
				if ( nodeReplace.StepLeft() )
					Connect_Right(nodeParent, nodeReplace);
				else
					nodeParent.SetRightChildNull();
			}
			else {
				if ( nodeReplace.StepLeft() ) 
					Connect_Left(nodeParent, nodeReplace);
				else
					nodeParent.SetLeftChildNull();
		    }
					
			nodeTmp.SetToNode(nodeParent);	//set to the start-point for 
											//rebalancing.
		
		}
		else {	//nhndDelete is exactly the 'root'
			if ( nodeReplace.StepLeft() ) {
				m_pRoot->SetToNode(nodeReplace);
				m_pRoot->SetParentNull();
			}
			else {
				delete m_pRoot;
				m_pRoot = NULL;
			}
		}	
	}
	else if (!nodeReplace.StepLeft()) {

		//set balance factor of nodeReplace
		nodeReplace.SetBalanceFactor(nodeTmp.GetBalanceFactor());
		m_bSearchPath[idxEnd] = true;		
	
		//connect
		if (nodeTmp.StepLeft() )
			Connect_Left ( nodeReplace, nodeTmp);
			
	
		if (nodeParent.StepUp() ) {
			if ( m_bSearchPath[idxEnd-1] ) 
				Connect_Right(nodeParent, nodeReplace);				
			else 
				Connect_Left(nodeParent, nodeReplace);
		}	
		else {	//nhndDelete is exactly the 'root'
			m_pRoot->SetToNode(nodeReplace);
			m_pRoot->SetParentNull();
		}	
		
		nodeTmp.SetToNode(nodeReplace);		
	}
	else {
		hndNode nodeTmp2;
		int old_idxEnd = idxEnd;
				
		m_bSearchPath[idxEnd] = true;
		m_bSearchPath[++idxEnd] = false;
		
		while(nodeReplace.StepLeft())
			m_bSearchPath[++idxEnd] = false;

		nodeReplace.SetBalanceFactor( nodeTmp.GetBalanceFactor());
		
		if(nodeTmp.StepLeft() ) {
			Connect_Left( nodeReplace, nodeTmp);
		}


		nodeTmp.SetToNode(nodeReplace);
		nodeTmp.StepUp();	//point to the start-point of rebalancing
				
		nodeTmp2.SetToNode(nodeReplace);		

		if ( nodeTmp2.StepRight() ) 
			Connect_Left(nodeTmp, nodeTmp2);
		else 
			nodeTmp.SetLeftChildNull();

		nodeTmp2.SetToNode(nodeParent);	//nodeParent still points to the 
										//nhndDelete for deletion
		verify( nodeTmp2.StepRight());
		Connect_Right(nodeReplace, nodeTmp2);
		
		
		if ( nodeParent.StepUp() ) {		
			if ( m_bSearchPath[old_idxEnd-1] ) 
				Connect_Right(nodeParent, nodeReplace);				
			else 
				Connect_Left(nodeParent, nodeReplace);			
		}
		else {	//nhndDelete is exactly the 'root'
			m_pRoot->SetToNode(nodeReplace);
			m_pRoot->SetParentNull();
		}
	}


	//rebalance
	if ( idxEnd >= 0) {
		

		for ( k = idxEnd; k >= 0; k--) {

			bf = nodeTmp.GetBalanceFactor();
			
			if ( !bf) {
				nodeTmp.SetBalanceFactor((m_bSearchPath[k] ? -1:1) );
				break;					
			}
			else if ( (bf == 1 && !m_bSearchPath[k])  ) {
				nodeReplace.SetToNode(nodeTmp);
				verify(nodeReplace.StepRight());
				nodeParent.SetToNode(nodeTmp);

				
				bf = nodeReplace.GetBalanceFactor();
				if( bf == 1 ) {	//RR
					if ( nodeParent.StepUp() )
						LL(nodeTmp, &nodeParent, m_bSearchPath[k-1], true);
					else
						LL(nodeTmp, NULL,false, true);
				}
				else if ( bf == -1) { //RL
					if ( nodeParent.StepUp() )
						LR(nodeTmp, &nodeParent, m_bSearchPath[k-1], true);
					else
						LR(nodeTmp, NULL,false,true);
				}
				else {
					if ( nodeParent.StepUp() )
						LL(nodeTmp, &nodeParent, m_bSearchPath[k-1], true);
					else
						LL(nodeTmp, NULL,false, true);
					
					nodeTmp.SetBalanceFactor(1);
					nodeReplace.SetBalanceFactor(-1);
					break;
				}
						
				nodeTmp.SetToNode(nodeParent);
			}
			else if ( (bf == -1 && m_bSearchPath[k])  ) {

				nodeReplace.SetToNode(nodeTmp);
				verify( nodeReplace.StepLeft() );
				nodeParent.SetToNode(nodeTmp);

				
				bf = nodeReplace.GetBalanceFactor();
				if( bf == -1 ) {	//LL
					if ( nodeParent.StepUp() )
						LL(nodeTmp, &nodeParent, m_bSearchPath[k-1], false);
					else
						LL(nodeTmp, NULL,false, false);
				}
				else if ( bf == 1) { //LR
					if ( nodeParent.StepUp() )
						LR(nodeTmp, &nodeParent, m_bSearchPath[k-1], false);
					else
						LR(nodeTmp, NULL,false,false);
				}
				else {
					if ( nodeParent.StepUp() )
						LL(nodeTmp, &nodeParent, m_bSearchPath[k-1], false);
					else
						LL(nodeTmp, NULL,false, false);
					
					nodeTmp.SetBalanceFactor(-1);
					nodeReplace.SetBalanceFactor(1);
					break;
				}
						
				nodeTmp.SetToNode(nodeParent);
			}
			else {
				nodeTmp.SetBalanceFactor(0);
				nodeTmp.StepUp();
			}
		
		}
		
		idxEnd = k;		
	}
	
	if ( idxEnd == -1) {
		m_nHeight--;
		
		assert(m_nHeight >= 0);
	}

	m_nNodeNumber--;
	ReAllocSearchPath();	

	return true;


}

#endif