4. 이진 트리 (Binary Tree)

1. 개요

[그림 1] 트리 (Tree)

"트리 (Tree)" 자료구조란 나무를 뒤집은 모습으로 계층구조를 표현하기에 적합한 자료구조이다. 맨 위의 노드가 "루트노드 (Root Node)" 라고 하며 이 노드 아래에 있는 노드들은 다시 트리 구조가 된다. 이런 구조를 "서브 트리 (Sub Tree)"라고 한다. 또한, 임의의 노드의 조상과 자손을 지칭 할 수 있는데, 임의의 노드 바로 위에 있는 노드를 "부모 노드 (Parent Node)" 라고 하고 그 바로 아래 노드들을 "자식 노드 (Children Node)"라 한다.

[그림 2] 이진 트리 (Binary Tree)

이런 트리구조에서 파생된 자료구조를 "이진트리 (Binary Tree)"라고 부르는데, 이진트리는 모든 노드들의 자식 노드가 두 개 이하인 트리를 의미한다. 이런 이진트리에서는 서브트리가 2개 이하기 때문에 서브트리는 왼쪽과 오른쪽으로 구분된다. 

이진트리를 구현하는 방법으로 < 1) 배열을 이용하여 구현 , 2) 링크드리스트를 이용하여 구현 > 두 가지가 있다. 

---

1. 배열로 구현

배열로 구현하게 될 경우, 연결리스트로 구현하는것보다 더 복잡하고 생각해야할것이 많다. 하지만 그렇다고해서 아예 안쓰이지는 않고, 힙 트리의 경우 배열로 구현하게 되는 경우가 많다. 

배열로 구현하는 방법은 다음과 같다.

우선, 0번방은 비워놓고 루트노드를 1번방으로 시작하여 내려간다. 임의의 노드를 탐색하고 싶은 경우 해당 배열 방 번호를 입력하면 된다.

[그림 2]처럼 데이터 4의 노드에서 오른쪽 자식노드(5)를 가고자 하면 => (2 x i ) + 1 을 해주면 데이터 5의 방 번호가 나온다.

정리하면, 

====================================

노드 i의 부모 노드 = i/2

노드 i의 왼쪽 자식 노드 = 2 x i

노드 i의 오른쪽 자식 노드 = ( 2 x i ) + 1

루트 노드 = 1

====================================

이다.

배열로 구현하는 방법의 장점은 시간복잡도를 줄일수 있다는 점이 있지만, 편향 이진트리의 경우 사용하지 않는 배열 원소에 대한 메모리 낭비가 발생하고, 삽입/삭제에 대한 배열의 크기 변경이 어렵다는 점이 있다.

---

2. 링크드리스트로 구현 ( Use to Linked List )

[그림 3] 링크드 리스트를 이용한 이진트리

링크드 리스트로 구현하는 방법은 배열로 구현하는것보다 더 쉽고 접근에 있어서 더 직관적이다. 하지만, 배열 구조에서만 가능한 임의 노드로의 접근이 불편(?)하다. 데이터가 커질수록 전위,후위 순회 하는 속도가 더 느려지므로 탐색시간에 있어서 링크드 리스트가 배열 구조보다 시간이 더 오래걸린다는 점이 있다.

1. 구조체 선언

typedef struct _node Node; typedef struct _node { DataType data; Node *left; Node *right; }Node; typedef struct _tree { Node *root; int nodeCnt; }Tree;

[그림 3]처럼 노드의 구조체를 코드처럼 데이터방, 노드포인터 왼쪽,오른쪽 변수를 가지는 구조체를 선언하고, 트리관리 구조체를 하나 선언한다. 트리관리 구조체를 선언하는 이유는 노드의 삽입 및 삭제 시 노드의 갯수를 저장해주는 공간의 필요와 삭제 시에 루트노드가 바뀌는 경우가 있으므로 루트노드를 지정해주기 위해 선언한다.

---

2. 트리 초기화 

void initTree(Tree *tr) { tr->root = NULL; tr->nodeCnt = 0; } 

루트노드를 NULL 값으로 초기화하고, 노드의갯수를 0으로 초기화 한다. 

3. 노드 생성 

Node *makeNode(DataType *data, Node *left, Node *right) { Node *node = (Node*)calloc(1,sizeof(Node)); if (node != NULL) { node->data = *data; node->left = left; node->right = right; } return node; }  

전달인자로 왼쪽노드와 오른쪽노드의 주소를 받아

해당 데이터를 메모리할당한 공간에 삽입해주고 왼쪽과 오른쪽의 주소값을 연결해준다.

---

3. 이진 탐색 트리 ( Binary Search Tree )

