[CPP] BST(Binary Search Tree)

예전, 이런저런 사고로 정신없던 학교 생활중에
과제하던 기억이 나는데, 그때 정신없이 BST를 구현하였다. 기억에 의하면 다른 기능 구현은 간단했지만, 삭제할때가 가장 까다로웠다. 삭제할때 워낙 변수가 여러가지라 if문이 잔뜩 들어갔었다.

이것도 어느날 밤, 맥주를 마시며, 걍 끄적거리며 작성해 보았다.
(물론 기본 개념을 생각하느라 예쩐 자료구조 책좀 참고 했다.)

트리에 대해 기본적인 이론 정리~!

Degree : 한 노드에 연결된 서브트리의 개수. 가장 큰값을 Degree로 한다.
Terminal Node, Leaf Node : Degree가 0인 노드, 마지막 노드이다.
Parent Node : 현재 노드의 상위 노드
Child Node : 현재 노드의 하위 노드
Sibling : 형제라고 한다. 같은 부모를 가지고 같은 level에 있는 노드들은 형제관계이다.
Ancestor : 조상, 현재 노드부터 root까지의 부모 노드를 뜻함
Descendant : 현재 노드와 연결되 모든 subTree의 자식 노드들을 뜻함.
Level : root는 level 1로 시작한다. 한단계씩 아래로 내려갈때 마다 level이 +된다.
Depth, height : 총 level수를 뜻한다. 최대 level수.... Depth와 Level이 같은 뜻인줄 알았는데... 아니었다 -.-;
FreeTree : 한 개의 연결요소(connected conponent)로 이루어진 무방향 그래프의 특수한 형태로서, 어떤 단순 사이클(cycle)도 갖지 않는 연결 그래프의 일종인 트리를 말한다.
Ordered Tree : 같은 레벨에 있는 노드들의 좌우배열 순서가 고정되어 위치상의 의미가 중요한 트리.
Oriented Tree : 노드들의 좌우배열 순서가 일정하지 않아 위치상 무의미한 트리
Similar Tree : 임의의 두 개의 트리가 있을 때 트리를 구성하는 전체 노드수와 위치 등의 구조는 같으나 자료 부분만 다른 두 개의 트리를 닮은 트리(similar tree)라 한다.
Equivalent Tree : 같은 위치에 같은 자료를 가진 두개의 트리.
Binary Tree : 모든 노드의 Degree가 2를 넘지 않는다. 일반 트리에서는 자식들의 순서를 구별하지 않지만 이진트리는 자식들의 순서를 구별한다.
Skewed Tree : 말단 노드를 제외한 모든 노드들이 한 방향의 자식만을 가리키는 트리
Complete Binary Tree : 레벨을 i, 노드수를 n이라 할 때 (2(l-1)-1)<n<(2(l)-1)를 만족하는 트리를 말한다. 레벨이 1인 근노드로부터 시작하여 하위레벨 순으로, 레벨이 같을 경우 왼쪽에서 오른쪽으로 번호를 붙이는 방법을 사용하여 순차적인 대응이 되는 트리를 완전 이진 트리라고 한다 . Full Binary Tree는 한 레벨이 가득 찬 Tree이지만 Complete Binary Tree는 비어 있을 수 있다. 단 마지막 노드만이 비어있을 수 있다. 즉 위에서 아래로 번호를 붙였을때 마지막 노드 만이 비어있을 수 있다. 중간에 한 노드의 차수가 1일 경우에도 허용된다는 의미(마지막 노드라는 조건 하에)
Full Binary Tree : 말단 노드를 제외한 모든 노드들이 차수가 2이다. 즉 차수가 0이가나 2이다. 깊이가 i일때 전체 노드의 수는 2(i)-1이다.   (가로는 승수), 삼각형 모양을 이룬다.

트리를 만드는 방법에는 배열을 사용하는 방법도 있지만 링크드 리스트처럼 노드와 포인터를 이용하는 방법이 있다.
배열 클래스를 사용하면되지만, 필자의 경우 링크드리스트를 이용하여 트리를 구현한다.
(뭔가 동적이고 연결하는 맛이 있다고라고 할까?, 그런데 사실 배열을 이용하여 만드는 것이 Index를 이용하여 자식, 부모 노드로 자유롭게 이동이 가능하기 때문에 구현이 훨씬 편하다.)

