#include <iostream>
#include <string>
#include "BinaryTree.cpp"
#include "TreeTraversal.cpp"
using namespace std;

#ifndef BINARYSEARCHTREE_CLASS_INCLUDED
#define BINARYSEARCHTREE_CLASS_INCLUDED

/*
	Binary Search Tree Class (BinaryTree)
	LastModification : 2008. 5. 15
	Version : 1.1.0
	myllyj(myllyj at myllyj dot com) / http://program.myllyj.com

*/

template <class T>
class BinarySearchTree
{
protected:
	BinaryTree<T>* rootTree;
	BinaryTree<T>* nowTree;
	int leftDepth;
	int rightDepth;
	BinaryTree<T>* GetReplaceNode();

public:
	bool Insert(T data);
	bool Remove(T data);
	bool Find(T data);
	void PrintInOrder();
	void Print(BinaryTree<T>* tree, int level);
	int GetDepth();

};

// ÇØ´ç µ¥ÀÌÅ͸¦ BST¿¡ Ãß°¡ ÇÕ´Ï´Ù.
template <class T>
bool BinarySearchTree<T>::Insert(T data)
{
	if (this->rootTree == NULL)
	{
		this->rootTree = new BinaryTree<T>(data);
		this->nowTree = this->rootTree;
		return true;
	}

	// µ¥ÀÌÅÍ ÀÖÀ¸¸é Ãß°¡ ¾ÈÇØ.
	if (this->Find(data)) return false;

	if (this->nowTree->GetData() > data)
	{
		this->nowTree->SetLeftChild(data);
		this->nowTree = this->nowTree->GetLeftChild();
	}
	else
	{
		this->nowTree->SetRightChild(data);
		this->nowTree->GetRightChild();
	}
	
	return true;

}

// ÇØ´ç µ¥ÀÌÅ͸¦ °¡Áø ³ëµå¸¦ Á¦°Å ÇÕ´Ï´Ù.
template <class T>
bool BinarySearchTree<T>::Remove(T data)
{
	if (!this->Find(data)) return false;

	if (this->nowTree==this->rootTree)
	{
		// root¸¸ ´Þ¶û ÀÖÀ» ¶§
		if (this->rootTree->CountChild()==0)
		{
			delete this->rootTree;
			this->rootTree = NULL;
			return true;
		}

		// 1°³À϶§
		if (this->rootTree->CountChild()==1)
		{
			// ¿ÞÂÊÀ̳ª ¿À¸¥ÂÊ¿¡ Àִ°ÍÀ̸é
			// ±×³É ±×³ðÀ» root·Î ¿Ã·Á ÁÖ¸é µÈ´Ù.
			if (this->rootTree->GetLeftChild()!=NULL)
			{
				this->rootTree = this->rootTree->GetLeftChild();
			}
			else
			{
				this->rootTree = this->rootTree->GetRightChild();
			}

			//delete this->rootTree->GetParent();
			this->rootTree->SetParent(NULL);

			return true;
		}

	}

	if (nowTree->CountChild()==0)
	{
		// root Tree´Â ¾Æ´Ï¶ó°í °¡Á¤.
		// ÇöÀç ¼±ÅõÈ, Áï Áö¿ì·Á´Â ³ëµå°¡ Â÷Àϵ尡 ¾ø´Ù.
		// »èÁ¦ÇÏ°í parent¿Í ¿¬°áÀ» ²÷¾îÁÖ¸é µÈ´Ù.

		BinaryTree<T>* parent = nowTree->GetParent();
		if (parent->GetLeftChild()==nowTree) parent->RemoveLeftChild();
		if (parent->GetRightChild()==nowTree) parent->RemoveRightChild();

		return true;
	}

	if (nowTree->CountChild()==1)
	{

		// root Tree´Â ¾Æ´Ï¶ó°í °¡Á¤.
		// ÇöÀç ¼±ÅõÈ, Áö¿ì·Á´Â ³ëµå´Â 1°³ÀÇ child¸¦ ¼ÒÀ¯.
		// Áö¿ì·Á´Â ³ëµåÀÇ parent¿¡ Áö¿ì·Á´Â ³ëµåÀÇ child¸¦ ¿¬°á.
		BinaryTree<T>* child;
		BinaryTree<T>* parent = nowTree->GetParent();

		// child ±¸Çϱâ.
		if (nowTree->GetLeftChild()!=NULL)
		{
			child = nowTree->GetLeftChild();
		}
		else
		{
			child = nowTree->GetRightChild();
		}

		// parent ¼³Á¤Çϱâ.
		if (parent->GetLeftChild()==nowTree)
		{
			parent->SetLeftChild(child);
		}
		else
		{
			parent->SetRightChild(child);
		}
		child->SetParent(parent);

		delete nowTree;

		return true;
	
	}

	if (nowTree->CountChild()==2)
	{
		// ÇöÀç Áö¿ö¾ß ÇÏ´Â ³ëµå ¹é¾÷
		BinaryTree<T>* nowNode = this->nowTree;

		// ±íÀÌ ÃøÁ¤Çϸ鼭 ¹Ù²ãÄ¡±â ÇÒ ³ëµå ¾îµð ÀÖ³ª È®ÀÎ
		BinaryTree<T>* highestNode = this->GetReplaceNode();
		T highestData = highestNode->GetData();

		// ÇöÀç ³ëµå¸¦ »èÁ¦ ÇÒ ±Ã¸® ÇÏÀÚ.
		// ¹Ù²ãÄ¡±â ÇÒ ³ëµå´Â child1°³ ¾Æ´Ï¸é 0°³.
		// »èÁ¦ Çѹø ´õ call
		this->Remove(highestData);
		nowNode->SetData(highestData);

		return true;
	}

	return false;

}