[그림 4] 이진 탐색트리 조건을 갖춘 트리

[그림 4]의 트리구조를 보면 조건이 하나 있다. 부모노드를 기준으로 왼쪽자식은 부모노드의 값보다 더 작은 값, 오른쪽 자식은 부모노드의 값보다 더 큰 값을 가지고 있다. 그 아래 서브트리도 마찬가지로 왼쪽이 작은 값 오른쪽이 큰 값을 가지는 형태로 이루어져있다.

예를 들어, [그림 4]의 "21" 데이터를 찾는다고 하면, 루트노드 10을 기준으로 하여 대/소 비교를 하며 트리 아래로 내려간다. 첫번째로 현재 노드가 찾을 값과 같은지 비교하고 같지 않으면 10과 21을 비교한다. 21이 더 크므로 오른쪽 자식으로 내려가고 그 다음 18과 비교하여 21이 더 크므로 오른쪽으로 간다. 이런 조건을 가지는 트리를 "이진 탐색 트리 (Binary Search Tree)" 라고 부른다.

다음은 그 과정을 코드로 구현한 것이다.

1. 노드 탐색

  Node *searchNode(Tree *tr, DataType *data, int(*compare)(DataType*, DataType*)) { Node *temp = tr->root; while (temp != NULL) { if (*data == temp->data) return temp; if (compare(data, &temp->data) > 0) temp = temp->right; else temp = temp->left; } return NULL; }  

배열처럼 임의의 노드를 찾기위해 방 번호를 입력하는게 아닌 임시노드를 하나 선언하여 루트노드로 지정해준 뒤 모든 노드를 이진 트리 조건에 맞춰서 순회하여 값을 찾는 방식이다.

2. 노드 삽입

 Node *addNode(Tree *tr, DataType *data, int(*compare)(DataType *, DataType*)) { Node *newNode; Node *parent = tr->root; Node *son = tr->root; newNode = makeNode(data, NULL, NULL); // 새로운노드 할당 if (newNode == NULL) // 메모리할당 실패시 리턴 return NULL; // 루트노드에 add할지 아닐지 검사 if (tr->root != NULL) // 루트노드 아닌경우 { // parent,son포인터 이용하여 값 대입할 곳 위치찾기 while (son != NULL) // son이 null이 될때까지 반복 { if (compare(data,&son->data)>0) // 대입할 값이 더 큰경우 -> 오른쪽 { parent = son; son = son->right; } else if(compare(data, &son->data)<0) // 대입할 값이 더 작은경우 -> 왼쪽 { parent = son; son = son->left; } } // 대소비교하여 노드삽입 if (compare(data, &parent->data)>0) // 오른쪽으로 parent->right = newNode; else if (compare(data, &parent->data)<0) // 왼쪽으로 parent->left = newNode; tr->nodeCnt++; // 노드카운트 ++ } else // 루트노드인 경우 { tr->root = newNode; tr->nodeCnt++; } return newNode; }  

노드 삽입은 이진탐색트리 조건에 맞춰 노드를 삽입한다. 

우선 변수로 < 1) 삽입할 새로운 노드 2) 임시로 부모노드 역할 해줄 노드 3) 임시로 자식노드 역할 해줄 노드 > 를 선언한다. 임시로 부모노드와 자식노드를 지정하는 이유는 이진탐색트리 조건에 맞춰서 대소비교를 하며 노드 아래로 내려가야 하기 때문에 노드의 주소가 바뀌지 않도록 임시변수를 지정해 주는 것이다.

부모노드, 자식노드 둘다 초기값으로 루트노드를 지정해준다.

새로운노드 메모리를 할당해준뒤, 맨 첫번째로 할 것은 삽입할 곳이 루트노드인지 루트노드가 아닌지 검사하는것이다. 이 과정은 처음만 일어나는 경우지만 이 조건이 없다면 루트노드가 수시로 바뀌어 트리의 구조가 엉망이 될 것이다.

다음으로, 부모와 자식 포인터노드를 이용하여 대입할 곳의 위치를 찾는 작업이다. 대/소 조건에 맞춰 부모노드와 자식노드를 같게 해준뒤 대입할 값보다 자식노드가 클 경우 자식노드는 자기사진의 왼쪽노드 ...작을경우 오른쪽노드로 옮긴다.

이 과정을 반복하다보면 자식노드가 null이 되는데 이때 반복문이 종료되고 현재 임시부모노드의 위치는 삽입할 곳의 부모노드 위치가 된다.

그 상태에서 마지막으로, 대소비교를하여 데이터가 부모노드 ( 현 임시부모노드위치 ) 보다 크면 오른쪽에 , 작으면 왼쪽에 삽입하는 식으로 부모노드의 오른쪽,왼쪽에 새로운노드 주소를 연결해줌으로 끝이난다.