이진탐색트리(BST)는 이진트리(Degree가 두개 이하)에 속하는 특징을 갖는 트리이다. 또한 이진트리는 공백이 가능하다.
이진탐색트리의 정의는 다음과 같다. 
1. 모든 원소는 키를 가지며, 어떠한 두 원소도 같은 값 키값을 갖지 않는다. (모든 원소는 값이 다르다.)
2. 왼쪽 서브트리(SubTree)의 키값은 그 서브트리 루트의 키보다 작다.
3. 오른쪽 서브트리에 있는 키들은 그 서브트리 루트의 키보다 크다.
4. 왼쪽 과 오른쪽 서브트리도 이진탐색트리이다.
위 정의에서 1번은 그 자체가 2, 3, 4번과 중복되는 정의이다. 그렇기 때문에 원소는 키값을 갖는다라고만 해도 된다.

작성한 BST에서는 삽입과 삭제, 출력, 경로 찾기 4가지 기능을 구현하였다.

[작성환경 : Window XP  작성툴 : Visual Studio 6.0  컴파일러 : Visual Studio 6.0  사용언어 : C++]
#include<iostream> using namespace std; class node{ public : int key; node *left; node *right; node(){ key=0; left=NULL; right=NULL; } node(int n){ key=n; left=NULL; right=NULL; } }; class tree{ public: node *root; node *current,*parent; int subnodeNum; int AllNodeNum; tree(){ root=parent=current=NULL; AllNodeNum=0; }; void insert(node *target){ current=parent=root; if(root==NULL){ root=target; return; } else{ if(!search(target->key)){ if(target->key<parent->key) parent->left=target; else parent->right=target; } else cout<<target->key<<" Already Exist"<<endl; } AllNodeNum++; return; }; node *search(int inputKey){ parent=current=root; while(current){ if(inputKey==current->key) return current; parent=current; if(inputKey<current->key) current=current->left; else current=current->right; } return NULL; }; void searchPath(int key){ current=parent=root; int *pathAry=new int[AllNodeNum]; int i=0; while(current){ if(key==current->key){ for(int j=0;j<i;j++) cout<<pathAry[j]<<"->"; cout<<current->key<<endl; delete []pathAry; return; } if(key<current->key){ pathAry[i++]=current->key; parent=current; current=current->left; } else{ pathAry[i++]=current->key; parent=current; current=current->right; } } cout<<"Key don't exist in Tree"<<endl; delete []pathAry; return; }; node *del(int key){ node *temp; temp=search(key); //calculate parent too! int nodeEdgeNum=0; if(temp==NULL){ cout<<"This key don't exist this BST"<<endl; return NULL; } else if(temp->left==NULL&&temp->right==NULL){ //Case : Node don't have child if(temp==parent&&parent==current) root=NULL; //Case : On Root, Has only 1 Node else if(parent->left==temp) parent->left=NULL; else parent->right=NULL; } else if(temp->left!=NULL&&temp->right!=NULL){ //Case : Node have 2 children node *chnode=temp->left; node *chnodeParent=temp; while (chnode->right){ chnodeParent=chnode; chnode=chnode->right; } int slot=chnode->key; //change key chnode->key=temp->key; temp->key=slot; if(chnode->left) if(chnodeParent==temp) chnodeParent->left=chnode->left; else chnodeParent->right=chnode->left; else{ if(chnodeParent==temp) chnodeParent->left=NULL; else chnodeParent->right=NULL; } AllNodeNum--; return chnode; } else{ //Case : Node have 1 child if(temp->left){ if(parent==current&&temp==root) root=temp->left; else if(parent->left==temp) parent->left=temp->left; else parent->right=temp->left; } else{ if(parent==current&&temp==root) root=temp->right; else if(parent->left==temp) parent->left=temp->right; else parent->right=temp->right; } } AllNodeNum--; return temp; }; void printTree(){ //using preorder printTree(root); cout<<endl; if(!root) cout<<"Empty Tree"<<endl<<endl; }; void printTree(node *point){ if(point){ cout<<"Key Value : "<<point->key<<endl<<"Current Node : "; cout<<point<<" Left Node : "<<point->left; cout<<" Right Node : "<<point->right<<endl; printTree(point->left); printTree(point->right); } }; }; int main(){ int select,num; node *delNode; tree *bst=new tree(); cout<<"<Binary Search Tree>"<<endl; while(1){ cout<<"========================================================"<<endl; cout<<"1. Insert"<<" 2. Delete"<<" 3. Search Path"<<" 4. Print"; cout<<" 0. Exit"<<endl; cout<<"========================================================"<<endl; cout<<"Plz Enter Num : "; cin>>select; switch(select){ case 1 :{ cout<<"Enter What you want to Insert Num : "; cin>>num; node *temp=new node(num); bst->insert(temp); break; } case 2 : cout<<"Enter What you want to Delete Num : "; cin>>num; delNode=bst->del(num); if(delNode!=NULL) delete delNode; break; case 3 : cout<<"Enter What you want to Search Num : "; cin>>num; bst->searchPath(num); break; case 4 : bst->printTree(); break; case 0 : cout<<"--------------------------------"<<endl; cout<<"Thanks for using Program GoodBye"<<endl; exit(1); break; default : cout<<"Plz Re-Enter Menu"<<endl; break; } } return 0; }

