10. 트리

10-1 트리

 

트리 (Tree) : 데이터 사이의 계층 관계를 나타내는 자료구조 

 

트리 구성 요소 

• 각각의 노드(node)는 가지(edge)를 통해 다른 노드와 연결된다.
• 루트 (root) : 가장 윗부분에 위치하는 노드 
• 리프 (leaf) : 트리의 가장 아랫부분에 위치하는 노드 (더이상 뻗어나갈 수 없는 마지막에 노드가 위치한다.)
• 안쪽 노드 : 루프를 포함하여 리프를 제외한 노드
• 자식 (child) : 어떤 노드로부터 가지로 연결된 아래쪽 노드 (* 노드는 자식을 여러 개 가질 수 있다.)
• 부모 (parent) : 어떤 노드에서 가지로 연결된 위쪽 노드 (* 노드는 1개의 부모를 가진다.)
• 형재 (sibing) : 같은 부모를 가지는 노드
• 조상 (ancestor) : 어떤 노드에서 가지로 연결된 위쪽의 모든 노드 
• 자손 (descendant) : 어떤 노드에서 가지로 연결된 아래쪽의 모든 노드 
• 레벨 (level) : 루트로부터 얼마나 떨어져 있는지에 대한 값 (* 0부터 시작하여 가지가 아래로 뻗어나갈 때마다 레벨이 1씩 늘어난다.)
• 차수 (degree) : 노드가 갖는 자식 수 (* 모든 노드의 차수가 n이하인 트리를 n진 트리라고 한다.)
• 높이 (height) : 루트부터 가장 멀리 떨어진 리프까지의 거리 (리프 레벨의 최댓값)
• 서브 트리 (subtree) : 트리 안에서 다시 어떤 노드를 루트로 정하고 그 자손으로 이루어진 트리 
• 널 트리 (null tree) : 노드, 가지가 없는 트리 
• 순서트리, 무순서 트리 : 형제 노드의 순서가 있는지 없는지에 따라 트리를 분류한다. 
  순서 트리 (ordered tre) : 형제 노드의 순서를 따질 때
  무순서 트리 (unordered tree) : 형제 노드의 순서를 따지지 않을 때 

 

순서 트리 탐색 방법

1) 너비 우선 탐색 (breadth-first search)

• 낮은 레벨(루트)에서 시작해 왼쪽에서 오른쪽 방향으로 검색하고 한 레벨에서의 검색이 끝나면 다음 레벨로 내려간다. 

2) 깊이 우선 탐색 (depth-first search)

• 리프까지 내려가면서 검색하는 것을 우선순위로 하는 탐색 방법 
• 리프에 도달해 더 이상 검색을 진행할 곳이 없는 경우 부모에게 돌아간다. 그런 다음 다시 자식 노드로 내려간다. 
• 두개의 자식이 있을 때, 루트 노드를 지나가는 최댓값은 3히이다. 

* 이때, 깊이 우선 탐색을 진행하면서 '언제 노드를 방문할지' 정하는 분류 방법도 세가지가 있다. 

1. 전위 순회 (Preorder) : 노드 방문 > 왼쪽 자식 > 오른쪽 자식 
2. 중위 순회 (Inorder) : 왼쪽 자식 > 노드 방문 > 오른쪽 자식 
3. 후위 순회 (Postorder) : 왼쪽 자식 > 오른쪽 자식 > (돌아와서) 노드 방문 

 

10-2 이진트리와 이진검색트리 

 

이진트리 (binary tree)

• 노드가 왼쪽 자식(왼쪽 서브 트리 left subtree)과 오른쪽 자식(오른쪽 서브 트리 right subtree)을 갖는 트리 
• 각 노드의 자식은 2명 이하만 유지해야 한다. 

 

완전 이진 트리 (complete binary tree)

• 루트부터 노드가 채워져 있으면서 같은 레벨에서는 왼쪽에서 오른쪽으로 노드가 채워져 있는 이진 트리 
• 너비 우선 탐색을 하며 각 노드에 0, 1, 2.. 값을 주면 배열에 저장하는 인덱스와 일대일로 대응한다. 
• 높이가 k인 완전이진트리가 가질 수 있는 노드의 최대값 : 2^k+1 - 1 개
  > 따라서 n개의 노드를 저장할 수 있는 완전이진트리 높이는 log n이다. 

 

