KD Tree - Searching in N-dimensions, Part I

#ifndef __BINARY_TREE_H__
#define __BINARY_TREE_H__

////////////////////////////////////////////////////////////////////////////////////////////////////////
// Author       A.Milev 
// Email        amil@abv.bg

//  Implementation of binary tree
//  to use it nclude this header to your project 
////////////////////////////////////////////////////////////////////////////////////////////////////////

//if you work with negative numbers should change it:
#define INVALID_VALUE -1  

//Binary Tree Node
template <class Xtype>
class BTNode
{
public:
	BTNode();
	BTNode(Xtype x);
	bool Delete_Tree(BTNode<Xtype>* Root);
	BTNode(BTNode<Xtype>* k1, BTNode<Xtype>* k2);
	BTNode<Xtype> *Left, *Right, *Parent;
	BTNode<Xtype>* place(BTNode<Xtype>* T);
	BTNode<Xtype>* insert( Xtype x, bool& root_changed, bool optimize = true);
	bool insert( BTNode<Xtype>* node, bool& root_changed, bool optimize = true );
	void remove();
	int count_childs();
	bool  moveup();
	Xtype x;
	bool ParentOrientation ; //where is child WRT parent ? 0=left 1=right
	//////////////////////////////////////////////////////////////////////////
};


//	int  get_height(int& h, int& S);

template <class Xtype>
bool  BTNode<Xtype>::moveup() ///used to optimize insert
{
	if(Parent)
	{
		BTNode<Xtype>* GrandPa = Parent->Parent ;
		if(GrandPa)
		{
			BTNode<Xtype>* EmptyNode = ParentOrientation ? 
				GrandPa->Right : GrandPa->Left ;
;

			/*
					  G                   N
					 /                   / \
					P         ->        P   G
					 \
					   N

			*/
			if(!EmptyNode) //if there is a hole here
			{
				//set new left and right links
				if(ParentOrientation)
				{Left = Parent ; Right = GrandPa; Parent->Right = NULL; GrandPa->Left = NULL;}
				else
				{Right = Parent; Left = GrandPa ; Parent->Left = NULL; GrandPa->Right = NULL;}

				//change parent links
				Parent->ParentOrientation = !ParentOrientation ;
				Parent->Parent = this ;

				//change grand-pa links
				ParentOrientation = GrandPa->ParentOrientation ;
				GrandPa->ParentOrientation = ! Parent->ParentOrientation ;

				//set new parent
				Parent = GrandPa->Parent ; 

				//set links to the new parent
				if(GrandPa->Parent)
				{				
					ParentOrientation ? 
						GrandPa->Parent->Right = this : GrandPa->Parent->Left = this;
				}


				GrandPa->Parent = this ;

				if(Parent == NULL) //this is the new tree root
					return true ;
				
				return false ;
			}
			

			EmptyNode = ParentOrientation ? 
			Parent->Left : Parent->Right ;

			if(!EmptyNode)
			{				
				EmptyNode = ParentOrientation ? 
				GrandPa->Left : GrandPa->Right ;
			}

			/*
					  G                   P
					 /                   / \
					P         ->        N   G
				  / 
				 N	   

			*/

			if(!EmptyNode )
			{
				//set new left and right links
				if(ParentOrientation)
				{Parent->Left = GrandPa; GrandPa->Right = NULL;}
				else
				{Parent->Right = GrandPa; GrandPa->Left = NULL;}
				
				//set links to the new parent
				if(GrandPa->Parent)
				{				
					GrandPa->ParentOrientation ? 
						GrandPa->Parent->Right = Parent : GrandPa->Parent->Left = Parent;
				}

				Parent->Parent = GrandPa->Parent ;

				GrandPa->Parent = Parent ;
				GrandPa->ParentOrientation = !ParentOrientation ;

				if(Parent->Parent == NULL) //this is the new tree root
					return true ;
				
				return false ;
			}
		}
	}

	return false ; //return != 0 only if root had changed!
}

// constructors
template <class Xtype>
BTNode<Xtype>::BTNode()
{
	Left = NULL;
	Right = NULL;
	Parent = NULL;
	ParentOrientation = 0;
}

template <class Xtype>
BTNode<Xtype>::BTNode(BTNode<Xtype>* k1, BTNode<Xtype>* k2)
{
	Left = k1;
	Right = k2;
	Parent = NULL;
	ParentOrientation = 0;
}

template <class Xtype>
BTNode<Xtype>::BTNode(Xtype xKey)
{
	Left = NULL;
	Right = NULL;
	Parent = NULL;
	x = xKey;
	ParentOrientation = 0;
}

//places x to left or right of the node
template <class Xtype>
BTNode<Xtype>* BTNode<Xtype>::place (BTNode<Xtype>* x)
{
	if(x < xKey)
		return Left;
	else
		return Right;
}

template <class Xtype>
void BTNode<Xtype>::remove()
{
	BTNode<Xtype>* pLeft = Left;
	BTNode<Xtype>* pRight = Right;
	delete this;
	if(pLeft) pLeft->remove();
	if(pRight)pRight->remove();
}

template <class Xtype>
int BTNode<Xtype>::count_childs()
{
	int nChilds = 1;
	if(Left) nChilds+= Left->count_childs();
	if(Right) nChilds+= Right->count_childs() ;
	return nChilds ;
}

