이진 탐색 트리(Binary Search Tree)

1. 개요

이진 탐색 트리(binary search tree)는 각 노드가 최대 2개의 child node를 갖는 이진 트리(binary tree)의 특수한 형태이다. 이진 탐색 트리는 데이터를 정렬된 형태로 보관하기 때문에 효율적으로 탐색 연산을 수행할 수 있다. 평균적으로 이진 탐색 트리에서 탐색 연산의 시간복잡도는 $O(\log_2n)$이다. 그러나 이진 탐색 트리는 입력되는 값의 순서에 따라 트리의 구성이 달라지기 때문에 트리가 한쪽으로 기울어진 편향 이진 트리(skewed binary tree)가 생성될 수 있다. 이러한 경우에는 탐색 연산의 시간복잡도가 $O(n)$으로 급증한다.

2. 정의

이진 탐색 트리의 정의는 아래와 같다.

각 노드는 최대 2개의 child node만을 가질 수 있다.
노드의 왼쪽 subtree는 그 노드의 값보다 작은 값들을 지닌 노드들로 이루어진다.
노드의 오른쪽 subtree는 그 노드의 값보다 큰 값들을 지닌 노드들로 이루어진다.
좌우 subtree는 각각이 다시 이진 탐색 트리이다.
각 노드의 값은 중복을 허용하지 않는다.

아래의 [그림 1]은 이진 탐색 트리의 몇 가지 예시를 나타낸다.

[그림 1] 이진 탐색 트리의 예시

3. Class 정의

이진 탐색 트리를 정의하기 위해서는 먼저 이진 탐색 트리의 노드를 정의해야 한다. 이진 탐색 트리의 각 노드는 데이터 필드와 왼쪽 자식 노드를 가리키는 포인터, 오른쪽 자식 노드를 가리키는 포인터를 갖는다. [소스 코드 1]은 이진 탐색 트리를 구성하는 class Node의 정의이다. 이진 탐색 트리의 구현에는 C++를 이용하였다.

[소스 코드 1] Class Node

아래의 [소스 코드 2]는 class Node를 이용하여 이진 탐색 트리를 정의하는 class BinarySearchTree이다.

[소스 코드 2] Class BinarySearchTree

Class BinarySearchTree에는 트리의 최상위 노드를 가리키는 root 포인터가 포함되어 있으며, 연산으로는 노드를 추가하는 insert 함수, 노드를 삭제하는 remove 함수, 특정 값을 갖고 있는 노드를 반환하는 get 함수가 있다. 또한, class BinarySearchTree에는 트리를 순회하면서 각 노드의 값을 C++의 ostream에 출력하는 traversal 함수가 정의되어 있다.

3. Insertion 연산

이진 탐색 트리는 데이터를 추가하는 동시에 데이터를 정렬하는 특성을 갖고 있다. [그림 2]는 이진 탐색 트리에 데이터 4를 insert하는 과정을 나타낸다.

[그림 2] 이진 탐색 트리의 insert 과정

어떠한 노드에 저장된 값을 기준으로, 새로운 데이터가 현재 노드에 저장된 값보다 작으면 왼쪽, 크면 오른쪽으로 이동한다. 이러한 과정은 재귀적으로 반복되기 때문에 아래의 [소스 코드 3]과 같이 이진 탐색 트리의 insert 함수는 자신을 반복적으로 호출한다.

[소스 코드 3] insert 함수

이진 탐색 트리의 insert 함수는 어떠한 노드의 child node가 NULL일 때까지 트리의 하단으로 이동하며, NULL 이 아닌 경우에는 자기 자신인 insert 함수를 재귀적으로 호출한다.

4. Deletion 연산

이진 탐색 트리의 deletion 연산은 insertion 연산에 비해 매우 복잡하다. 이진 탐색 트리의 deletion 연산은 아래의 [그림 3]과 같은 3가지 경우를 모두 고려해야 한다.

[그림 3] Deletion 연산이 발생하는 상황에 대한 3가지 경우

[그림 3]의 (a)와 같은 경우에는 6을 제거하고, 6이 있었던 자리에 4를 위치시킨다. 만약 4의 chide node들이 존재한다면, 이들 중에서 가장 큰 값을 6의 자리에 위치시킨다. 가장 큰 값을 갖고 있는 노드를 찾는 작업은 아래의 [소스 코드 4]와 같은 findMaxNode 함수에 의해 수행되며, findMaxNode는 remove 함수에서 호출된다.

[소스 코드 4] findMaxNode 함수

[그림 3]의 (b)와 같이 제거되는 노드가 left child만 갖고 있는 경우에는 단순히 left child를 제거되는 노드의 자리에 위치시키면 된다. 반대로, (c)와 같이 right child만 갖고 있는 경우에는 right child를 제거되는 노드의 자리에 위치시키기만 하면 된다. 아래의 [소스 코드 5]는 이진 탐색 트리의 deletion 연산을 구현한 remove 함수이다.

[소스 코드 5] remove 함수

5. 전체 소스 코드

이진 탐색 트리의 구현을 위한 전체 소스 코드는 아래와 같다.

소스 파일: BinarySearchTree.h

#ifndef BST
#define BST

#include <iostream>
#define PRE_ORDER	0
#define IN_ORDER	1
#define POST_ORDER	2
using namespace std;

template <typename T>
class Node {
	template <typename T>
	friend class BinarySearchTree;
public:
	Node(const T & data);
private:
	T data;
	Node<T> *leftChild;
	Node<T> *rightChild;
};