// ÇØ´ç µ¥ÀÌÅ͸¦ °¡Áö´Â ¿ø¼Ò¸¦ ã½À´Ï´Ù. ãÀº ³ëµå´Â ÇöÀç ÀÛ¾÷³ëµå·Î ¼³Á¤µË´Ï´Ù.
template <class T>
bool BinarySearchTree<T>::Find(T data)
{
	this->nowTree = this->rootTree;

	while (nowTree!=NULL)
	{
		if (nowTree->GetData() == data) return true;
		if (nowTree->GetData() > data)
		{
			if (nowTree->GetLeftChild()==NULL) return false;
			this->nowTree = this->nowTree->GetLeftChild();
		}
		else
		{
			if (nowTree->GetRightChild()==NULL) return false;
			this->nowTree = this->nowTree->GetRightChild();
		}
	}

	return false;

}

// ÀÌ BSTÆ®¸®¸¦ InOrder¹æ½ÄÀ¸·Î Traversal ÇÑ °á°ú¸¦ Ãâ·ÂÇÕ´Ï´Ù.
template <class T>
void BinarySearchTree<T>::PrintInOrder()
{
	TreeTraversal<T>* bt = new TreeTraversal<T>();
	bt->InOrder(this->rootTree);

	cout << " ";
}

// ÀÌ BSTÆ®¸®¸¦ ·¹º§¿¡ ¸ÂÃß¾î Ãâ·ÂÇÕ´Ï´Ù.
template <class T>
void BinarySearchTree<T>::Print(BinaryTree<T>* tree, int level)
{
	if (tree==NULL) return;

	int margin = 3;

	this->Print(tree->GetLeftChild(), level+1);
	for (int i=0; i<margin * level; i++) cout << " ";
	cout << tree->GetData() << endl;
	this->Print(tree->GetRightChild(), level+1);

	return;
}

// ÀÌ BSTÀÇ ±íÀ̸¦ ±¸ÇÕ´Ï´Ù.
template <class T>
int BinarySearchTree<T>::GetDepth()
{
	return this->rootTree->GetDepth();
}

template <class T>
BinaryTree<T>* BinarySearchTree<T>::GetReplaceNode()
{
	BinaryTree<T>* left = this->nowTree->GetLeftChild();
	BinaryTree<T>* right = this->nowTree->GetRightChild();
	BinaryTree<T>* result;
	BinaryTree<T>* tmpNode;

	this->leftDepth = 0;
	this->rightDepth = 0;
	
	// ¿ÞÂÊ °Ë»ç
	while(left!=NULL)
	{
		tmpNode = left;
		left = left->GetRightChild();
		this->leftDepth++;
	}

	// ¿À¸¥ÂÊ °Ë»ç
	while(right!=NULL)
	{
		right = right->GetLeftChild();
		this->rightDepth++;
	}

	// ¾î¶²³ðÀ» °ñ¶ó¾ß ÇÏ´ÂÁö »ÌÀÚ.
	if (this->leftDepth >= this->rightDepth)
	{
		// ¿ÞÂʳ𿡼­ °¡Àå ¿À¸¥ÂÊ¿¡ ÀÖ´Â °Í »Ì±â.
		result = nowTree->GetLeftChild();
		while(result!=NULL)
		{
			if (result->GetRightChild()==NULL) break;
			result = result->GetRightChild();
		}
	}
	else
	{
		// ¿À¸¥Âʳ𿡼­ °¡Àå ¿ÞÂÊ¿¡ ÀÖ´Â °Í »Ì±â.
		result = nowTree->GetRightChild();
		while(result!=NULL)
		{
			if (result->GetLeftChild()==NULL) break;
			result = result->GetLeftChild();
		}
	}

	return result;

}

#endif