트리 1

트리(Tree)의 접근

트리의 설명을 위해서 우리는 다음 사실을 알아야 한다.

"트리는 계층적 관계(Hierarchical Relationship)을 표현하는 자료구조이다."

 

위의 문장에서 "게층적 관계"가 제일 눈에 뛸 것이다. 그런데 이에 뭇지않게 관심을 둬야 할 단어가 바로 '표현'이다. 자료구조하면 보통은 무엇인가를 저장하고 꺼내는 것이 전부인것으로 이해하는 경우가 많다. 앞서 보인 선형 자료구조들은 이에 초점이 맞춰져 잇었기 때문이다 .하지만 자료구조는 근본적으로 무엇인가를 '표현'하는 도구이다. 표현을 위해서 저장과 삭제라는 기능이 제공되는 것으로 이해하는 것이 옳다.

 

트리의 ADT를 다음과 같이 바라보면은 안된다.

"데이터의 저장, 검색 및 삭제가 용이하게 정의되어 있는가?"

 

대신 다음과 같이 바라보아야 한다.

"트리의 구조로 이뤄진 무엇인가를 표현하기에 적절히 정의되어 있는가?"

 

우리는 트리를 구현한 다음에 이를 기반으로 무엇인가를 표현해 볼것이다. 

 

트리가 표현할 수 있는 것들

그렇다면 트리는 무엇을 표현하기 위한 자료구조 인가?  사실 트리도 큐 못지않게 우리 주변에서 쉽게 접근할 수 있는 자료구조 이다. 컴퓨터의 디렉터리 구조도 트리의 예가 되고, 집안의 족보나 기업 및 정부의 조직도도 트리의 예가 된다.

 

즉 가지를 늘려가며 뻗어나간다 라는 이유 때문에 트리 구조라 부른다.

 

트리를 무엇인가를 표현하는 도구라고 생각해야 한다.

 

---

트리 관련 용어의 소개

트리와 관련해서 제밥 많은 용어가 정의되어 있다. 

기본적인 트리

위의 그림을 대상으로 하여 트리와 관련된 기본적인 용어를 정리하면 다음과 같다.

노드 : node

트리의 구성요소에 해당하는 A, B, C, D, E, F 와 같은 요소

 

간선 : edge

노드와 노드를 연결하는 선

 

루트 노드 : root node

트리 구조에서 최상위에 존재하는 A와 같은 노드

 

단말 노드 : termianl node

아래로 또 다른 노드가 연결 되어 있지 않은 E, F, C, D와 같은 노드

 

내부 노드 : internal node

단말 노드를 제외한 모든 노드로 A, B와 같은 노드

 

참고로 '단말 노드'는 나무의 구조상 잎에 해당한다 하여 '잎사귀 노드(leaf node)'라고도 불리며, '내부 노드'는 단말 노드가 아니라 하여 '비단말 노드(nonterminal node)'라고도 불린다.

그리고 노드간에는 부모(parent), 자식(child), 형제(sibling)의 관계가 성립이 되어 다음과 같이 표현할 수 있다. 참고로 트리의 구조상 위에 있을 수록 촌수가 높다.

 

노드 A는 노드 B, C, D의 부모 노드(parent node)이다.

노드 B, C, D는 노드 A의 자식 노드(child node)이다.

노드 B, C, D는 부모 노드가 같으므로, 서로가 서로에게 형제 노드(sibling node)이다.

 

그런데 부모와 자식의 관계는 상대적이다. 따라서 노드 B는 노드 A의 자식 노드이지만, 동시에 노드 E와 F의 부모 노드도 된다. 

조금 더 나아가서 조상(Ancestor), 후손(Descendant)의 관계도 있다. 특정 노드의 위에 위치한 모든 노드를 가리켜 '조상 노드'라 하고, 특정 노드의 아래에 위치한 모든 노드를 가리켜 '후손 노드'라 한다. 즉 노드 A와 B는 노드 E의 조상 노드이다. 반면 노드 B, C, D, E, F는 모두 노드 A의 후손 노드이다.

---

이진 트리(Binary Tree)와 서브 트리(Sub Tree)

