[자료 구조] 알아야 할 자료구조 Binary Search Tree

Binary Search Tree

트리형 데이터 구조는 탐색에 최적화된 자료 구조이다.

 

- 이진 탐색 트리 Binary Search Tree

각 노드는 키 값을 가지며 root와 left, right child 노드를 기준으로 다음을 만족해야 한다.

1. left.key <  root.key

2. right.key > root.key

3. left 서브 트리와 right 서브 트리는 BST를 만족해야 한다.

 

- 이진 탐색 트리의 중위 순회

위 성질을 만족하기 때문에 left -> root -> right의 중위 순회에서 key 값을 순서대로 출력하면 정렬된 값을 얻을 수 있다.

 

- 탐색 시간

높이가 h인 모든 레벨에 노드가 채워진 완전 이진트리의 전체 노드 개수는 $1 + 2 + ... + 2^h$ 이다.  전체 갯수 $2^{h+1} -1 = N$ 이므로 $h = logN$의 식을 얻을 수 있다.

각 질의에 대한 key 값을 BST에 존재하는지 탐색하기 위해 이진 탐색 트리 성질을 이용하여 다음 탐색 과정을 거친다.

1. key < root.key : 왼쪽으로 탐색

2. key > root.key : 오른쪽으로 탐색

3. key == root.key : root 반환

 

평균 탐색 시간은 root 노드에서 모든 노드에 대해 각 노드까지 도달하는 경로의 합을 노드 수로 나누어 평균을 구한 것과 같다. 이는 $\Theta(h) = \Theta(logN)$로 알려져 있다.

 

하지만 자료의 삽입 순서에 따라 이진 탐색 트리의 구조는 한쪽 서브 트리의 높이가 비대하지는 불균형 트리가 만들어질 수 있다. 이를 해결하기 위해 AVL이나 Red-Black과 같은 균형 트리를 사용하며 기본 자료구조인 이진 탐색 트리의 경우 균형을 맞추는 기능이 없기 때문에 트리 높이가 전체 노드 개수가 되어 최악의 경우 $O(N)$이 된다.

 

- 트리를 구성하는 기본 노드 구조

template <typename Key>
class TreeNode
{
	template<typename Key>
	friend class BinarySearchTree;
public:
	Key _key;
	TreeNode* _left = nullptr;
	TreeNode* _right = nullptr;
private:
	TreeNode(Key key)
		: _key(key) 
	{
	}
	~TreeNode()
	{
		delete _left;
		delete _right;
	}
};

- 삽입

1. left.key <  root.key

2. right.key > root.key

private:
	void Insert(Key key, NodePtr root)
	{		
		// key < root.key
		if (key < root->_key)
		{
			// 왼쪽 서브트리가 있을 경우 계속 탐색
			if(root->_left)
				return Insert(key, root->_left);
			// 여기에 삽입
			root->_left = new Node(key);
		}
		// key > root.key
		else if (key > root->_key)
		{
			// 오른쪽 서브 트리가 있을 경우 계속 탐색
			if (root->_right)
				return Insert(key, root->_right);
			// 여기에 삽입
			root->_right = new Node(key);
		}
		// 중복 키는 허용하지 않는다.
	}

- 탐색

탐색도 삽입과 같은 원리로 이진 탐색 성질을 이용하여 찾는다.

	NodePtr Search(Key key, NodePtr root)
	{
		// 키 찾았거나 없는 경우
		if (!root || key == root->_key)
			return root;

		if (key < root->_key)
			return Search(key, root->_left);
		else
			return Search(key, root->_right);
	}

- 삭제

삭제의 경우 고려할 사항이 있게 되는데, 삭제할 노드를 대신할 노드를 찾아야한다. 그러한 노드는 왼쪽 서브트리에서 가장 큰 값이거나 오른쪽 서브트리에서 가장 작은 값을 택하면 된다.

 

1. 오른쪽 서브트리에서 가장 작은 값을 가지는 노드를 찾는다. 그러한 노드를 y라 하자

2. 삭제할 노드 x의 키 값을 y의 키값으로 대입한다.

3. 다시 x의 오른쪽 서브 트리에서 y의 키값을 삭제하는 것으로 재귀한다.

 

위 재귀의 연속으로 대입이 계속 일어나고 최종 도달한 노드의 경우 리프 노드 이거나 왼쪽 서브트리만 가지고 있는 경우이다. 최종 도달한 노드를 삭제하고 왼쪽 서브트리가 있을 경우 그 루트를 최종 도달 노드에 할당한다.

 

