언어 [자료구조] Binary Search Tree
2006.12.29 10:39
오늘은 그동안 강의했던 객체 지향 프로그래밍에서 약간 벗어나, 자료 구조에 대해 설명을 드리려고 합니다.
매일 똑같은 것만 보면 질리기 마련이니까요 ^^; (말하는 사람도 지쳐요 ~)
- 자료구조는 무엇인가?
: 우리가 프로그램을 만들면서 사용하는 데이터는 너무나 다양합니다. 정수, 실수, 문자, 문자열, 객체...
이런 자료들을 어떻게 하면 효율적으로 컴퓨터에서 다룰 수 있을 것인가에 대한 분야입니다.
가장 기초적인 자료구조는 '배열', '구조체' 등이 있고, 약간 발전한 '클래스(객체)' 도 자료구조로 칠 수 있습니다.
하지만 이런 것은 그냥 '덩어리'를 통채로 만들어 내는 것이라 융통성이 없지요.
예를 들어 배열을 10개 잡는다면 그 이후에는 크기를 변경할 수 없잖아요?
그래서 처음 등장한 것이 Linked List, 연결 리스트형태입니다. 이부분은 아래쪽에 잘 설명해주신분이 계시기에 넘어가기로 했습니다.
저 연결리스트를 사람들이 많이 사용하다가 느낀점은, '자료를 찾는데 너무 오래걸린다!' 라는 것입니다.
크기도 융통성 있게 변하고, 데이터도 모두 다룰 수 있는 점에서는 합격이었지만, 연결 리스트이기에 처음부터 마지막까지 쭉 훑어봐야하는 과정이 필요했던 것이죠.
그래서 등장한 것이 지금 설명드리는 Binary Search Tree입니다.
[10]
┌─┴─┐
[5] [15]
┌┴┐ ┌┴─┐
[2] [7] [12] [17]
[예.이진 탐색트리]
위 그림에서 제일 꼭대기에 있는 [10]을 Root라고 부릅니다.
왼쪽에 연결된 칸에는 10보다 작은 데이터.
오늘쪽에 연결된 칸에는 10보다 큰 데이터를 넣어 놓는 방식입니다.
여기서 12를 찾고자 한다면, [10]에서 시작해서, 목표인 12가 현재칸의 수보다 크면 오른쪽 칸으로, 작으면 왼쪽칸으로 이동하면서 비교를 하면 됩니다.
단순히 보면, [10]->[15]->[12] 순으로 찾아나가게 되는 것이지요.
단순한 연결리스트였다면, [2]->[5]->[7]->[10]->[12] 이런 순서로 검색을 하게 될 것입니다.
이 규칙을 이용해서, 삽입 역시 쉽게 할 수 있습니다.
13을 삽입한다고 예를 들면, 13을 검색하면서 따라가다가 '공백'을 만나면 새로 칸을 만들어서 저장하면 됩니다.
규칙대로 [12]의 오른쪽 칸에 삽입이 될 것입니다.
하지만 BST(Binary Search Tree)에서 중요한 것은 '삭제'입니다.
만약 [10]을 삭제한다고 하면, 어떻게 해야 할까요?
이 때의 방법은 약간 생각을 해야합니다. 10에서 연결된 양쪽 데이터들 역시 작은 BST라고 할 수 있지요?
[5] [15]
┌┴┐ ┌┴─┐
[2] [7] [12] [17]
이 양쪽의 작은 트리중에 가장 가운데에 가까운 숫자를 뽑아냅시다.
7 또는 12가 선택되어야 합니다.
이를 선택하는 방법은, 양쪽 트리를 기준으로 공백이 나올때까지 왼쪽 또는 오른쪽으로 이동하면 한쪽 트리의 끝 데이터를 만날 수 있습니다.
이때의 데이터를 삭제할 [10]의 위치에 넣는 것입니다.
[7] 노드를 선택하였다고 합시다.
[7]
┌─┴─┐
[5] [15]
┌┘ ┌┴─┐
[2] [12] [17]
대충 어떤 방식인지 이해가 가시겠죠?
몇개의 발생할 수 있는 상황을 예측해서 그에따른 BST를 유지해주는 것이 관건입니다.
그리고 또 한가지 알려드릴 것은 In Order Traversal 입니다. 이것은 Tree를 하나의 리스트로 바꿔줄 수 있는 방법입니다.
List를 가지고 트리를 구성할 수도 있습니다.
In Order Traversal은 어떤 노드에서 시작하여, '왼쪽 데이터뭉치', 자신, '오른쪽 데이터뭉치' 순서로 출력하는 것을 기준으로 계속 아래쪽으로 시켜나가는 방식입니다.
그림으로 설명드리는게 가장 편하겠군요.
1 : 왼쪽 - [7] - 오른쪽
2 : 왼쪽-[5]-오른쪽-[7]-왼쪽-[15]-오른쪽
3 : [2]-[5]-[7]-[12]-[15]-[17]
이런식으로 시켜나가면 왼쪽부터 오른쪽 데이터까지 순서대로 가져올 수 있습니다.
이번에 알려드린 BST는 가장 기본적인 검색트리로써, 데이터를 [간단하고] 빠르게 찾아낼 수 있는 유명한 방식입니다.
오늘은 말로만 설명을 드리면 이해가 안되실 분들이 많을 것 같아서 예제를 통채로 드리니 참고하세요.
삽입, 삭제, 검색, In Order Traversal을 확인하기 쉽도록 메뉴를 만들어 두었습니다.
코드를 그대로 가져다 컴파일 하셔도 동작하니 한번쯤 테스트하고, 자료구조가 어떤 것인가에 대해 생각해보시는 것도 좋을 것 같습니다.
===============================================================================
#include <iostream>
#include <string>
using namespace std;
class BST
{
public:
typedef struct BST_Node
{
struct BST_Node* l_child;
struct BST_Node* r_child;
int Key;
} BST_NODE;
BST_NODE* root;
BST();
~BST();
BST_NODE* Insert_BST(int Key);
BST_NODE* Insert_BST(int Key, BST_NODE* srt);
int Search_BST(int Key);
int Search_BST(int Key, BST_NODE* srt);
int Delete_BST(int Key);
int Delete_BST(int Key, BST_NODE* srt, bool display);
BST_NODE* Get_MAX(BST_NODE* srt);
BST_NODE* Get_MIN(BST_NODE* srt);
void InOrderTraversal();
void InOrderTraversal(BST_NODE* srt);
int Clear(BST_NODE** Key);
int Clear_All();
};
BST::BST()
{
root = 0;
}
BST::~BST()
{
Clear_All();
}
BST::BST_NODE* BST::Get_MAX(BST_NODE* srt)
{
if (srt->r_child == 0) return srt;
else return Get_MAX(srt->r_child);
}
BST::BST_NODE* BST::Get_MIN(BST_NODE* srt)
{
if (srt->l_child == 0) return srt;
else return Get_MIN(srt->l_child);
}
BST::BST_NODE* BST::Insert_BST(int Key)
{
return Insert_BST(Key, root);
}
BST::BST_NODE* BST::Insert_BST(int Key, BST_NODE* srt)
{
if (root == 0)
{
root = new BST_NODE();
root->Key = Key;
root->l_child = 0;
root->r_child = 0;
cout << " * 정상적으로 입력되었습니다. " << endl;
return root;
}
else
{
if (srt == 0)
{
srt = new BST_NODE();
srt->Key = Key;
srt->l_child = 0;
srt->r_child = 0;
cout << " * 정상적으로 입력되었습니다. " << endl;
return srt;
}
else
{
if (srt->Key > Key)
{
BST_NODE* temp = Insert_BST(Key, srt->l_child);
if (temp != 0)
srt->l_child = temp;
return 0;
}
else if (srt->Key == Key)
{
cout << " * 이미 노드가 존재합니다. " << endl;
return 0;
}
else
{
BST_NODE* temp = Insert_BST(Key, srt->r_child);
if (temp != 0)
srt->r_child = temp;
return 0;
}
}
}
}
int BST::Search_BST(int Key)
{
return Search_BST(Key, root);
}
int BST::Search_BST(int Key, BST_NODE* srt)
{
if (srt == 0)
{
cout << " * 노드가 존재하지 않습니다." << endl;
return -1;
}
else
{
if (srt->Key > Key)
return Search_BST(Key, srt->l_child);
else if (srt->Key == Key)
{
cout << " * 노드를 찾았습니다. [" << srt->Key <<"]" << endl;
return srt->Key;
}
else
return Search_BST(Key, srt->r_child);
}
return 0;
}
int BST::Delete_BST(int Key)
{
int temp = Delete_BST(Key, root, true);
if (temp == 1)
{
cout << " * 트리가 공백입니다." << endl;
root = 0;
return 1;
}
else return temp;
}
int BST::Delete_BST(int Key, BST_NODE* srt, bool display)
{
if (srt != 0)
{
if (srt->l_child == 0 && srt->r_child == 0)
{
if (srt->Key == Key)
{
if (display)
cout << " * 성공적으로 삭제하였습니다." << endl;
delete(srt);
return 1;
}
else
{
if (display)
cout << " * 노드를 찾을 수 없습니다." << endl;
return 0;
}
}
else
{
if (srt->Key == Key)
{
int temp = 0;
if (srt->l_child != 0) temp = Get_MAX(srt->l_child)->Key;
else temp = Get_MIN(srt->r_child)->Key;
Delete_BST(temp, root, false);
if (display)
cout << " * 성공적으로 삭제하였습니다." << endl;
srt->Key = temp;
return 0;
}
if (srt->l_child != 0)
{
int temp = Delete_BST(Key, srt->l_child, display);
if (temp == 1) srt->l_child = 0;
}
if (srt->r_child != 0)
{
int temp = Delete_BST(Key, srt->r_child, display);
if (temp == 1) srt->r_child = 0;
}
else return 0;
return 0;
}
}
else return 0;
}
int BST::Clear(BST_NODE** Key)
{
if ((*Key) != 0)
{
if ((*Key)->l_child != 0)
Clear(&((*Key)->l_child));
if ((*Key)->r_child != 0)
Clear(&((*Key)->r_child));
delete(*Key);
(*Key) = 0;
}
return 0;
}
int BST::Clear_All()
{
return Clear(&root);
}
void BST::InOrderTraversal()
{
InOrderTraversal(root);
}
void BST::InOrderTraversal(BST_NODE *srt)
{
if (srt == 0) return;
else
{
if ((srt->l_child))
InOrderTraversal(srt->l_child);
cout << "[" << srt->Key << "] ";
if ((srt->r_child))
InOrderTraversal(srt->r_child);
}
}
void main()
{
string command = "0";
BST bst;
for(;;)
{
system("cls");
cout << "====================================" << endl;
cout << " Binary Search Tree " << endl;
cout << "------------------------------------" << endl;
cout << " 1. Insert " << endl;
cout << " 2. Search " << endl;
cout << " 3. Delete " << endl;
cout << " 4. Clear " << endl;
cout << " 5. In Order Traversal " << endl;
cout << " 6. Exit " << endl;
switch(command[0])
{
case '1':
cout << "------------------------------------" << endl;
cout << " * 정상적으로 삽입 되었습니다. " << endl;
break;
case '2':
cout << "------------------------------------" << endl;
cout << " * 정상적으로 검색 되었습니다. " << endl;
break;
case '3':
cout << "------------------------------------" << endl;
cout << " * 정상적으로 삭제 되었습니다. " << endl;
break;
case '4':
cout << "------------------------------------" << endl;
cout << " * 정상적으로 반환 되었습니다. " << endl;
break;
case '5':
cout << "------------------------------------" << endl;
cout << " * 정상적으로 출력 되었습니다. " << endl;
break;
}
cout << "====================================" << endl;
cout << ">";
cin >> command;
if (command[0] == '6') break;
int icommand = 0;
BST::BST_Node* ncommand = 0;
switch(command[0])
{
case '1':
system("cls");
cout << "====================================" << endl;
cout << " Binary Search Tree " << endl;
cout << "------------------------------------" << endl;
cout << " * 삽입할 노드의 키를 입력하세요. " << endl;
cout << "------------------------------------" << endl;
cout << ">"; cin >> icommand;
cout << "====================================" << endl;
ncommand = bst.Insert_BST(icommand);
system("pause");
break;
case '2':
system("cls");
cout << "====================================" << endl;
cout << " Binary Search Tree " << endl;
cout << "------------------------------------" << endl;
cout << " * 검색할 노드의 키를 입력하세요. " << endl;
cout << "------------------------------------" << endl;
cout << ">"; cin >> icommand;
cout << "====================================" << endl;
icommand = bst.Search_BST(icommand);
system("pause");
break;
case '3':
system("cls");
cout << "====================================" << endl;
cout << " Binary Search Tree " << endl;
cout << "------------------------------------" << endl;
cout << " * 삭제할 노드의 키를 입력하세요. " << endl;
cout << "------------------------------------" << endl;
cout << ">"; cin >> icommand;
cout << "====================================" << endl;
icommand = bst.Delete_BST(icommand);
system("pause");
break;
case '4':
system("cls");
cout << "====================================" << endl;
cout << " Binary Search Tree " << endl;
cout << "------------------------------------" << endl;
cout << " * 정상적으로 반환하였습니다. " << endl;
cout << "====================================" << endl;
bst.Clear_All();
system("pause");
break;
case '5':
system("cls");
cout << "====================================" << endl;
cout << " Binary Search Tree " << endl;
cout << "------------------------------------" << endl;
cout << " * In Oder Traversal 결과 " << endl;
cout << " : "; bst.InOrderTraversal(); cout << endl;
cout << "====================================" << endl;
system("pause");
break;
default:
break;
}
}
}
=================================================
댓글 4
-
flint
2006.12.29 22:15
이진탐색트리와 중위순회~~~ 감회가 새롭군요.|+rp2+|2564|+rp3+|acoc_board_ideatip -
Zeprod
2006.12.30 12:05
이 글을 읽어주시는 분이 1분이라도 계신게 다행입니다... ^^ |+rp+|2564|+rp2+|2567|+rp3+|acoc_board_ideatip -
아란
2006.12.30 21:24
수고하셨어요.
좋은 강의, 잘 들었어요.
p.s 이제 슬슬 잡담 하나 올릴 때가 왔군요;;|+rp2+|2571|+rp3+|acoc_board_ideatip -
Zeprod
2006.12.31 16:24
아란님 덕분에 글을 자주 올릴수 있게 돼어 다행입니다.. ^^;; |+rp+|2571|+rp2+|2573|+rp3+|acoc_board_ideatip