다음 그림을 보자 . 이 그림에서 보이듯이 큰 트리는 작은 트리로 구성이 된다. 그리고 이렇듯 큰 트리에 속하는 작은 트리를 가리켜 '서브 트리(sub tree)'라 한다.

 

다음 그림은 위의 그림에서 왼쪽의 B를 루트 노드로 하는 서브 트리를 그린 것인데, 이 그림에서 보이듯이 서브 트리의 아래에는 더 작은 서브 트리가 존재한다.

이로써 서브 트리가 무엇을 의미하는지, 그리고 트리와 서브 트리와의 관계가 어떻게 되는지 이해하였을 것이다. 그럼 이러한 이해를 바탕으로 다음 트리를 보자.

위 그림에서 보이는 트리는 우리가 중점을 두어 공부하고 구현할 '이진 트리 (binary tree)' 이다.

이진트리는 다음 두 조건을 만족해야 한다.

1. 루트 노드를 중심으로 두 개의 서브 트리로 나뉘어 진다.

2. 나뉘어진 두 서브 트리도 모두 이진 트리이어야 한다.

 

이진 트리의 조건 자체가 재귀적이기 때문에 조건에 이진트리가 등장하는 것이다.

"이진 트리가 되려면 , 루트 노드를 중심으로 둘로 나뉘는 두 개의 서브 트리도 이진 트리이어야 하고, 그 서브 트리의 모든 서브 트리도 이진 트리이어야 한다."

 

이로써 이진 트리가 되기 위한 기본 조건을 이해하였다. 그런데 이진 트리의 조건이 여기까지라면, 다음 트리는 이진트리의 조건으로 볼 수 없다. 모든 서브 트리가 이진트리로 보이지 않기 때문이다.

하지만 이것도 이진 트리가 맞다. 왜냐하면 이진트리와 관련해서 다음의 내용이 추가로 정의되어 있기 떄문이다.

"노드가 위치할 수 있는 곳에 노드가 존재하지 않는다면, 공집합(empty set)노드가 존재하는 것으로 간주한다. 물론 공집한 노드도 이진 트리의 판단에 있어서 노드로 인정한다.

 

이진 트리에서 말하는 공집합 노드, 간단히 공집합이라 불리는 것을 그림에서 보이면 다음과 같다. 그리고 이 그림은 위의 트리가 이진 트리가 되는 이유도 함께 설명하고 있다.

無는 공집합을 의미한다.

이러한 공집한 노드 덕분에 위 그림에서 서브 트리가 하나인 노드 B와 C도 , 그리고 단말 노드인 D와 E도 모두 이진 트리가 된다.

 

생각보다 이진 트리의 폭이 넓기 때문에 그 특성에 따라서 보다 세분화 된다.

 

---

포화 이진 트리(Full Binary Tree)와 완전 이진 트리(Complete Binary Tree)

이진 트리의 몇몇 분류를 소개하기에 앞서 트리 관련 용어인 '레벨(leve)'과 '높이(height)'를 소개하겠다. 트리에서는 각 층별로 숫자를 매겨서 이를 트리의 '레벨'이라 하고, 트리의 최고 레벨을 가리켜 '높이'라 한다.

 

 

위 그림에서 보이듯이 레벨이 0에서부터 시작하는 관계로 최고의 레벨과 높이가 일치하기 때문에, 최고의 레벨을 높이라 하는 것이다. 

먼저 포화 이진 트리(full binary tree) 를 소개하겠다. 

포화 이진 트리는 위 그림처럼 노드를 더 추가하려면 레벨을 늘려야 할때, 

즉 모든 레벨이 꽉 찬 이진 트리를 가리켜 '포화 이진 트리'라 한다.

 

그럼 위 그림의 포화 이진트리에 레벨을 하나 더 늘려서 레벨 3에 두개의 노드를 추가한다고 가정하자.

 

위의 트리를 가리켜 '완전 이진 트리(complete binary tree)'라 한다. 이는 포화 이진 트리 처럼 모든 레벨이 꽉 찬 상태는 아니지만, 차곡차곡 빈 틈 없이 노드가 채워진 이진 트리를 뜻한다. 그리고 여기서 말하는 '차곡 차곡 빈틈 없이 노드가 채워진 상태'가 갖는 의미는 다음과 같다.

 