그리고 마지막으로 노드 카운트 (갯수) 를 증가시켜준다.

---

  3. 노드 삭제

 Node *deleteNode(Tree *tr, DataType *data, int(*compare)(DataType*, DataType*)) { Node *temp = tr->root; // 삭제할 노드 임시 저장 포인터 Node *parent = tr->root; Node *child; // 삭제할 노드 위치 검색 while ((temp!=NULL)&& (temp->data != *data)) // 찾을때까지 반복 { parent = temp; if (compare(data, &temp->data) > 0) // 대입할 값이 더 큰경우 -> 오른쪽 temp = temp->right; else if (compare(data, &temp->data) < 0) // 대입할 값이 더 작은경우 -> 왼쪽 temp = temp->left; } if (temp == NULL) return temp; // 유형 1 (삭제할 노드의 오른쪽 자식이 없는 경우) if (temp->right == NULL) { child = temp->left; // 삭제할 노드의 왼쪽자식을 임시포인터 child에게 준다 if (compare(data, &parent->data) > 0) // 삭제할 노드가 삭제할노드의부모보다 컸다면 parent->right = child; // 삭제할노드부모노드 오른쪽에 child 붙인다 else // 삭제할 노드가 삭제할노드의부모보다 작았다면 parent->left = child; // 삭제할노드부모노드 왼쪽에 child 붙인다 } // 유형 2 (삭제할 노드의 오른쪽 자식의 왼쪽자식이 없는 경우) else if (temp->right->left == NULL) { child = temp->right; // 삭제할 노드의 오른쪽자식을 임시포인터 child에게 준다 if (compare(data, &parent->data) > 0) // 삭제할 노드가 삭제할노드의부모보다 컸다면 { parent->right = child; // 삭제할노드부모노드 오른쪽에 child 붙인다 child->left = temp->left; } else // 삭제할 노드가 삭제할노드의부모보다 작았다면 { parent->left = child; // 삭제할노드부모노드 왼쪽에 child 붙인다 child->left = temp->left; } } // 유형 3 (그 외 모든 경우) else { Node *tempp; tempp = temp; child = temp->right; while (child->left != NULL) // child노드의 왼쪽이 없을때까지 탐색 { tempp = child; child = child->left; } tempp->left = child->right; if (temp == tr->root) // 삭제하려는 노드가 루트노드랑 같은경우 { tr->root = child; tr->root->right = temp->right; tr->root->left = temp->left; } else // 루트노드가 아닌경우 { temp = child; // 삭제한 자리에 child값 주고 child->right = temp->right; // 노드 이어줌 child->left = temp->left; } } free(temp); return parent; }  

노드를 삭제하는 과정은 꽤나 까다롭다. 링크드 리스트나 스택, 큐 자료구조와 달리 계층구조로 이루어져 있기 때문에 임의의 한 노드를 삭제한다고 하면 그 임의의노드의 부모노드, 자식노드, 경우에 따라 루트노드까지 바꿔주어야하기 때문에 고려할것이 많다.

그 수많은 케이스를 3분류로 나눌 수 있는데 그것은 아래와 같다.

==================================================

Case 1 : 삭제할 노드의 오른쪽 자식이 없는 경우

Case 2 : 삭제할 노드의 오른쪽 자식의 왼쪽 자식이 없는 경우

Case 3 : 그 외의 모든 경우

==================================================

우선 삭제하기 전 노드삽입때와 마찬가지로 몇 가지 변수를 선언해주어야 한다. 

< 1) 삭제할 노드의 부모노드 2) 삭제할 노드대신 자식역할을 할 노드 3) 삭제할 노드 > 이다.  1)과 3)의 변수를 루트노드의 주소로 초기화 시켜준다.

처음으로 삭제 할 노드를 찾기 위해 반복문을 설정해준다. 과정은 노드탐색 함수와 비슷하게 대소비교를 하며 탐색한다. 탐색이 완료되면 3) 삭제할 노드 변수에는 삭제할 노드의 주소가 지정돼있을것이고 1) 부모노드 에는 삭제할 노드의 부모노드의 주소가 지정이 됐을것이다.

다음은 Case를 분류한다.

유형 1의 경우 간단하므로 2) 자식노드 변수에 삭제할 노드의 왼쪽주소를 넣어준다.

유형 2의 경우 삭제할 노드의 오른쪽 자식이 자식노드 역할을 한다. 자식노드에 삭제할 노드 (del)의 오른쪽 주소를 넣어주고 삭제할 노드의 왼쪽노드랑 연결해 주어야하므로 자식노드의 왼쪽에 삭제할 노드 (del)의 왼쪽주소를 넣어준다.