* 채우다 

1. 마지막 레벨을 제외한 레벨은 노드를 가득 채운다. 
2. 마지막 레벨은 왼쪽부터 오른쪽 방향으로 노드를 채우되, 반드시 끝까지 채울 필요는 없다. 

 

이진 검색 트리 (binary search tree) 조건 

1. 어떤 노드 N을 기준으로 왼쪽 서브 트리 노드의 모든 키 값은 노드 N의 키 값보다 작아야 한다. 
2. 오른쪽 서브 트리 노드의 키 값은 노드 N의 키 값보다 커야 한다. 
3. 같은 키 값을 갖는 노드는 없다. 

• 이진검색트리를 중위순회(Inorder)하면 키 값의 오름차순으로 노드를 얻을 수 있다. 
• 또한 구조가 단순하고 이진검색과 비슷한 방식으로 검색 가능, 노드 삽입이 쉬워 폭넓게 사용된다. 

//이진검색트리 프로그램 
#ifndef ___BinTree
#define ___BinTree

#include "Member.h"

//노드를 표현하는 구조체 
//이진 검색 트리의 개별 노드는 자기 참조형 구조체인 BinNode이다. 
typedef struct __bnode {
    Member data;  //데이터
    struct __bnode *left;  //왼쪽 자식 노드에 대한 포인터
    struct __bnode *right; //오른쪽 자식 노드에 대한 포인터
} BinNode;

//검색
BinNode *Search(BinNode *p, const Member *x);

//노드 삽입
BinNode *Add(BinNode *p, const Member *x);

//노드 삭제 
int Remove(BinNode **root, const Member *x);

//모든 노드 출력
void PrintTree(const BinNode *p);

//모든 노드 삭제 
void FreeTree(BinNode *p);
#endif

//이진검색트리 프로그램 
#include <stdio.h>
#include <stdlib.h>
#include "Member.h"
#include "BinTree.h"

//BinNode형 객체를동적으로 할당 
static BinNode *AllocBinNode (void) {
    return calloc(1, sizeof(BinNode));
}

//노드 멤버 값 설정
//n이 가리키는 BinNode형 객체에 대해 멤버 값을 설정한다. 
//n이 가리키는 객체 멤버인 data, left, right에 두번째 매개변수 x가 가리키는 객체의 값 *x와 
//세번째, 네번째 매개변수의 포인터 값 left, right를 각각 대입한다. 
static void SetBinNode(BinNode *n, const Member *x, const BinNode *left, const BinNode *right) {
   n->data = *x;     //데이터
   n->left = left;   //온쪽 자식 노드에 대한 포인터
   n->right = right; //오른쪽 자식 노드에 대한 포인터 
}

//검색
//현재 선택한 노드의 키 값과 목표하는 값을 비교하면서 왼쪽 > 오른쪽으로 검색을 진행한다. 
//매개변수 p에 이진검색트리의 루트 노드 포인터를 전달한다. 
//x가 가리키는 구조체 Member형 객체와 같은 키 값을 갖는 노드를 검색한다. 
BinNode *Search (BinNode *p, const Member *x) {
   int cond;
   if(p == NULL) 
      return NULL; //검색 실패
   else if((cond = MemberNocmp(x, &p->data)) == 0)
      return p;    //검색 성공 > 해당 노드에 대한 포인터 반환 
   else if(cond < 0) 
      Search(p->left, x);   //왼쪽 서브 트리에서 검색
   else 
      Search(p->right, x);  //오른쪽 서브 트리에서 검색
}

