트리(Tree) (C)

용어

• 트리는 노드(node)와 가지(edge)로 구성한다.
• 가장 윗부분의 노드를 루트(root)라고 한다.
• 가장 아랫부분의 노드를 리프(leaf)라고 한다.
• 한 노드로부터 연결된 아래쪽 노드를 자식(child)이라고 한다.
• 반대는 부모(parent)이다.
• 같은 부모를 가지는 노드는 형제(sibling)이다.
• 위쪽 노드를 모두 조상(ancestor)이라고 한다.
• 아래쪽 노드를 모두 자손(descendant)라고 한다.
• 루트로부터 얼마나 떨어져 있는지에 대한 값을 레벨(level)이라고 한다. 루트의 레벨은 0이다.
• 노드가 가지는 자식의 수를 차수(degree)라고 한다.
• 루트부터 가장 먼 리프까지의 거리를 높이(height)라고 한다.
• 트리 안에서 어떤 노드를 루트로 정하고 그 자손으로 이루어진 트리를 서브트리(subtree)라고 한다.
• 노드, 가지가 없는 트리를 널 트리(null tree)라고 한다.
• 형제간의 순서가 다른것을 다른 트리로 보는 순서 트리(ordered tree)와 같은 것으로 보는 무순서 트리(unordered tree)가 있다.

순서 트리 탐색

너비 우선 탐색(breadth-first Search)

낮은 레벨에서 시작해 지그재그 방향으로 탐색하는 방법이다.

깊이 우선 탐색(depth-first Search)

리프까지 내려가면서 검색하는 것을 우선순위로 하는 탐색 방법이다. 리프에 도달하면 부모에게 돌아간다. 다시 다른 리프쪽으로 내려가며 이를 반복한다. 이런 특성상 하나의 노드를 여러번 지나가게 되는데 이를 세종류로 나눈다.
1. 전위 순회(Preorder)
노드 방문 -> 왼쪽자식 -> 오른쪽자식 의 방법으로 탐색을 진행한다. (A->B->C)
2. 중위 순회(Inorder)
왼쪽자식 -> 노드 방문 -> 오른쪽자식 순으로 탐색을 진행한다. (B->A->C)
3. 후위 순회(Postorder)
왼쪽자식 -> 오른쪽자식 -> 노드 방문 순이다. (B->C->A)

이진트리

노드가 왼쪽 자식과 오른쪽 자식 총 둘(혹은 이하)의 자식을 갖는 트리를 이진트리(binary tree)라고 한다.
특징은 왼쪽 자식과 오른쪽 자식을 구분한다는 점이다.

완전이진트리

루트로부터 노드가 채워져 있으며, 같은 레벨에서는 왼쪽에서 오른쪽으로 노드가 채워져 있는 이진트리를 완전이진트리(complete binary tree)라고 한다.
1. 마지막 레벨이 아니라면 노드를 가득 채운다. 2. 마지막 레벨은 왼쪽부터 노드를 채운다. 의 방식으로 채우면 된다.

높이가 k인 완전이진트리가 가질 수 있는 노드의 최댓값은 2^(k+1)-1개 이다. 따라서 n개이 노드를 저장할 수 있는 완전이지느리의 높이는 log n이다.

이진검색트리

이진검색트리(binary Search tree)는 이진트리가 다음 조건을 만족하면 된다.
1. 어떤 노드 N을 기준으로 왼쪽 서브 트리 노드의 모든 키 값은 노드 N의 키 값보다 작아야 한다.
2. 오른쪽 서브 트리 노드의 키 값은 노드 N의 키 값보다 커야한다.
3. 같은 키 값을 갖는 노드는 없다.

이런 특징을 갖는 이진검색트리를 중위 순회 방식으로 탐색하면 값의 오름차순으로 노드를 얻을 수 있다. 그리고 구조가 단순하며 노드의 삽입이 쉽다는 장점 때문에 폭넓게 사용된다고 한다.

구현

구조체는 다음과 같다.

typedef struct __bnode {
	Member data; //데이터
    struct __bnode* left; //왼쪽 자식 노드에 대한 포인터
    struct __bnode* right; //오른쪽 자식 노드에 대한 포인터
} BinNode;

함수는 다음과 같다. 선언문은 생략했다.

#include <stdio.h>
#include <stdlib.h>
#include "Member.h"
#include "BinTree.h"

//노드를 동적으로 할당
static BinNode* AllocBinNode() {
	return calloc(1, sizeof(BinNode));
}

//노드의 멤버 값 설정
static void SetBinNode(BinNode* n, const Member* x, const BinNode* left, const BinNode* right) {
	n->data = *x;
    n->left = left;
    n->right = right;
}

//따로 Initialize가 필요 없다. BinNode형 객체를 하나 준비하고 null값을 대입하면 되기 때문이다.

//검색
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);
}

삽입하는 Add함수
1. p에 루트 포인터를 대입한다.(루트 포인터 선택)
2. 삽입할 키 key와 p의 키 값을 비교함. 같다면 삽입에 실패->종료
(1) key값이 삽일할 값보다 작다.
왼쪽 자식 노드가 없을 경우, 삽입 후 종료.
왼쪽 자식 노드가 있을 경우, 선택한 노드에 왼쪽 자식 노드 포인터를 대입한다.
(2) key값이 삽입할 값보다 크다.
오른쪽 자식이 없는 경우, 삽입 후 종료.
오른쪽 자식이 있는 경우, 선택한 노드에 오른쪽 자식 노드 포인터 대입.

코드는 다음과 같다.

BinNode* Add (BinNode* p, const Member* x) {
	int cond;
    if(p == NULL) {
    	p = AllocBinNode();
        SetBinNode(p, x, NULL, NULL);
    }
    else if((cond = MemberNocmp(x, &p->data)) ==0)
    	printf("-1");
    else if(cond < 0)
    	p->left = Add(p->left, x);
    else
    	p->right = Add(p->right, x);
    return p;
}

삭제하는 Remove 함수
1. 자식 노드가 없는 노드를 삭제하는 경우
부모노드의 삭제할 노드 방향의 포인터를 null로 업데이트한다.
2. 자식 노드가 1개인 노드를 삭제하는 경우
부모노드의 삭제할 노드 방향의 포인터를 자식을 가리키도록 업데이트한다.
3. 자식 노드가 2개인 노드를 삭제하는 경우
(1) 삭제할 노드의 왼쪽 서브 트리에서 키 값이 가장 큰 노드를 검색한다.
(2) 검색한 노드를 삭제 위치로 복사한다.
(3) 옮긴 노드를 삭제한다. (재귀)

코드는 다음과 같다.

int Remove (BinNode** root, const Member* x) {
	BinNode* next* temp;
    BinNode** left;
    BinNode** p = root;
    
    while(1) {
    	int cond;
        if(*p == NULL) {
        	printf("-1");
            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;
}

• Remove 함수 매개변수의 자료형은 BinNode**이다. 그 이유는 루트만 있는 이진검색트리에서 루트 노드를 삭제하는 경우, 루트 포인터를 null로 업데이트 해야하기 때문이다.

//모든 데이터를 출력
void PrintTree (const BinNode* p) {
	if(p != NULL) {
    	PrintTree(p->left);
        PrintMember(&p->data);
        PrintTree(p->right);
    }
}

//모든 노드를 삭제
void FreeTree (BinNode* p) {
	if(p != NULL) {
    	FreeTree(p->left);
        FreeTree(p->right);
        free(p);
    }
}