/*
template <class Xtype>
int  BTNode<Xtype>::get_height(int& h, int& S)
{
//	h++ ;
//	S+= h ;
	h = 0;
	BTNode<Xtype>* pNext = this;
	while(pNext)
	{
		pNext = pNext->Parent ;
		h++ ;
	}

	S+= h ;

	if(Left)   Left->get_height(h,S);
	if(Right)  Right->get_height(h, S);
	
//	h-- ;
	return h ;
}

*/

//delete from memory the whole tree
template <class Xtype>
bool Delete_Tree(BTNode<Xtype>* &Root)
{
	if(Root)
		Root->remove();
	Root = NULL;
	return true;
}

//insert node to the tree, starts from current node
template <class Xtype>
bool
BTNode<Xtype>::insert( BTNode<Xtype>* node, bool& root_changed, bool optimize )
{
	BTNode<Xtype>* pNext = this;
	BTNode<Xtype>* pFather;
	while(pNext) //do not insert if already exist
	{
		pFather = pNext;
		if(node->x < pNext->x)
			pNext = pNext->Left;
		else if(node->x > pNext->x)
			pNext = pNext->Right;
		else 
			return false;
	}

	if(!pNext) //empty place, do not insert value twice
	{
		node->Parent = pFather;
		if(node->x < pFather->x)
		{
			pFather->Left = node;
			node->ParentOrientation = 0 ;
		}
		else
		{
			pFather->Right = node;
			node->ParentOrientation = 1;
		}

		if(optimize)
			root_changed = node->moveup();
		else 
			root_changed = false ;

		return true;
	}
	return false;
}

//create and insert node to the tree, starts from current node
template <class Xtype>
BTNode<Xtype>*
BTNode<Xtype>::insert( Xtype x, bool& root_changed, bool optimize)
{
	BTNode<Xtype>* node = new BTNode<Xtype>(x);
	if(!insert(node, root_changed, optimize))
	{
		delete node;
		return NULL;
	}
	else
		return node;
}


template <class Xtype>
BTNode<Xtype>* get_father(BTNode<Xtype>* Root, Xtype x,  int& path_length) 
{
	BTNode<Xtype>* pNext = Root;
	BTNode<Xtype>* pFather;
	path_length = 0;
	while(pNext)
	{
		pFather = pNext;
		if(x<pNext->x)
			pNext = pNext->Left;
		else if(x>pNext->x)
			pNext = pNext->Right;
		else 
			return pNext;

		path_length++ ;
	}

	return pFather ;
}

template <class Xtype>
float get_average_height(BTNode<Xtype>* Root, Xtype* Array, int nArrayLen)
{
	float TotPathLen = 0;
	int len ;
	for(int n=0; n<nArrayLen; n++)
	{
		get_father(Root, Array[n], len);
		TotPathLen+= len ;
	}

	return TotPathLen/nArrayLen ;
}




//add node to the tree
template <class Xtype>
BTNode<Xtype>* append(BTNode<Xtype>* &Root, Xtype X, bool& root_changed, bool optimize)
{
	if(!Root)
	{
		Root =	new BTNode<Xtype>(X);
		return Root;
	}
	else
	{
		return Root->insert(X, root_changed, optimize);
	}
}

//finds if exact match exist
template <class Xtype>
bool exist(BTNode<Xtype>* Root, Xtype x)
{
	BTNode<Xtype>* pNext = Root;
	BTNode<Xtype>* pFather;
	while(pNext)
	{
		pFather = pNext;
		if(x<pNext->x)
			pNext = pNext->Left;
		else if(x>pNext->x)
			pNext = pNext->Right;
		else 
			return 1;
	}

	return 0;
}

/*   nearest neighbour search
   input:
    Root - the root of the tree
	x - template type with search target value

   output:
    l - the left limiting value or INVALID_VALUE if there is no neighbour to left
	r - the right limiting value or INVALID_VALUE if there is no neighbour to right
    
   returns:  
      - the closest value to x
	  - INVALID_VALUE - empty tree 
*/
template <class Xtype>
Xtype FindNearest(BTNode<Xtype>* Root, Xtype x, Xtype* l, Xtype* r)
{
	Xtype left,right;
	BTNode<Xtype>* pNext = Root;
	BTNode<Xtype>* pFather;
	bool ParentOrientation ;
	while(pNext)
	{
		pFather = pNext;
		if(x<pNext->x)
		{
			pNext = pNext->Left;
			ParentOrientation = false; 
		}
		else if(x>pNext->x)
		{
			pNext = pNext->Right;
			ParentOrientation = true; 
		}
		else 
		{
			*l = pNext->x;
			*r = pNext->x;
			return pNext->x;
		}
	}

	if(!ParentOrientation)  //x < pFather->x
	{
		right = pFather->x;
		//go up in the tree	and search for the left limit
		pFather = pFather->Parent;
		while(pFather && !pFather->ParentOrientation)  //search parent to the left
			pFather = pFather->Parent;

		if(!pFather)
		{
			*l = INVALID_VALUE;  //no neighbour to the left
			*r = right;
			return right;
		}
		else
		{
			*l = pFather->x;
			*r = right;
			return (x-pFather->x < right-x ? pFather->x:right);
		}
	}

	else //x > pFather->x
	{
		left = pFather->x;
		// go up in the tree and search for the right limit
		pFather = pFather->Parent;
		while(pFather && pFather->ParentOrientation)  //search parent to the lright
			pFather = pFather->Parent;

		if(!pFather)
		{
			*l = left;  
			*r = INVALID_VALUE;   //no neighbour to the right
			return left;
		}
		else
		{
			*l = left;
			*r = pFather->x;
			return (x-left < pFather->x-x ? left:pFather->x);;
		}
	}

	return INVALID_VALUE;
}




#endif