"노드가 위에서 아래로, 그리고 왼쪽에서 오른쪽의 순서대로 채워졌다"

---

이진트리의 구현

 

드디어 트리를 구현할 차례가 되었다. 따라서 트리를 대표하는 이진 트리를 구현할 것이다. 그런데 이진 트리는 재귀적인 특성을 지니고 있다. 이는 앞서 보인 이진 트리의 정의에서도 확인할  수 있었다. 이진 트리의 이러한 재귀적인 특성 때문에 이진 트리와 관련된 일부 연산은 재귀호출의 형태를 띤다. 따라서 우리는 재귀적인 사고에, 그리고 재귀함수의 정의에 어느 정도 익숙한 상태이어야 한다.

 

이진 트리의 구현 방법 : 배열 기반 or 연결 리스트 기반

이진 트리 역시 배열을 기반으로도, 그리고 연결 리스트를 기반으로도 구현이 가능하다. 그러나 트리를 표현하기에는 연결 리스트가 더 유연하기 때문에 우리가 구현할 대부분의 트리는 연결 리스트를 기반으로 구현할 것이다. 그러나 이진 트리라면 , 특히 다음과 같은 특성을 갖는 완전 이진 트리 라면 배열 기반의 구현도 고려해 볼 만 하다.

"트리가 완성 된 이후부터는 그 트리를 대상으로 매우 빈번한 탐색이 이뤄진다"

 

배열은 분명  연결 리스트에 비해서 탐색이 매우 용이하고 또 빠르기 때문이다. 따라서 배열을 기반으로 이진 트리를 구성하는 방법을 간단히 소개하고, 이어서 모든 이야기의 초점을 연결 리스트 기반의 이진 트리에 맞추자.

 

위 그림의 핵심은 노드에 번호가 부여되어 있다는 점이다. 이렇듯 배열을 기반으로 이진 트리를 구현하려면 노드에 고유의 노드 번호를 부여해야 한다. 그렇다면 이 번호가 의미하는 것은 무엇일까? 이는 각 노드의 데이터가 저장되어야 하는 배열의 인덱스 값을 의미한다.

 

위 그림에서는 길이가 7인 배열을 선언하여 , 노드 번호 1부터 5까지의 노드에 저장된 데이터를 배열에 저장한 결과를 보여준다. 그림에서 데이터가 저장되는 배열의 위치는 노드 번호를 기준으로 결정하였다.

 

예를 들어 번호가 1인 루트 노드의 데이터 A는 인덱스가 1인 위치에 저장되었고, 번호가 3인 노드의 데이터 C는 인덱스가 3인 위치에 저장되었다.

 

인덱스가 0인 배열의 요소는 사용할 수도 있지만 사용하지 않는 편이 여러모로 구현에 편의를 가져다 주고, 또 실수할 확률을 낮춰주기 때문에 일반적으로 사용하지 않는다.

이로써 배열을 기반으로 하는 이진 트리의 구현이 어떻게 이뤄지는지 대략적인 이해를 갖췄을 것이다. 그럼 이번에는 연결 리스트 기반의 구현 방법을 소개하겠다.

 

그림을 보는 순간 연결 리스트 기반의 구현 방식이 바로 이해가 되었을 것이다. 이렇듯 이해가 쉬운 이유는 , 연결 리스트를 기반으로 트리를 구현할 경우 연결 리스트의 구성 형태가 트리와 일치하기 때문이다.

 

"배열 기반의 트리는 별 의미가 없는가? "

그렇지 않다. 완전 이진 트리의 구조를 갖는 '힙(heap)'이라는 자료구조는 배열을 기반으로 구현한다. 힙이 요구하는 바를 만족시키기가 배열이 훨씬 용이하기 때문이다. 

---

헤더파일에 정의된 구조체의 이해

 

먼저 이진 트리의 헤더파일을 보이겠다.

//BinaryTree.h
#ifndef __BINARY_TREE_H__
#define __BINARY_TREE_H__

