[알고리즘] 이진 탐색 트리 (Binary Search Tree)

이진 탐색 트리는 부모 노드가 자식 노드보다 크다는 점은 힙 트리와 같다.

하지만 부모노드 기준 왼쪽 자식은 부모보다 작은 값, 오른쪽 자식은 부모보다 큰 값이어야 한다.

그래서 값을 찾을 때 한단계 내려갈 때마다 데이터 절반에 해당하는 서브트리를 제외할 수 있어서

log n의 시간 복잡도를 가지는 장점이 있다.

 

 

void BinarySearchTree::Print_Inorder(Node* node)
{
	// 전위 순회 (preorder traverse)
	// 중위 순회 (inorder)
	// 후위 순회 (postorder)
	if (node == nullptr)
		return;

	// 전위 : [중]이 앞에 온다
	// 중위 : [중]이 중간에 온다
	// 후위 : [중]이 마지막에 온다	
	cout << node->key << endl;
	Print_Inorder(node->left);	
	Print_Inorder(node->right);	
}

 

먼저 이진 탐색 트리의 순회 방법에는 세가지가 있는데, 부모 노드의 위치에 따라 전위, 중위, 후위로 갈린다.

 

void BinarySearchTree::Insert(int key)
{
	Node* newNode = new Node();
	newNode->key = key;

	if (_root == nullptr)
	{
		_root = newNode;
		return;
	}

	Node* node = _root;
	Node* parent = nullptr;

	while (node)
	{
		parent = node;
		if (key < node->key)
			node = node->left;
		else
			node = node->right;
	}

	newNode->parent = parent;

	if (key < parent->key)
		parent->left = newNode;
	else
		parent->right = newNode;
}

 

삽입할 때는 아무것도 없을 때 root에 집어넣고,  root 노드가 있으면 while 루프를 돌며 값을 비교해 left 또는 right으로 이동한다. 그리고 부모를 설정한다.

 

Node* BinarySearchTree::Search(Node* node, int key)
{
	if (node == nullptr || key == node->key)
		return node;

	if (key < node->key)
		return Search(node->left, key);
	else
		return Search(node->right, key);
}

 

탐색 방법은 단순하다. 현재 노드와 값을 비교해 더 작으면 left로 가서 재귀, 크면 right에서 재귀를 사용한다.

 

Node* BinarySearchTree::Min(Node* node)
{
	while (node->left)
		node = node->left;

	return node;
}

Node* BinarySearchTree::Max(Node* node)
{
	while (node->right)
		node = node->right;

	return node;
}

Node* BinarySearchTree::Next(Node* node)
{
	if (node->right)
		return Min(node->right);

	Node* parent = node->parent;

	while (parent && node == parent->right)
	{
		node = parent;
		parent = parent->parent;
	}

	return parent;
}

 

Min, Max는 최소값 최대값을 찾는 함수인데 이진탐색 트리에서는 계속 left나 right을 따라가기만 하면 된다. 

노드의 다음 노드를 찾는 Next 함수는 Min을 이용하여 간단하게 구현할 수 있다.

다음 노드는 현재 노드보다 크기 때문에 현재 노드의 right으로 이동해 Min을 사용하면 다음 노드를 찾을 수 있다.

그런데 노드의 right이 없을 경우 부모쪽으로 올라가서 다음 노드를 찾아야한다.

부모가 나보다 크다면 (내가 부모의 left라면) 부모가 다음 노드이고,

부모가 나보다 작다면 (내가 부모의 right이라면) 내 직속부모가 나보다 클 때까지 거슬러 올라간다.

 

 

void BinarySearchTree::Replace(Node* u, Node* v)
{
	if (u->parent == nullptr)
		_root = v;
	else if (u == u->parent->left)
		u->parent->left = v;
	else
		u->parent->right = v;

	if (v)
		v->parent = u->parent;

	delete u;
}

 

replace는 u 트리를 v 트리로 교체하는 것이다. u의 parent의 left나 right을 v로 설정하고 v의 parent 는 u의 parent로 설정한다.  u 트리와 null 포인터로 교체해서 delete 함수에도 이용할 수 있다. 

 

 

void BinarySearchTree::Delete(Node* node)
{
	if (node == nullptr)
		return;

	if (node->left == nullptr)
		Replace(node, node->right);
	else if (node->right == nullptr)
		Replace(node, node->left);
	else
	{
		// 다음 데이터 찾기
		Node* next = Next(node);
		node->key = next->key;
		Delete(next);
	}
}

 

노드를 삭제할 때 자식이 없으면 null 포인터와 교체되므로 바로 삭제되고, 자식 한쪽만 있으면 자식이 부모가 제거된 자리에 들어간다. 만약 자식이 left, right 둘 다 있으면 삭제할 노드의 next 노드를 찾아 삭제할 노드 자리에 오게 하고 next노드를 다시 삭제한다.