//노드 삽입 
//x가 가리키는 Member형 객체를 트리에 삽입한다. 
//Add함수를 처음 호출할 때는 매개변수 p에 이진검색트리의 루트 노드 포인터를 전달한다. 
BinNode *Add (BinNode *p, const Member *x) {
   int cond;
   //p가 널인 경우 = 루트 노드가 없음 
   //루트 노드를 만들고 값을 설정한다. 
   //만약, 함수를 처음 호출하는 상태가 아니라면, 노드를 삽입할 위치를 제대로 찾은 것이므로 삽입할 노드를 만들고 값을 설정하면 삽입 과정이 끝난다.
   if(p == NULL) {
      p = AllocbinNode();
      SetBinNode(p, x, NULL, NULL);
   } //p가 널이 아닌 경우 3가지
   else if((cond = MemberNocmp(x, &p->data)) == 0) //1. 선택한 노드의 키 값과 삽입할 키 값이 같은 경우
      printf("오류, %d는 이미 등록되어 있습니다.\n", x->no);
   else if(cond < 0) //2. 삽입할 키 값이 선택한 노드의 키 값보다 작은 경우 
      p->left = Add(p->left, x);
   else  //3. 삽입할 키 값이 선택한 노드의 키 값보다 큰 경우 
      p->right = Add(p->right, x);
   return p;
}

//노드 삭제 
//루트만 있는 이진검색트리에서 루트 노드를 삭제하는 경우 
//루트 포인터를 널로 업데이트하기 때문에 포인터의 포인터를 매개변수로 받는다.
int Remove(BinNode **root, const Member *x) {
   BinNode *next *temp;
   BinNode **left;
   BinNode **p = root;
   
   while(1) {
      int cond;
      if(*p == NULL) {
         printf("오류, %d는 등록되어 있지 않습니다.\n", x->no);
         return -1;  //이 키는 없습니다.
      } else if((cond = MemberNocmp(x, &(*p)->data)) == 0)
         break;  //검새 성공
      else if (cond < 0)
         p = &((*p)->left);  //왼쪽 서브 트리에서 검색
      else 
         p = &((*p)->right); //오른쪽 서브 트리에서 검색
    }
    
    if((*p)->left == NULL)
       next = (*p)->right;
    else {
       left = &((*p)->left);
       while((*left)->right != NULL)
          left = &(*left)->right;
       next = *left;
       *left = (*left)->left;
       next->left = (*p)->left;
       next->right = (*p)->right;
    }
    temp = *p;
    *p = next;
    free(temp);
    
    return 0;
}

//모든 노드의 데이터 출력
//매개변수 p에 루트 노드의 포인터를 전달받는다. 
void PrintTree (const BinNode *p) {
   if(p!=NULL) {  //p가 널 포인터인지 검사 
      PrintTree(p->left);
      PrintLnMember(&p->data);
      PrintTree(p->right);
   }
}

//모든 노드 삭제
//후위 순회(postorder) 방법으로 트리를 검색하여 삭제를 진행한다. 
void FreeTree(BinNode *p) {
   if(p!=NULL) {
      FreeTree(p->left);
      FreeTree(p->right);
      free(p);
   }
}

 

* Initilize 함수 

• 루트 노드를 가리키는 BinNode형 객체를 하나 준비하고 널 값을 대입하면 되기 때문에 Initialize 함수가 필요 없다. 
• 이때 노드를 가리키는 포인터는 이진검색트리를 사용하는 main 함수에서 미리 선언한다. 

 

* Search 함수 검색 과정 

1. 루트부터 선택하여 검색 진행한다. 여기서 선택하는 노드를 p라고 한다. 
2. p가 널이면 검색 실패
3. 검색하는 값 key와 선택한 노드 p의 키 값 비교 
   1. 값이 같으면 검색 성공 (검색 종료) 
   2. key가 작으면 선택한 노드에 왼쪽 자식 노드를 대입한다. (왼쪽으로 검색 진행)
   3. key가 크면 선택한 노드에 오른쪽 자식 노드를 대입한다. (오른쪽으로 검색 진행)
4. 2번 과정으로 되돌아간다. 

 

* Add 함수 

• 노드를 삽입한 다음 트리 형태가 이진검색트리 조건을 만족해야 한다. > 알맞은 위치에 노드 삽입!
• 또한 삽입할 노드의 키와 같은 값을 가지는 노드가 이미 있다면, 노드를 삽입해선 안 된다. 

노드 삽입 과정 