typedef int BTData;

typedef struct _bTreeNode
{
	BTData data;
    struct _bTreeNode *left;
    struct _bTreeNode *right;
}BTreeNode;

BTreeNode * MakeBTreeNode(void);
BTData GetData(BTreeNode *bt);
void SetData(BTreeNode * bt, BTData data);

BTreeNode *GetLeftSubTree(BTreeNode *bt);
BTreeNode *GetRightSubTree(BTreeNode * bt);

void MakeLeftSubTree(BTreeNode *main, BTreeNode *sub);
void MakeRightSubTree(BTreeNode *main, BTreeNode *sub);

#endif

그럼 헤더파일에 대한 이야기를 시작해보자. 다음은 위의 헤더파일에 정의되어 있는 구조체 이다.

 

typedef struct _bTreeNode   //이진 트리의 노드를 표현한 구조체

{

  BTData data;

  struct _bTreeNode *left;

  struct _bTreeNode *right;

}BTreeNode;

 

이것이 헤더파일에 정의되어 있는 유일한 구조체이다. 따라서 앞서 리스트, 스택, 큐를 경험한 우리들은 위의 헤더파일을 보면서 다음과 같이 생각할 수 있다.

 

"연결 리스트를 기반으로 이진 트리를 구현하니, 노드를 표현한 구조체는 당연히 있어야 한다. 근데 왜 이진 트리를 표현한 구조체는 정의하지 않은거지?"

 

앞서 리스트 기반의 큐를 구현 할 때에는 노드를 표현한 구조체와 큐를 표현한 구조체를 각각 정의하였다. 큐 뿐만 아니라, 스택을 구현할 때에도 그랬다. 때문에 위와 같이 느끼는 것이 당연하다. 하지만 우리는 다음 사실을 알고 있다.

 

"노드가 위치할 수 있는 곳에 노드가 존재하지 않는다면, 공집합(empty set)노드가 존재하는 것으로 간주한다. 물론 공집합 노드도 이진 트리를 판단하는데 있어서 노드로 인정한다"

 

즉 자식 노드가 하나도 없는 노드도 그 자체로 이진 트리이다. 두 개의 공집합 노드를 자식 노드로 두고 있기 때문이다.

 

마찬가지로 구조체 BTreeNode는 노드를 표현함과 동시에 이진 트리를 표현한 결과가 된다. 따라서 구조체 포인터의 변수의 이름은 다음과 같이 선언될 수 있지만.

BTreeNode *pnode;

다음과 같이 포인터 변수의 이름에 tree가 들어가도 이상할 것이 없다.

BTreeNode *ptree;

 

BTreeNode는 노드의 표현결과일 뿐만 아니라 이진 트리의 표현 결과도 된다는 것을 말한다.

 

헤더 파일에 선언된 함수들의 기능

이진 트리의 구현은 의외로 간단하다. 다만 중요한 것은 앞서 설명한 이진 트리의 재귀적인 성향을 이해하는 것이다. 그럼 헤더파일에 선언된 함수의 기능을 설명하겠다. 참고로 이 함수들이 이진 트리를 만드는 도구가 된다.

 

BTreeNode *MakeBTreeNode(void);  //노드의 생성

BTData GetData(BTreeNode *bt);   //노드에 저장된 데이터를 반환

void SetData(BTreeNode *bt, BTData data);  //노드에 데이터를 저장

 

위의 세 함수는 이름이 의미하듯이 노드의 생성, 데이터의 반환 및 저장에 대한 기능을 제공한다. 특히 노드의 생성을 담당하는 MakeBTreeNode 함수는, 호출되면 다음 형태의 노드를 동적 할당 및 초기화 하여 그 주소 값을 반환한다.

 

위 그림에 표시된 물음표는 쓰레기 값을 의미한다. 즉 데이터가 저장되는 멤버 data를 대상으로 별도의 초기화를 진행하지 않는다. 그러니 왼쪽 서브 트리, 그리고 오른쪽 서브 트리를 가리키기 위한 멤버 left와  right는 NULL로 초기화 한다. 그럼 이어서 다음 두 함수를 보자.

 

