10. 트리

10-1. 트리

트리란?

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

순서 트리 탐색

1. 우선 탐색(breadth-first Search)

낮은 레벨에서 시작해 왼쪽에서 오른쪽 방향으로 검색하고 한 레벨에서의 검색이 끝나면 다음 레벨로 내려감

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

리프까지 내려가면서 검색하는 것을 우선순위로 하는 탐색 방법

리프에 도달해 더 이상 검색을 진행할 곳이 없는 경우 부모에게 돌아간 뒤 다시 자식 노드로 내려감
깊이 우선 탐색에서 가능한 방문 종류

2-1. 전위 순회(Preorder)

노드 방문 -> 왼쪽 자식 -> 오른쪽 자식

A->B->D->H->E->I->J->C->F->K->L->G

2-2. 중위 순회(Inorder)

왼쪽 자식 -> 노드 방문 > 오른쪽 자식

H->D->B->I->E->J->A->K->F->L->C->G

2-3. 후위 순회(Preorder)

왼쪽 자식 -> 오른쪽 자식 -> (돌아와) 노드 방문

H->D->I->J->E->B->K->L->F->G->C->A

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

이진트리

노드가 왼쪽 자식과 오른쪽 자식을 갖는 트리
각 노드의 자식은 2명 이하만 유지해야 함

이진트리는 왼쪽 자식과 오른쪽 자식을 구분함

완전이진트리

루트부터 노드가 채워져 있으면서 같은 레벨에서는 왼쪽에서 오른쪽으로 노드가 채워져 있는 이진트리

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

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

이진검색트리(binary Search tree)

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

이진검색트리를 중위 순회하면,
1. 키 값의 오름차순으로 노드를 얻을 수 있음
2. 구조가 단순함
3. 이진검색과 비슷한 방식으로 검색이 가능함
4. 노드의 삽입이 쉬움

이진검색트리 만들기

/* 이진검색트리 프로그램(헤더) */
#ifndef ___BinTree
#define ___BinTree

#include "Member.h"

/*--- 노드 ---*/
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

노드를 표현하는 구조체 BinNode

• data : 회원 데이터
• left : 왼쪽 자식 노드에 대한 포인터
• right : 오른쪽 자식 노드에 대한 포인터

노드를 생성하는 AllocBinNode 함수

BinNode형 객체를 만드는 함수

static BinNode *AllocBinNode(void)
{
	return calloc(1, sizeof(BinNode));
}

노드 멤버의 값을 설정하는 SetBinNode 함수

BinNode형 객체의 멤버 값을 설정하는 함수
첫 번째 매개변수 n이 가리키는 BinNode형 객체에 대한 멤버의 값 설정

static void SetBinNode(BinNode *n, const Member *x, const BinNode *left, const BinNode *right)
{
	n->data = *x;			/* 데이터 */
	n->left = left;			/* 왼쪽 포인터 */
	n->right = right;		/* 오른쪽 포인터 */
}

n이 가리키는 객체 멤버인 data, left, right에 두 번째 매개변수 x가 가리키는 객체의 값 *x와 세 번째, 네 번째 매개변수의 포인터 값 left, right를 각각 대입

비어 있는 상태의 이진검색트리 만들기

해시법과 선형 리스트 프로그램과 달리 빈 테이블이나 리스트를 만드는 Initialize 함수가 없음. 루트 노드를 가리키는 BinNode형 객체를 하나 준비하고 NULL값을 대입하면 되기 때문. 이때 루트 노드를 가리키는 포인터는 이진검색트리를 사용하는 main 함수에서 미리 선언

키 값으로 검색하는 Search 함수

이진검색트리에서의 검색 알고리즘
1. 루트부터 선택하여 검색 진행. 여기서 노드 선택(p)
2. p가 NULL이면 검색 실패
3. 검색하는 값 key와 선택한 노드 p의 키 값을 비교하여

• 값이 같으면 검색에 성공(검색 종료)
• key가 작으면 선택한 노드에 왼쪽 자식 노드를 대입(왼쪽으로 검색 진행)
• key가 크면 선택한 노드에 오른쪽 자식 노드를 대입(오른쪽으로 검색 진행)

4 . 2번 과정으로 되돌아감

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); 			/* 오른쪽 서브 트리에서 검색 */
}

이 함수를 호출하면서 매개변수 p에 이진검색트리의 루트 노드 포인터 전달,
이후 x가 가리키는 구조체 Member형 객체와 같은 키 값을 갖는 노드 검색
검색에 성공하면 해당 노드에 대한 포인터 반환

노드를 삽입하는 Add 함수

[주의] 노드를 삽입한 다음에 트리의 형태가 이진검색트리의 조건을 유지해야 함. 따라서 노드를 삽입할 때는 알맞은 위치에 삽입해야 함. 이때 삽입할 노드의 키와 같은 값을 가지는 노드가 이미 있다면 노드를 삽입해서는 안 됨

