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

BST에 대한 간단한 설명

트리(Tree)는 비선형적이며 계층적인 자료구조의 대표적인 예로 노드(node)들의 연결체로 표현된다.

이때 각 노드는 자식 노드를 0개 이상 가질 수 있고 부모 노드는 하나만 가진다.

만약 자식 노드의 개수가 최대 2개라면 그 트리를 이진 트리(Binary Tree)라고 부른다.

이진 트리 중에서 다음 성질들을 만족하는 경우 이를 이진 탐색 트리(Binary Search Tree)라고 부른다.

노드가 왼쪽 자식 노드를 가진다면 그 노드가 가지는 값은 그 부모 노드가 가지는 값보다 작다.
노드의 오른쪽 자식 노드를 가진다면 그 노드가 가지는 값은 그 부모 노드가 가지는 값보다 작다.
트리 내의 어떠한 노드 내에서도 저 성질을 만족한다.

이진 탐색 트리는 노드의 개수가 n개일 경우 탐색, 노드 삽입, 노드 제거에

평균적인 경우 O(log(N))의 시간복잡도를 가진다.
최악의 경우 O(N)의 시간복잡도를 가진다.

최악의 경우에서 이진 탐색 트리를 보면 모양이 마치 연결 리스트와 닮아있다.

이런 경우에는 트리의 높이 값이 n에 가까워지기 때문에 탐색할 때 성능이 떨어지게 된다.

이런 문제를 해결하기 위해 2-3 트리, AVL 트리와 같은 자가 균형 이진 탐색 트리(Self Balancing Binary Search Tree)를 사용하기도 한다.

구현 코드

트리가 루트 노드가 이루는 전체 트리 뿐만 아니라 그 자식 노드들이 이루는 서브 트리들도 트리가 되기 위한 조건을 만족해야 한다는 것은, 트리가 결국 자기유사성을 띄는 구조를 가진다고 할 수 있다. 이러한 경우는 재귀(recursion)을 통해 구현하면 편리하다.

언어는 C++를 사용했다.

트리는 노드들의 연결체라 했으므로, 우선 노드를 구조체로 만들어준다. 자식 노드들은 노드의 포인터 타입으로 정의, 노드 안의 값은 int형으로 정의했다.

typedef struct node{
	node *left = nullptr;
	node *right = nullptr;
	int value;
}node;

클래스의 정의

그 다음 클래스 형태로 트리를 정의했다. 메서드는 트리의 내부적인 데이터 처리를 위한 프라이빗 메서드와, 실제 main 함수에서 트리를 사용하기 위한 퍼블릭 메서드를 분류하였다.

탐색, 노드 삽입, 노드 제거, 트리 내 최대 최소값 찾기 등의 기본적 기능을 구현했다.

class tree{
	public:
	node *root;
	tree(int val);
	
	void traverse();
	
	void level_traverse();
	
	void insertNode(int val);
	
	void deleteNode(int val);
	
	int find_maximum();
	
	int find_minimum();
	
	private:
	void p_preorder_traverse(node *n);
	
	void p_inorder_traverse(node *n);
	
	void p_postorder_traverse(node *n);
	
	void p_insert(node *n, int val);
	
	node* p_delete(node *n, int val);
	
	node* p_find_maximum(node* ref);
	
	node* p_find_minimum(node* ref);
	
	node* p_search(node *n, int val);
};

생성자

생성자를 통해 int형 변수를 인자로 받아 그 값을 가지는 루트 노드를 생성해준다.

tree::tree(int val){
		node *temp;
		temp = (node*)calloc(1,sizeof(node));
		temp->left = nullptr;
		temp->right = nullptr;
		temp->value = val;
		this->root = temp;
	}

노드의 삽입

새로운 노드의 삽입을 담당하는 메서드이다.

이진 탐색 트리의 조건에 따라 모든 노드가 자신을 기준으로 왼쪽 서브트리의 노드들의 값보다는 크고, 오른쪽 서브트리의 노드들의 값보다는 작도록 노드가 삽입된다.

이는 다음과 같은 작업을 통해 진행된다.

루트 노드부터 탐색하여 삽입하고자 하는 값과 현재 노드의 값을 비교한다.
현재 노드의 값이 더 크면 왼쪽 자식 노드로, 그 반대면 오른쪽 자식 노드로 내려간다.
왼쪽 자식 노드로 내려갈 경우
1. 왼쪽 자식 노드로 내려간 경우 그 노드가 왼쪽에 자식 노드가 없다면
2. 그렇지 않을 때에는 위 조건을 만족할 때 까지 계속 그 노드의 오른쪽 자식 노드로 내려가서 1번부터의 작업을 다시 시행한다.
오른쪽 자식 노드로 내려갈 경우
1. 오른쪽 자식 노드로 내려간 경우 그 노드가 오른쪽에 자식 노드가 없다면
2. 그 노드의 오른쪽 자식에 새로운 노드를 삽입한다.
3. 그렇지 않을 때에는 위 조건을 만족할 때 까지 계속 그 노드의 오른쪽 자식 노드로 내려가서 1번부터의 작업을 다시 시행한다.

