18. 이진트리 -e. 이진탐색트리(Binary Search Tree)

이진탐색트리(Binary Search Tree)

  # 이진 탐색 트리란 이진 트리 중 탐색을 위해서 고안된 것으로 다음과 같은 조건을 갖는다.

    1) 노드N에 대해서 N의 왼쪽 하위트리에 있는 노드는 N보다 작고, N의 오른쪽 하위트리에 있는 노드는 N보다 크다.

    2) 노드N에 대해서 N의 왼쪽 서브트리도, 오른쪽 서브트리도 이진 탐색트리이다.

  # 이진탐색트리는 정렬 기준에 대해 약하게 정렬되어 있다고 할 수 있다. 

  # 이를 이용해 완전히 정렬된 상태를 얻고 싶다면 이진탐색트리를 중위순회하면 된다.

  # 이진탐색트리는 최악의 경우 탐색, 삽입, 삭제 작업에 대해서 N의 효율을 보인다. 

  # 이는 이진탐색트리의 최악의 경우는 데이터가 한쪽 방향으로만 쏠려 연결리스트와 같은 모습이 되기 떄문이다.

  # 하지만 평균적인 경우 이진탐색트리의 탐색, 삽입, 삭제 작업은 LogN에 가까운 효율을 유지한다.

  # 힙과 우선순위 큐를 소개하기 전에 이진탐색트리를 먼저 소개하는 이유는 우선순위 큐를 힙과 이진탐색트리 두가지로 구현가능하기 때문이다.

     (물론, 배열이나 연결리스트도 가능하긴 하지만 효율이 너무 떨어지니 고려하지 않음.)

  # 배열 기반의 힙으로 우선순위 큐를 구현할 경우 효율은 좋지만 큐의 크기가 고정된다는 단점이 있다.

  # 이진탐색트리를 기반으로 우선순위 큐를 구현할 경우 효율은 조금 떨어지지만 큐의 크기 고정되지 않는다는 장점이 있다.

  # 이진탐색트리의 구현을 우선하기 위해서 데이터형을 int로 한정했다.

  # 이를 노드가 임의의 데이터를 갖게 하고 임의의 테이터의 대소 비교의 기준이 되는 함수를 지정하는 형태로 확장할 수도 있을 것이다.

C++로 구현한 이진탐색트리

#pragma once
//일단 이진탐색트리에 구현에 집중하기 위해서 데이터형을 정수로 고정.

struct node
{
	int data;
	node* left;
	node* right;
};

void preorder(node* node, void(*action)(int))
{
	if (node != nullptr) {
		action(node->data);
		preorder(node->left, action);
		preorder(node->right, action);
	}
}

void inorder(node* node, void(*action)(int))
{
	if (node != nullptr) {
		inorder(node->left, action);
		action(node->data);
		inorder(node->right, action);
	}
}

void postorder(node* node, void(*action)(int))
{
	if (node != nullptr) {
		postorder(node->left, action);
		postorder(node->right, action);
		action(node->data);
	}
}

class BinarySearchTree
{
public:
	node* TreePointer;

private:
	node* &RootNode = TreePointer;

private:
	node* MakeNode(int data);
	node* Search(node* nptr, int key);
	node* delSearch(node* nptr, int key);
	node* DeleteNode(node* nptr);

public:
	node* Search(int key);
	void AddNode(int data);
	void DeleteNode(int key);

public:
	BinarySearchTree();
	virtual	~BinarySearchTree();
};

//----------------------------->>

node* BinarySearchTree::MakeNode(int data)
{
	node* nn = new node;
	nn->data = data;
	nn->left = nullptr;
	nn->right = nullptr;

	return nn;
}

node* BinarySearchTree::Search(node* nptr, int key)
{
	if (nptr == nullptr) {
		return nullptr;
	}
	else if (nptr->data == key) {
		return nptr;
	}
	else if (nptr->data > key) {
		return Search(nptr->left, key);
	}
	else {
		return Search(nptr->right, key);
	}
}

node* BinarySearchTree::delSearch(node* nptr, int key)
{
	if (nptr == nullptr) {
		return nullptr;
	}

	else if (nptr->data > key) {
		if (nptr->left->data == key) {
			return nptr;
		}
		else {
			return delSearch(nptr->left, key);
		}
	}
	else if (nptr->data < key) {
		if (nptr->right->data == key) {
			return nptr;
		}
		else {
			return delSearch(nptr->right, key);
		}
	}
	else if (nptr->data == key) {
		return nptr;
	}
}

node* BinarySearchTree::DeleteNode(node* nptr)
{
	node* ret;
	if (nptr->left == nullptr && nptr->right == nullptr) {
		ret = nullptr;
	}
	else if (nptr->left != nullptr &&nptr->right == nullptr) {
		ret = nptr->left;		
	}
	else if (nptr->left == nullptr && nptr->right != nullptr) {
		ret = nptr->right;
	}
	else {
		ret = nptr;
		node* prev = nullptr;
		while (nptr->right != nullptr) {
			nptr->data = nptr->right->data;
			prev = nptr;
			nptr = nptr->right;
		}
		prev->right = nullptr;
	}

	delete nptr;
	return ret;
}

//----------------------------->>



BinarySearchTree::BinarySearchTree()
{
	TreePointer = nullptr;
}

node* BinarySearchTree::Search(int key)
{
	return Search(RootNode, key);
}

void BinarySearchTree::AddNode(int data)
{
	node* nptr = nullptr;

	if (RootNode == nullptr) {
		RootNode = MakeNode(data);
	}
	else {
		nptr = RootNode;
		node* nNode = MakeNode(data);

		while (true) {
			if (nNode->data < nptr->data) {
				if (nptr->left != nullptr) {
					nptr = nptr->left;
				}
				else {
					nptr->left = nNode;
					break;
				}
			}
			else if(nNode->data > nptr->data) {
				if (nptr->right != nullptr) {
					nptr = nptr->right;
				}
				else {
					nptr->right = nNode;
					break;
				}
			}
			else {
				if (nptr->left == nullptr) {
					nptr->left = nNode;
					break;
				}
				else if (nptr->right == nullptr) {
					nptr->right = nNode;
					break;
				}
				else {
					nptr = nptr->left;
				}
			}
		}
	}
}

void BinarySearchTree::DeleteNode(int key)
{
	node* sNode = delSearch(RootNode, key);

	if (sNode == RootNode) {
		DeleteNode(sNode);
	}
	else if(sNode->left != nullptr && sNode->left->data == key) {
		sNode->left = DeleteNode(sNode->left);
	}
	else if (sNode->right != nullptr && sNode->right->data == key) {
		sNode->right = DeleteNode(sNode->right);
	}
}

BinarySearchTree::~BinarySearchTree()
{

}