p를 루트로 하는 이진검색트리에 키 값이 key인 데이터를 삽입하는 알고리즘
1. p에 루트 포인터를 대입(루트 선택)
2. 삽입할 키 key와 p의 키 값을 비교함. 값이 같다면 삽입 실패(종료)

• 값이 같지 않은 경우 key 값이 삽입할 값보다 작으면
  왼쪽 자식 노드가 없는 경우[a]에는 노드 삽입(종료)
  왼쪽 자식 노드가 있는 경우 선택한 노드에 왼쪽 자식 노드 포인터 대입
• key 값이 삽입할 값보다 크면
  오른쪽 자식 노드가 없는 경우[b]에는 노드 삽입(종료)
  오른쪽 자식 노드가 있는 경우에는 선택한 노드에 오른쪽 자식 노드 포인터 대입

3 . 2로 되돌아감

BinNode *Add(BinNode *p, const Member *x)
{
	int cond;
    
    	/* [1] */
	if (p == NULL) {			
		p = AllocBinNode();		
		SetBinNode(p, x, NULL, NULL);
	}
    
    	/* [2] */
	else if ((cond = MemberNoCmp(x, &p->data)) == 0)	// [3]
		printf("【오류】 %d는 이미 등록되어 있습니다.\n", x->no);
	else if (cond < 0)					// [4]
		p->left = Add(p->left, x);
	else							// [5]
		p->right = Add(p->right, x);
        
	return p;
}

[1] p가 NULL인 경우
처음 Add 함수 호출 시 NULL이면 루트 노드가 없다는 뜻(이진검색트리가 비어 있음),
따라서 루트 노드를 만들고 값을 설정함

함수를 처음 호출하는 상태가 아니라면 노드를 삽입할 위치를 제대로 찾은 것

[2] p가 NULL이 아닌 경우

• [3] 선택한 노드의 키 값과 삽입할 키 값이 같은 경우
  값을 삽입할 수 없음. 삽입할 수 없다는 내용 출력
• [4] 삽입할 키 값이 선택한 노드의 키 값보다 작은 경우
  선택한 노드에 왼쪽 자식 노드 대입. Add 함수에 왼쪽 자식 노드를 전달하며 재귀 호출
• [5] 삽입할 키 값이 선택한 노드의 키 값보다 큰 경우
  선택한 노드에 오른쪽 자식 노드 대입. Add 함수에 오른쪽 자식 노드를 전달하며 재귀 호출

노드를 삭제하는 Remove 함수

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

• 삭제할 노드가 부모 노드의 왼쪽 자식이면 부모의 왼쪽 포인터를 NULL로
• 삭제할 노드가 부모 노드의 오른쪽 자식이면 부모의 오른쪽 포인터를 NULL로

이후 삭제 대상인 노드 객체의 메모리 영역을 해제
이 순서로 삭제를 진행하지 않고 삭제할 노드의 메모리를 먼저 해제하면 부모는 해제한 메모리의 주소를 가리킴

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

• 삭제 대상 노드가 부모 노드의 왼쪽 자식인 경우,
  부모의 왼쪽 포인터가 삭제 대상 노드의 자식을 가리키도록 함
• 삭제 대상 노드가 부모 노드의 오른쪽 자식인 경우,
  부모으 ㅣ오른쪽 포인터가 삭제 대상 노드의 자식을 가리키도록 함

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

1. 삭제할 노드의 왼쪽 서브 트리에서 키 값이 가장 큰 노드 검색
2. 검색한 노드를 삭제 위치로 옮김(검색한 노드의 데이터를 삭제 대상 노드 위치로 복사)
3. 옮긴 노드 삭제

• 옮긴 노드에 자식이 없으면,
  '자식 노드가 없는 노드의 삭제 순서'에 따라 노드 삭제
• 옮긴 노드에 자식이 1개만 있으면,
  '자식 노드가 1개 있는 노드의 삭제 순서'에 따라 노드 삭제

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;
}

루트만 있는 이진검색트리에서 루트 노드를 삭제하는 경우에는 루트 포인터를 NULL로 업데이트하기 때문에, Remove 함수의 첫 번째 매개변수의 자료형은 BinNode**

모든 노드를 출력하는 PrintTree 함수

모든 노드를 오름차순으로 출력하는 함수

void PrintTree(const BinNode *p)
{
	if (p != NULL) {
		PrintTree(p->left);
		PrintLnMember(&p->data);
		PrintTree(p->right);
	}
}

중위 순회의 방법으로 트리 검색

매개변수 p가 NULL포인터라면 아무것도 하지 않고 호출한 위치로 돌아감
그렇지 않다면,

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

이진검색트리의 데이터를 오름차순으로 출력

모든 노드를 삭제하는 FreeTree 함수

모든 노드를 삭제하는 함수

void FreeTree(BinNode *p)
{
	if (p != NULL) {
		FreeTree(p->left);
		FreeTree(p->right);
		free(p);
	}
}

후위 순회 방법으로 트리를 검색하며 삭제 진행