자식 노드에서도 부모 노드에서와 동일한 작업을 수행해야하기 때문에 재귀적 방법을 통해 구현하였다.

void tree::p_insert(node *n, int val){
		node *temp;
		temp = (node*)calloc(1,sizeof(node));
		temp->value = val;
		if(n->value == temp->value)
		{
			printf("canceled. n->value : %d  val : %d. \n",n->value,val);
			return;
		}
		else if(n->value > temp->value)
		{
			if(n->left==nullptr){
				n->left = temp;
				printf("%d inserted on the left of %d.\n",temp->value,n->value);
				return;
				
			}
			else{p_insert(n->left,val);}
			
			
		}
		else if(n->value < temp->value)
		{
		if(n->right==nullptr){
				n->right = temp;
				printf("%d inserted on the right of %d.\n",val,n->value);
				return;
			}
			else{p_insert(n->right,val);}
			
		}
};

노드의 검색

트리 내에 특정 값을 가진 노드를 검색하여 조건을 만족하는 노드가 있다면 그 노드를 반환하는 메서드다.

역시 재귀를 사용하여 구현한다.

node* tree::p_search(node *n, int val){
	if(n==nullptr){
		return nullptr;
	}
	else if(n->value==val){
		return n;
	}
	else if(n->value > val){
		return p_search(n->left, val);
	}
	else if(n->value < val){
		return p_search(n->right, val);
	}
}

최대 최소값 검색

트리 내의 최대값, 최소값을 가진 노드를 찾아주는 메서드들이다.

이진 탐색 트리의 규칙에 따라서 가장 왼쪽에 있는 리프 노드가 최소값을 가지고 가장 오른쪽에 있는 리프 노드가 최대값을 가진다.

node* tree::p_find_maximum(node* ref){
	if(ref->right==nullptr){
		return ref;
	}
	else{
		return p_find_maximum(ref->right);
	}
}
 
node* tree::p_find_minimum(node* ref){
	if(ref->left==nullptr){
		return ref;
	}
	else{
		return p_find_maximum(ref->left);
	}
}

노드의 삭제

이진 탐색 트리에서 노드의 삭제는 삽입보다 좀 더 까다롭다. 노드의 삭제 후에도 이진 탐색 트리의 특성을 만족해야하기 때문이다.

노드의 삭제는 다음과 같은 절차를 통해 진행된다.

삭제하고자 하는 값을 가진 노드를 루트 노드부터 검색한다.
현재 노드의 값이 더 크면 왼쪽 자식 노드로, 그 반대면 오른쪽 자식 노드로 내려간다.
삭제하고자 하는 노드가 자식이 없거나(리프 노드) 하나 일 때
- 리프 노드의 경우 그 노드를 없애버린다.
- 자식 노드가 하나인 경우
  
  9라는 값을 가지는 노드를 제거하고자 한다.
  
  삭제하고자 하는 노드의 부모 노드와 자식 노드를 연결한다.
  
  그 뒤 노드를 삭제한다.
자식 노드가 두개인 경우

9라는 값을 가지는 노드를 제거하고자 한다.

먼저 삭제하고자 하는 노드의 오른쪽 서브트리 내의 최소값을 가진 노드를 검색한다.

그 다음 삭제하고자 하는 노드의 값을 최소값으로 덮어 씌운다.

최소값을 가지고 있던 원래 노드에 대해 삭제 작업을 한다.

node* tree::p_delete(node *n, int val){
	if(n->value > val){
		n->left = p_delete(n->left,val);
	}
	else if(n->value < val){
		n->right = p_delete(n->right,val);
	}
	else{
	if(n->left==nullptr){
		node* temp_n = n->right;
		free(n);
		return temp_n;
	}
	else if(n->right==nullptr){
		node* temp_n = n->left;
		free(n);
		return temp_n;
	}

		node* min_n = p_find_minimum(n->right);
		n->value = min_n->value;
		n->right = p_delete(min_n->right,min_n->value);

	}
	return n;
}

순회

그래프의 경우 비선형 구조이기 때문에 모든 노드를 탐색하기 위해 특별한 방법을 사용한다. 탐색 순서를 정하는 방법에 따라 DFS(Depth First Search), BFS(Breadth Firts Search)의 두 가지 방법이 있다.

트리 또한 그래프의 일종이기 때문에 저 두가지 방법을 사용한다. 다만 트리는 그래프의 특수한 형태이기 때문에 탐색을 구현하는 것이 좀 더 간단하다.