template <typename T>
class BinarySearchTree {
public:
	BinarySearchTree();
	~BinarySearchTree();
	bool insert(const T & data);
	int remove(const T & data);
	T & get(const T & data);
	void traversal(const int order, ostream & stream) const;
private:
	Node<T> *root;
	bool isRemoved;
	void init();
	bool insert(Node<T> *current, const T & data);
	Node<T> *remove(Node<T> *current, const T &data);
	Node<T> *findNode(Node<T> *current, const T & data) const;
	Node<T> *findMaxNode(Node<T> *current) const;
	void preorderTraversal(Node<T> *current, ostream & stream) const;
	void inorderTraversal(Node<T> *current, ostream & stream) const;
	void postorderTraversal(Node<T> *current, ostream & stream) const;
	void destroyNode(Node<T> *current);
};

template <typename T>
Node<T>::Node(const T & data) {
	this->data = data;
	this->leftChild = NULL;
	this->rightChild = NULL;
}

template <typename T>
BinarySearchTree<T>::BinarySearchTree() {
	init();
}

template <typename T>
BinarySearchTree<T>::~BinarySearchTree() {
	destroyNode(root);
}

template <typename T>
bool BinarySearchTree<T>::insert(const T & data) {
	if (root == NULL) {
		root = new Node<T>(data);

return true;
	}
	else {
		return insert(root, data);
	}
}

template <typename T>
int BinarySearchTree<T>::remove(const T & data) {
	isRemoved = true;

if (root == NULL) {
		return false;
	}

if (data < root->data) {
		remove(root->leftChild, data);
	}
	else if (data > root->data) {
		remove(root->rightChild, data);
	}
	else if(data == root->data) {
		remove(root, data);
	}

return isRemoved;
}

template <typename T>
T & BinarySearchTree<T>::get(const T & data) {
	Node<T> *target = findNode(root, data);

return target->data;
}

template <typename T>
Node<T> *BinarySearchTree<T>::findNode(Node<T> *current, const T & data) const {
	if (data == current->data) {
		return current;
	}
	else if (data < current->data) {
		return findNode(current->leftChild, data);
	}
	else if (data > current->data) {
		return findNode(current->rightChild, data);
	}

return NULL;
}

template <typename T>
Node<T> *BinarySearchTree<T>::findMaxNode(Node<T> *current) const {
	if (current->rightChild == NULL) {
		return current;
	}
	else {
		return findMaxNode(current->rightChild);
	}
}

template <typename T>
void BinarySearchTree<T>::traversal(const int order, ostream & stream) const {
	if (order == PRE_ORDER) {
		preorderTraversal(root, stream);
	}
	else if (order == IN_ORDER) {
		inorderTraversal(root, stream);
	}
	else if (order == POST_ORDER) {
		postorderTraversal(root, stream);
	}
}

template <typename T>
void BinarySearchTree<T>::init() {
	root = NULL;
	isRemoved = false;
}

template <typename T>
bool BinarySearchTree<T>::insert(Node<T> *current, const T & data) {
	if (data < current->data) {
		if (current->leftChild == NULL) {
			current->leftChild = new Node<T>(data);
		}
		else {
			return insert(current->leftChild, data);
		}
	}
	else if (data > current->data) {
		if (current->rightChild == NULL) {
			current->rightChild = new Node<T>(data);
		}
		else {
			return insert(current->rightChild, data);
		}
	}
	else if(data == current->data) {
		return false;
	}
}

template <typename T>
Node<T> *BinarySearchTree<T>::remove(Node<T> *current, const T & data) {
	if (current == NULL) {
		isRemoved = false;
		return NULL;
	}

if (data < current->data) {
		current->leftChild = remove(current->leftChild, data);
	}
	else if (data > current->data) {
		current->rightChild = remove(current->rightChild, data);
	}
	else if (data == current->data) {
		if (current->leftChild != NULL && current->rightChild != NULL) {
			Node<T> *maxNode = findMaxNode(current->leftChild);

current->data = maxNode->data;
			current->leftChild = remove(current->leftChild, maxNode->data);
		}
		else if (current->leftChild != NULL && current->rightChild == NULL) {
			Node<T> *temp = current;

current = current->leftChild;
			delete temp;
		}
		else if (current->leftChild == NULL && current->rightChild != NULL) {
			Node<T> *temp = current;
			
			current = current->rightChild;
			delete temp;
		}
		else {
			delete current;
			current = NULL;
		}
	}

return current;
}

template <typename T>
void BinarySearchTree<T>::preorderTraversal(Node<T> *current, ostream & stream) const {
	if (current != NULL) {
		stream << current->data << " ";
		preorderTraversal(current->leftChild, stream);
		preorderTraversal(current->rightChild, stream);
	}
}

template <typename T>
void BinarySearchTree<T>::inorderTraversal(Node<T> *current, ostream & stream) const {
	if (current != NULL) {
		inorderTraversal(current->leftChild, stream);
		stream << current->data << " ";
		inorderTraversal(current->rightChild, stream);
	}
}

template <typename T>
void BinarySearchTree<T>::postorderTraversal(Node<T> *current, ostream & stream) const {
	if (current != NULL) {
		postorderTraversal(current->leftChild, stream);
		postorderTraversal(current->rightChild, stream);
		stream << current->data << " ";
	}
}

template <typename T>
void BinarySearchTree<T>::destroyNode(Node<T> *current) {
	if (current != NULL) {
		destroyNode(current->leftChild);
		destroyNode(current->rightChild);
		delete current;
	}
}
#endif

저작자표시 비영리 변경금지

이진 탐색 트리(Binary Search Tree)

관련글

티스토리툴바