BTreeNode * GetLeftSubTree(BTreeNode * bt);   //왼쪽  서브 트리 주소 값 반환

BTreeNode * GetRightSubTree(BTreeNode *bt);  //오른쪽 서브 트리 주소 값의 반환

 

위의 두 함수는 각각 인자로 전달된 이진 트리의 왼쪽 서브 트리, 그리고 오른쪽 서브 트리의 루트 노드의 주소 값을 반환하는 함수이다. 마지막으로 다음 두 함수를 보자.

 

void MakeLeftSubTree(BTreeNode * main, BTreeNode * sub);

void MakeRightSubTree(BTreeNode * main, BTreeNode * sub);

 

위의 두 함수는 서브 트리의 연결을 담당한다. 첫 번째 함수는 매개변수 sub로 전달된 트리 또는 노드를 매개변수 main으로 전달된 노드의 왼쪽 서브 트리로 연결한다.

마찬가지로 두 번째 함수는 매개변수 sub로 전달된 트리 또는 노드를, 매개변수 main으로 전달된 노드의 오른쪽 서브 트리로 연결한다. 이렇듯 이 두 함수는 연결을 담당할 뿐, 노드의 트리와 생성을 담당하지 않는다. 지금 까지 소개한 함수의 이해를 확인하기 위해서 다음 질문에 답을 해보자.

 

"노드 A, B, C를 생성해서 A를 루트로 하고, B와 C를 각각 A에 왼쪽, 그리고 오른쪽 자식 노드가 되도록 구성하려면 함수의 호출 흐름을 어떻게 가져가야 할까?"

 

위의 문장에서 말하는 대로 이진 트리를 구성하기 위한 함수의 호출 흐름은 대략 다음과 같다.

 

int main()

{
  BTreeNode * ndA = MakeBTreeNode();  //노드의 생성

  BTreeNode * ndB = MakeBTreeNode();  //노드의 생성

  BTreeNode * ndC = MakeBTreeNode();  //노드의 생성

 

  MakeLeftSubTree(ndA, ndB);  //노드 A의 왼쪽 자식 노드로 노드 B 연결

  MakeRightSubTree(ndA, ndC);  //노드 A의 오른쪽 자식 노드로 노드 C 연결

...

}

 

---

이진 트리의 ADT

 

BTreeNode * MakeBTreeNode(void);

-이진 트리 노드를 생성하여 그 주소 값을 반환한다.

 

BTData GetData(BTreeNode *bt);

-노드에 저장된 데이터를 반환한다.

 

void SetData(BTreeNOde * bt, BTData data);

-노드에 데이터를 저장한다. data로 전달된 값을 저장한다.

 

BTreeNode * GetLeftSubTree(BTreeNode * bt);

-왼쪽 서브 트리의 주소 값을 반환한다.

 

BTreeNode * GetRightSubTree(BTreeNode *bt);

-오른쪽 서브 트리의 주소 값을 반환한다.

 

void MakeLeftSubTree(BTreeNode * main, BTreeNode *sub);

-왼쪽 서브 트리를 연결한다.

 

void MakeRightSubTree(BTreeNode *main, BTreeNode * sub);

-오른쪽 서브 트리를 연결한다.

 

이진 트리의 구현

이진 트리의 구현은 의외로 쉽다. 코드도 몇 줄 안된다. 그래서 우리는 헤더파일에 정의된 구조체, 그리고 이진 트리의 재귀적인 특성을 강조해 공부한 것이다. 이것이 이해할 내용의 전부이기 때문이다.

 

//BinaryTree.h
#ifndef __BINARY_TREE_H__
#define __BINARY_TREE_H__

typedef int BTData;

typedef struct _bTreeNode
{
	BTData data;
    struct _bTreeNode *left;
    struct _bTreeNode *right;
}BTreeNode;

BTreeNode * MakeBTreeNode(void);
BTData GetData(BTreeNode *bt);
void SetData(BTreeNode * bt, BTData data);

BTreeNode *GetLeftSubTree(BTreeNode *bt);
BTreeNode *GetRightSubTree(BTreeNode * bt);