트리에서의 DFS

트리에서 DFS를 사용할 경우 탐색 순서에 따라 3가지 방법으로 나뉜다.

전위 순회(Preorder Traversal) : 루트 -> 왼쪽 자식 -> 오른쪽 자식순으로 순회
중위 순회(Inorder Traversal): 왼쪽 자식 -> 루트 -> 오른쪽 자식순으로 순화
후위 순회(Postorder Traversal): 왼쪽 자식 -> 오른쪽 자식 -> 루트순으로 순회

이 트리에서 DFS의 결과는 다음과 같다.

전위 순회 : 6 4 2 5 9 8 11 10 13
중위 순회 : 2 4 5 6 8 9 10 11 13
후위 순회 : 2 5 4 8 10 13 11 9 6

트리에서의 DFS 또한 재귀적 호출을 이용하여 구현한다.

void tree::p_preorder_traverse(node *n){
		printf("%d ",n->value);
		if(n->left!=nullptr){p_preorder_traverse(n->left);}
		if(n->right!=nullptr){p_preorder_traverse(n->right);}
	};
	
void tree::p_inorder_traverse(node *n){
		if(n->left!=nullptr){p_inorder_traverse(n->left);}
		printf("%d ",n->value);
		if(n->right!=nullptr){p_inorder_traverse(n->right);}
	};
	
void tree::p_postorder_traverse(node *n){
		if(n->left!=nullptr){p_postorder_traverse(n->left);}
		if(n->right!=nullptr){p_postorder_traverse(n->right);}
		printf("%d ",n->value);
	};

트리에서의 BFS

트리에서 BFS로 탐색할 경우 층별로 노드를 탐색한다.

이 트리에서 BFS의 결과는 다음과 같다.

순회 결과 : 6 4 9 2 5 8 11 10 13

트리에서 BFS를 구현할 때는 재귀적 호출 대신 큐(Queue)를 이용하여 구현했다.

탐색 과정을 정말 간단히 하자면 다음과 같다.

최초로 루트 노드를 큐에 삽입한다.
루트 노드를 큐에서 지운 뒤 그 자식 노드들을 큐에 삽입한다.
다시 큐에서 제일 먼저 들어간 원소를 지우고 지웠던 노드의 자식 노드들을 큐에 삽입한다.
3번 과정을 반복한다.
탐색 중에 큐가 비게 될 때는 자식 노드가 없는 가장 깊은 리프 노드까지의 탐색이 끝나는 때로 이 때 탐색을 종료한다.

  void tree::level_traverse(){
	queue<node*> q_n;
	node* n;
	n= this->root;
	q_n.push(n);
	printf("\n");
	while(!q_n.empty()){
		printf("%d ", q_n.front()->value);
		n = q_n.front();
		q_n.pop();
		if(n->left!=nullptr){
			q_n.push(n->left);
			}
		if(n->right!=nullptr){
			q_n.push(n->right);
			};
	}
	printf("\n");
	return;
}

퍼블릭 메서드들

실제로 main 함수에서 쓰게 되는 퍼블릭 메서드를 구현했다.

노드의 삽입, 삭제, 최대값과 최소값 찾기, 순회를 할 수 있다.

void tree::traverse(){
	 printf("\n");
	 p_preorder_traverse(this->root);
	 printf("\n");
	 p_inorder_traverse(this->root);
	 printf("\n");
	 p_postorder_traverse(this->root);
	 printf("\n");
	}
	
void tree::insertNode(int val){
	p_insert(this->root, val);
	}
	
void tree::deleteNode(int val){
	p_delete(this->root, val);
	}

int tree::find_maximum(){
	node* temp_n = p_find_maximum(this->root);
	return temp_n->value;
	}

int tree::find_minimum(){
	node* temp_n = p_find_minimum(this->root);
	return temp_n->value;
	}

전체 코드

전체 소스 코드를 첨부한다.

개발의 바다를 떠다니는 항해자

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

BST에 대한 간단한 설명

구현 코드

클래스의 정의

생성자

노드의 삽입

노드의 검색

최대 최소값 검색

노드의 삭제

순회

트리에서의 DFS

트리에서의 BFS

퍼블릭 메서드들

전체 코드

'Algorithm, Data Structure > Data Structure' 카테고리의 다른 글

티스토리툴바

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

BST에 대한 간단한 설명

구현 코드

클래스의 정의

생성자

노드의 삽입

노드의 검색

최대 최소값 검색

노드의 삭제

순회

트리에서의 DFS

트리에서의 BFS

퍼블릭 메서드들

전체 코드

'Algorithm, Data Structure > Data Structure' 카테고리의 다른 글

'Algorithm, Data Structure/Data Structure' Related Articles

티스토리툴바