1. p에 루트 포인터 대입 (루트 선택)
2. 삽입할 키 key와 p 키 값 비교 > 값이 같다면 삽입 실패 (종료)
   
   1. 값이 같지 않은 경우 : key 값이 삽입할 값보다 작으면, 
      왼쪽 자식 노드가 없는 경우에는 노드 삽입 후 종료
      왼쪽 자식 노드가 있는 경우에는 선택한 노드에 왼쪽 자식 노드 포인터를 대입한다. 
   2. 값이 같지 않은 경우 : key 값이 삽입할 값보다 크면, 
      오른쪽 자식 노드가 없는 경우에는 노드 삽입 후 종료
      오른쪽 자식 노드가 있는 경우에는 선택한 노드에 오른쪽 자식 노드 포인터를 대입한다. 
3. 2번으로 되돌아간다.

 

* 노드 삭제할 때 3가지 경우

1. 자식 노드가 없는 노드를 삭제하는 경우 

• 삭제할 노드가 부모 노드의 왼쪽 자식이면 부모의 왼쪽 포인터에 NULL 대입
• 삭제할 노드가 부모 노드의 오른쪽 자식이면 부모의 오른쪽 포인터에 NULL 대입 
• 삭제 대상인 노드 객체의 메모리 영역을 해제한다.
• 만약 순서대로 삭제하지 않고 삭제할 노드 메모리를 먼저 해제하면 부모는 해제한 메모리를 가리키게 되고 오류가 발생할 수 있다. 

2. 자식 노드가 1개인 노드를 삭제하는 경우

• 삭제 대상 노드가 부모 노드의 왼쪽 자식인 경우 : 부모의 왼쪽 포인터가 삭제 대상 노드의 자식을 가리키도록 한다. 
• 삭제 대상 노드가 부모 노드의 오른쪽 자식인 경우 : 부모의 오른쪽 포인터가 삭제 대상 노드의 자식을 가리키도록 한다. 

3. 자식 노드가 2개인 노드를 삭제하는 경우 

• 삭제할 노드의 왼쪽 서브 트리에서 키 값이 가장 큰 노드를 검색한다. 
• 검색한 노드를 삭제 위치로 옮긴다. (검색한 노드의 데이터를 삭제 대상 노드 위치로 복사한다.)
• 옮긴 노드를 삭제한다.
  만약, 옮긴 노드에 자식이 없으면 : 자식 노드가 없는 노드의 삭제 순서에 따라 노드 삭제
  만약, 옮긴 노드에 자식이 1개만 있으면 : 자식 노드가 1개 있는 노드의 삭제 순서에 따라 노드 삭제 

 

* PrintTree 함수 과정 > 이진검색트리의 데이터를 오름차순으로 출력한다. 

1. 왼쪽 포인터를 PrintTree 함수에 전달하면서 재귀적으로 호출
2. 현재 노드의 데이터 출력
3. 오른쪽 포인터를 PrintTree 함수에 전달하면서 재귀적으로 호출 

 

//이진검색트리를 사용하는 프로그램 
#include <stdio.h>
#include "Member.h"
#include "BinTree.h"

//메뉴
typedef enum {
   TERMINATE, ADD, REMOVE, SEARCH, PRINT 
} Menu;

//메뉴 선택 
Menu SelectMenu(void) {
   int ch;
   do {
      printf("(1) 삽입 (2) 삭제 (3) 검색 (4) 출력 (0) 종료 : ");
      scanf("%d", &ch);
   } while(ch < TERMINATE || ch > PRINT);
   return(Menu)ch;
}

//메인 함수 
int main(void) {
   Menu menu;
   BinNode *root = NULL; //이진검색트리의 루트 노드 포인터
   do {
      Member x;
      BinNode *temp;
      switch(menu = SelectMenu()) {
      //노드 삽입
      case ADD:
         x = ScanMember("삽입", MEMBER_NO | MEMBER_NAME);
         root = Add(root, &x);
         break;
         
      //노드 삭제 
      case REMOVE:
         x = ScanMember("삭제", MEMBER_NO);
         Remove(&root, &x);
         break;
         
      //노드 검색
      cas SEARCH:
         x = ScanMember("검색", MEMBER_NO);
         if((temp = Search(root, &x)) != NULL)
            PrintLnMember(&temp->data);
         break;
         
      //모든 노드 출력
      case PRINT:
         puts("모든 노드 출력");
         PrintTree(root);
         break;
      }
   } while(menu != TERMINATE);
   FreeTree(root);
   
   return 0;
}