3~18 Line : Node 선언(키값과 왼쪽 SubNode와 오른쪽 SubNode 포인터 형이 존재)
19~146 Line : tree의 함수와 변수 선언, 변수로는 트리의 가장 상위부분을 나타내는 root와 이동하면서 현재 노드를 가리킬 current, 그 부모를 나타내는 parent, 총 노드개수인 AllNodeNum과 현재 아래 노드들을 가리키는 subnodeNum이 존재한다.
subnodeNum은 순위에 의한 검색에 쓰일 변수였으나, 사용하지는 않았다. subnodeNum을 이용하면 순위에 의한 탐색구현도 가능하다.
29~44 Line : Insert 함수 구현. 삽입의 경우 BST의 정의를 이용하였다. 일단 search를 통해 존재여부를 찾는데 생각해보니 search자체가 순환을 하기 때문에 프로그램자체가 느려지게 될 것이다. 아예 search가 있는 if문을 없에고 바로 검색하는 부분이 좋을 듯하다.
45~54 Line : search함수로 찾으면 해당 노드의 주소를 리턴, 아니면 Null을 리턴한다. BST의 기본적인 search이다.
55~80 Line : searchPath함수로 해당 key값의 경로를 출력한다. search함수랑 비슷하나, 경로를 지날수록 해야하는 역할이 다름으로 따로 만들어 주었다. 배열을 동적할당 하고 그 곳에 각 노드를 지나면서 값들을 기록한다. 그후 값을 찾으면 출력
81~131 Line : Delete 함수 구현. 가장 생각할 변수가 많고 복잡하다.
delete의 기본적인 알고리즘은 다음과 같다.
해당 노드를 지우면 그 위치에 올 수 있는 수는,
지울 노드의 왼쪽 SubNode의 가장 큰 값(즉 SubNode의 가장 오른쪽의 값), 또는 오른쪽 SubNode의 가장 작은 값(즉 SubNode의 가장 왼쪽 값) 둘 중에 하나이다.
이를 구분하기 위해서는 왼쪽 또는 오른쪽 상에서 적절히 비교해서 사용하면된다.
이번 delete에서는 무조건 왼쪽 SubNode에서 가장 큰 수 를 지울노드와 교환하기로 했다.
또한 노드 교환시 노드를 직접 교환하는 방법(최대 4번의 명령어 필요)과 안의 값을 교환하고 교환된 노드를 삭제해 버리는 방법이 있다. 필자는 후자의 방법을 사용하였다. (코드가 그나마 간단해져서^^;)
기본적으로 삭제에는 총 3가지의 경우가 있다.
첫번쨰는 Degree가 1개(자식노드가 1개)인 경우,
- 지울 노드의 하위 노드와 지울 노드의 부모 노드를 연결하면 된다. 단 지울노드가 루트일 경우를 고려하고, 부모노드의 왼쪽 또는 오른쪽에서 파생되었는지를 확인해야 한다.
두번째는 Degree가 2개(자식노드가 2개)인 경우,
- 두개일 경우에는 왼쪽 subNode에서 가장 큰값으로 대체한다. 이 경우 가장 큰 값은 노드가 왼쪽으로 subNode를 갖거나, 자식노드가 없는 경우밖에 없다. 지울노드를 search함수로 찾은 후에 그곳에서 다시 왼쪽에서 가장 큰 노드를 찾아야 한다. 그러기 위해 chnode와 chnodeParent를 선언하였다. 두개를 교환후에는 마지막으로 교환될 chnode가 왼쪽으로 subNode를 갖고 있는지 없는지를 체크해주어야 한다.
세번째는 Degree가 0개인 경우이다.
- 하위 노드가 없다면 단순히 삭제할 노드의 부모노드의 포인터를 NULL로 주면된다.
132~146 Line : Tree를 출력하는 부분이다. PreOrder를 이용하여 순회한다. 출력시에는 각 노드의 주소및 오른쪽과 왼쪽 가리키는 주소를 출력하여 Tree구조가 잘 이루어 졌는지 확인해 본다.

<삽입시 모습>

<삽입된 7개의 Node를 PreOrder 방식으로 출력>

<삽입된 7개의 노드와 트리 구조>

<경로찾기 기능 수행>

<근(Root)노드인 10을 삭제후 전체 Tree 출력 모습>

<그림으로 그린 10이 삭제된 후의 모습>

<15를 삭제한후 전체 Tree 출력 모습>

<그림으로 그린 15삭제 후의 모습>