유형 3의 경우는 1,2의 경우를 제외한 모든 경우를 뜻하는데, 이 케이스가 가장 많고 생각해내기가 좀 까다롭다. 간단히 말하면 삭제를 하고하 하는 노드가 자식을 모두 가지고 있는 경우이다.

[그림4] 를 예시로 들어 설명하겠다.

[그림 4] 이진 탐색트리 조건을 갖춘 트리

예를들어, 10값을 가진 노드를 삭제한다고 가정하자. 10노드를 삭제하게 되면 10의 자리에는 어떤 값이 들어가야 할까? 이진탐색트리의 조건에 맞춰서 6보다는 크고 18보다는 작아야 한다. 그 값은 두 가지로 구할수 있다. 하나는 삭제하고자 하는 노드의 왼쪽노드 부분에서 최대값을 찾는 것이고 하나는 삭제하고자 하는 노드의 오른쪽노드 부분에서 최솟값을 찾는것이다. 전자는 "8" 이 될 것이고 후자의 경우 "15" 가 될 것이다.

여기서는 후자의 경우 ( 최소값찾기 ) 로 설명하겠다.

임시노드 temp를 하나 선언해준다. temp값에는 삭제할 노드 (del)의 오른쪽 주소로 초기화해준다. 그리고 오른쪽노드 부분에서 최소값을 찾기위해 반복문을 설정하는데 최소값은 왼쪽 노드로 계속 이동해야하므로 왼쪽노드가 null 이 될 때까지 반복문을 설정한다. 모두 끝나면 temp는 최솟값을 담고있는 노드의 부모노드 주소를 가지고 있게된다. 2) 자식노드 (son) 에도 temp의 왼쪽주소값을 지정해준다. ( 최소값 노드 )

이제 "10"의 위치에 2) 자식노드 (son)을 넣어주어야 하므로 son의 왼쪽에 "10"의 왼쪽노드주소, son의 오른쪽에 "10"의 오른쪽노드주소를 주며 인수인계 작업을 해준다.

마지막으로 free함수를 이용하여 del 노드를 메모리 해제하며 끝낸다.

 4. 노드 붕괴

  void destroyTree(Tree *tr, void(*print)(DataType *)) { postorderDelete(tr->root, print); tr->nodeCnt = 0; tr->root = NULL; }  

이 함수는 트리의 모든 노드를 소멸시키는 함수로 후위순회를 해주며 각 노드마다 free() 메모리 해제를 해주며 순차적으로 없애나간다.

5. 후위 순회식 노드 삭제

void postorderDelete(Node *np, void(*print)(DataType *)) { if (np != NULL) { postorderTraverse(np->left, print); postorderTraverse(np->right, print); print(&np->data); free(np); // 노드 삭제 } printf("\n\n"); }

노드붕괴함수에 연계되는 함수로 후위순회의 방식을 따르면서 추가로 free() 메모리해제를 해준다.

---

4. 노드 순회 ( Traversal )

[그림 5] 순회 과정

"순회 (Traversal)" 란 이진트리의 모든 노드를 특정한 순서대로 한 번씩 방문하는 것이다. 순회방법으로는 

< 1) 전위순회 (Pre Order) 2) 중위순회 (In Order) 3) 후위순회 (Post Order) > 방식이 있다. 

  1. 전위순회

  void preorderTraverse(Node *np, void(*print)(DataType *)) { if (np != NULL) { print(&np->data); preorderTraverse(np->left, print); preorderTraverse(np->right, print); } }

 전위순회는 루트노드를 먼저 방문하고 왼쪽 서브트리, 오른쪽 서브트리 순으로 방문하는 방법이다. 왼쪽서브트리를 모두 방문하고 왼쪽방이 더 이상 없으면 그 이전 노드로 돌아가 오른쪽 노드를 탐색하고 왼쪽,,,또 오른쪽..이런 순으로 방문한다.

  2. 중위순회 

 void inorderTraverse(Node *np, void(*print)(DataType *)) { if (np == NULL) return; inorderTraverse(np->left, print); print(&np->data); inorderTraverse(np->right, print); }  

중위순회는 먼저 왼쪽부터 방문한 뒤 루트노드를 탐색하고 오른쪽 서브트리를 방문한다.

  3. 후위순회

  void postorderTraverse(Node *np, void(*print)(DataType *)) { if (np == NULL) return; postorderTraverse(np->left, print); postorderTraverse(np->right, print); print(&np->data); }  

후위순회는 왼쪽 서브트리, 오른쪽 서브트리, 그리고 마지막에 루트노드를 방문한다.