void MakeLeftSubTree(BTreeNode *main, BTreeNode *sub);
void MakeRightSubTree(BTreeNode *main, BTreeNode *sub);

#endif

//BinaryTree.c
#include <stdio.h>
#include <stdlib.h>
#include "BinaryTree.h"

BTreeNode * MakeBTreeNode (void)
{
	BTreeNode * nd = (BTreeNode *)malloc(sizeof(BTreeNode));
    nd->left = NULL;
    nd->right =NULL;
    return nd;
}

BTData GetData(BTreeNode *bt)
{
	return bt->data;
}

void SetData(BTreeNode * bt, BTData data)
{
	bt->data= data;
}

BTreeNode * GetLeftSubTree(BTreeNOde * bt)
{
	return bt->left;
}

BTreeNode * GetRightSubTree(BTreeNode * bt)
{
	return bt->right;
}

void MakeLeftSubTree(BTreeNode * main, BTreeNOde * sub)
{
	if(main->left !=NULL)
    	free(main->left);
        
   	main->left = sub;
}

void MakeRightSubTree(BTreeNode * main, BTreeNode * sub)
{
	if(main->right !=NULL)
    	free(main->right);
        
   	main->right  = sub;
}

간단하게나마 언급이 필요한 함수는 MakeLeftSubTree 와 MakeRightSubTree 정도이다. 이 두 함수의 다음 특징은 기억해 둘 필요가 있다.

 

"왼쪽 또는 오른쪽 서브 트리가 존재한다면, 해당 트리를 삭제하고서 새로운 왼쪽 또는 오른쪽 서브트리를 연결한다."

 

이는 함수 구현에 있어서 나름 의미를 부여할 수 있는 선택이다. 그런데 이 방법에는 다음과 같은 문제가 있다.

 

"한 번의 free 함수 호출이 전부이기 때문에 , 삭제할 서브 트리가 하나의 노드로 이뤄져 있다면 문제되지 않지만, 그렇지 않다면 메모리의 누수로 이어진다."

 

둘 이상의 노드로 이뤄져 있는 서브 트리를 완전히 삭제하려면 서브 트리를 구성하는 모든 노드를 대상으로 free함수를 호출해야 한다. 즉 모든 노드를 방문해야 하는 것이다. 이렇듯 모든 노드를 방문하는 것을 가리켜 '순회'라 하는데, 이진 트리의 순회는 연결 리스트의 순회와 달리 별도의 방법이 필요하다. 잠시 후에는 서브 트리 전부를 삭제하는데 필요한 '순회'의 방법을 설명할 것이다. 그럼 이진 트리의 구성의 예를 보이는 다음 main함수를 보자.

//BinaryTreeMain.c
#include <stdio.h>
#include "BinaryTree.h"

int main()
{
	BTreeNode * bt1 = MakeBTreeNode();		//노드 bt1생성
    BTreeNode * bt2 = MakeBTreeNode();		//노드 bt2생성
    BTreeNode * bt3 = MakeBTreeNode();		//노드 bt3생성
    BTreeNode * bt4 = MakeBTreeNode();		//노드 bt4생성
    
    SetData(bt1, 1);  		//bt1에 1 저장
    SetData(bt2, 2);  		//bt2에 2 저장
    SetData(bt3, 3);  		//bt3에 3 저장
    SetData(bt4, 4);  		//bt4에 4 저장
    
    MakeLeftSubTree(bt1, bt2);   		//bt2를 bt1의 왼쪽 자식 노드로
    MakeRightSubTree(bt1, bt3);  		//bt3을 bt1의 오른쪽 자식 노드로
    MakeLeftSubTree(bt2, bt4); 			//bt4를 bt2의 왼쪽 자식 노드로
    
    //bt1의 왼쪽 자식 노드의 데이터 출력
    printf("%d \n", GetData(GetLeftSubTree(bt1)));
    
    //bt1의 왼쪽 자식 노드의 왼쪽 자식 노드의 데이터 출력
    printf("%d \n", GetData(GetLeftSubTree(GetLeftSubTree(bt1))));
    
    return 0;
}
===============실행 결과==========================
2
4