실제로는 최종 도달 노드의 Parent의 왼쪽에 할당하는 것이니 함수를 잘 설계하여 Parent에 꼭 할당할 수 있도록 한다.

	NodePtr Erase(Key key, NodePtr root)
	{
		// 키 찾지 못함
		if (!root)
			return root;

		if (key < root->_key)
		{
			root->_left = Erase(key, root->_left);
		}
		else if (key > root->_key)
		{
			root->_right = Erase(key, root->_right);
		}

		// 키를 찾은 경우
		if (key == root->_key)
		{
			// 리프 노드 혹은 왼쪽 서브트리만 있는 노드에 도달한 경우 삭제하고 왼쪽 노드를 반환
			if (!root->_right)
			{
				NodePtr leftSubTree = root->_left;
				delete root;
				return leftSubTree;
			}

			// 오른쪽 서브트리에서 가장 작은 키를 가지는 노드를 찾는다.
			NodePtr rightSmallest = FindMinNode(root->_right);
			
			// 키 변경
			root->_key = rightSmallest->_key;

			// 재귀
			root->_right = Erase(rightSmallest->_key, root->_right);
		}

		// 정상 삭제 후 재귀 스택 호출 종료 
		return root;
	}
	NodePtr FindMinNode(NodePtr root)
	{
		if (root->_left)
			return FindMinNode(root->_left);

		return root;
	}

 

전체 소스 코드

프로그램 종료시 트리의 노드 삭제는 재귀적으로 일어나도록 해준다.

template <typename Key>
class BinarySearchTree
{
public:
	using Node = TreeNode<Key>;
	using NodePtr = TreeNode<Key>*;
	~BinarySearchTree()
	{
		delete _root;
	}
private:
	NodePtr _root = nullptr;
private:
	void Insert(Key key, NodePtr root)
	{		
		// key < root.key
		if (key < root->_key)
		{
			// 왼쪽 서브트리가 있을 경우 계속 탐색
			if(root->_left)
				return Insert(key, root->_left);
			// 여기에 삽입
			root->_left = new Node(key);
		}
		// key > root.key
		else if (key > root->_key)
		{
			// 오른쪽 서브 트리가 있을 경우 계속 탐색
			if (root->_right)
				return Insert(key, root->_right);
			// 여기에 삽입
			root->_right = new Node(key);
		}
		// 중복 키는 허용하지 않는다.
	}
	NodePtr Search(Key key, NodePtr root)
	{
		// 키 찾았거나 없는 경우
		if (!root || key == root->_key)
			return root;

		if (key < root->_key)
			return Search(key, root->_left);
		else
			return Search(key, root->_right);
	}
	NodePtr Erase(Key key, NodePtr root)
	{
		// 키 찾지 못함
		if (!root)
			return root;

		if (key < root->_key)
		{
			root->_left = Erase(key, root->_left);
		}
		else if (key > root->_key)
		{
			root->_right = Erase(key, root->_right);
		}

		// 키를 찾은 경우
		if (key == root->_key)
		{
			// 리프 노드 혹은 왼쪽 서브트리만 있는 노드에 도달한 경우 삭제하고 왼쪽 노드를 반환
			if (!root->_right)
			{
				NodePtr leftSubTree = root->_left;
				delete root;
				return leftSubTree;
			}

			// 오른쪽 서브트리에서 가장 작은 키를 가지는 노드를 찾는다.
			NodePtr rightSmallest = FindMinNode(root->_right);
			
			// 키 변경
			root->_key = rightSmallest->_key;

			// 재귀
			root->_right = Erase(rightSmallest->_key, root->_right);
		}

		// 정상 삭제 후 재귀 스택 호출 종료 
		return root;
	}
	NodePtr FindMinNode(NodePtr root)
	{
		if (root->_left)
			return FindMinNode(root->_left);

		return root;
	}
	void InOrderTraversal(NodePtr root)
	{
		if (!root)
			return;

		InOrderTraversal(root->_left);
		printf("%d ", root->_key);
		InOrderTraversal(root->_right);
	}
public:
	void Insert(Key key)
	{
		if (!_root)
		{
			_root = new Node(key);
			return;
		}
		Insert(key, _root);
	}
	NodePtr Search(Key key)
	{
		return Search(key, _root);
	}
	void Erase(Key key)
	{
		_root = Erase(key, _root);
	}
	void Print()
	{
		InOrderTraversal(_root);
		printf("\n");
	}
};

 

- 참고 자료

www.geeksforgeeks.org/avl-tree-set-1-insertion/

www.geeksforgeeks.org/binary-search-tree-set-2-delete/