[자료구조] 이원 탐색 트리(Binary Search Tree)

사전(Dictionary)

사전(Dictionary)은 쌍의 집합으로서 각 쌍은 키와 이에 연관된 원소로 구성된다.

같은 key를 갖는 두 쌍은 없다고 가정한다.

template <class T>
class Dictionary{
public:
    virtual bool IsEmpty() const = 0;
    virtual pair<K,E> *Get(const k&) const = 0;
    virtual void Insert(const pair<K,E>&) = 0;
    virtual void Delete(const K&) = 0;
};

키와 원소의 데이터 값은 각각 K와 E이다.

 

이진 탐색 트리(Binary Search Tree)

1. 모든 원소는 서로 다른 유일한 키를 갖는다.
2. 왼쪽 서브 트리에 있는 원소의 키들은 그 루트의 키보다 작다.
3. 오른쪽 서브 트리에 있는 원소의 키들은 그 루트의 키보다 크다.
4. 왼쪽 서브 트리와 오른쪽 서브 트리도 이진 탐색 트리다.

<재귀를 이용한 탐색>

template <class T>
class TreeNode { 
friend class Tree<T>;
private:
	T data;
	TreeNode<T> *leftChild;
	TreeNode<T> *rightChild;
};

template <class K, class E> //Driver
pair<K,E>* BST<K,E>::Get(const K& k)
{ //키 k를 가진 쌍을 이원 탐색 트리(*this)에서 탐색
// 쌍을 발견하면 포인터 반환, 아니면 0 반환
	return Get(root, k);
}
template <class K, class E> //Workhorse
pair<K,E>* BST<K,E>::Get(TreeNode <pair <K,E>>* p, const K& k)
{
	if(!p) return 0;
	if(k < p->data.first) return Get(p->leftChild, k);
	if(k > p->data.first) return Get(p->rightChild, k);
	return &p->data;
}

<정수형 Key만으로 구성된 트리의 탐색>

int BST<K,E>::Get(const int& k)
{ //키 k를 가진 쌍을 이원 탐색 트리(*this)에서 탐색
// 쌍을 발견하면 값 반환, 아니면 0 반환
	return Get(root, k);
}
int BST<K,E>::Get(TreeNode <int>* p, const int& k)
{
	if(!p) return 0;
	if(k < p->data) return Get(p->leftChild, k);
	if(k > p->data) return Get(p->rightChild, k);
	return p->data;
}

<반복문을 사용한 탐색>

template <class K, class E>
pair<K,E>* BST<K,E>::Get(const K& k)
{
	TreeNode <pair<K, E>> *currentNode = root;
	while (currentNode) {
		if (k < currentNode->data.first)
			currentNode = currentNode->leftChild;
		else if (k > currentNode->data.first)
			currentNode = currentNode->rightChild;
		else
			return &currentNode->data;
	}
	return 0;
}

<순위에 의한 탐색>

template <class K, class E> //순위에 의한 탐색
pair<K,E>* BST<K,E>::RankGet(int r)
{ //r번째 작은 쌍을 탐색한다.
	TreeNode<pair<K,E>>*currentNode = root;
	while(currentNode) {
		if(r < currentNode->leftSize) 
			currentNode = currentNode->leftChild;
		else if (r > currentNode->leftSize) {
			r -= currentNode->leftSize;
			currentNode = currentNode->rightChild;
		}
	else 
		return &currentNode->data;
    }
	return 0;
}

 

이진 탐색 트리에서의 삽입

 

p는 root에서 시작하며, pp는 현재 node의 parent다.

이를 코드로 나타내면 다음과 같다.

template <class K, class E>
void BST<K,E>::Insert(const pair<K,E>& thePair)
{ // Insert thePair into the binary search tree.
// search for thePair.first, pp is parent of p
	TreeNode<pair<K,E>> *p = root, *pp = 0;
	while (p) {
		pp = p;
		if (thePair.first < p->data.first) p = p->leftChild;
		else if (thePair.first > p->data.first) p = p->rightChild;
		else {// 이미 key가 있는 경우 value를 update 후 종료
			p->data.second = thePair.second; return;
		}
	}
	// perform insertion
	p = new TreeNode<pair<K,E>>(thePair);
	if (root) // tree not empty
		if (thePair.first < pp->data.first) pp->leftChild = p;
		else pp->rightChild = p;
	else root = p;
}

 

이진 탐색 트리에서의 삭제

<리프 원소의 삭제>

• 부모의 자식 필드에 0을 삽입한다.
• 삭제된 노드를 반환한다.

 

<하나의 자식을 가진 비리프 노드의 삭제>

• 삭제된 노드의 자식을 삭제된 노드의 자리에 위치한다.

<두 개의 자식을 가진 비리프 노드의 삭제>

• 왼쪽 서브 트리에서 가장 큰 원소나 오른쪽 서브 트리에서 가장 작은 원소로 대체한다.
• 대체된 서브 트리에서 대체한 원소의 삭제 과정을 진행한다.