추상자료형 트리

Posted on | In



개요

이번 과제는 추상자료형 트리가 무엇인지 알고 그중에서 이진 트리라는 트리의 한 종류와 그 트리중의 특정 데이터를 순회하는 방법을 직접 구현해보는 것이다.



선형 자료구조

시각적으로 볼 때 이전에 구현했던 리스트, 스택, 큐와 같은 추상 자료형은 선형 자료구조(Linear Structure)라고 부른다.

이는 데이터가 한 줄로 나열되어있다는 특징 때문에 이름을 붙인 것이다.

간단하게 각각의 노드의 관계가 1대1 관계이면 선형 자료구조이다.


선형의 사전적 의미

선형은 직선처럼 똑바른 도형, 또는 그와 비슷한 성질을 갖는 대상이라는 뜻으로, 이러한 성질을 갖고 있는 변환 등에 대하여 쓰는 용어이다.

Linear의 품사는 형용사로 명사 Line의 형용사형이다. Line은 수학적 의미로 직선이라는 뜻을 가지고 있으며 그것의 형용사형의 뉘앙스 및 의미는 충분히 유추해볼 수 있다.



비선형 자료구조

그렇다면 트리는 그 반대, 비선형 자료구조(Non-Linear structure)라고 부른다.

비선형 자료구조의 특징은 데이터를 직선처럼 한 줄이 아닌 여러 줄로 나열했다는 점이다.

간단하게 각각의 노드의 관계가 1대다 혹은 다대다 관계이면 비선형 자료구조이다.

비선형 자료구조를 사용하는 가장 큰 이유는 탐색 시간을 단축하기 위해서이다.



트리

트리는 사이클이 없는 그래프의 일종으로 볼 수 있으며 노드와 간선들로 계층 구조를 표현한 추상자료형이다.

컴퓨터 디렉토리, 기업의 조직도, 가족 관계등 계층구조로 묘사 할 수 있는 모두 트리로 나타낼 수 있다.



노드(Node)

트리의 구성요소로 트리의 데이터를 담고 있는 요소를 의미한다.

위의 그림에서는 알파벳이 써져 있는 것은 모두 노드라고 불린다.


부모/자식 노드(Parent/Child Node)

부모 자식 노드는 관계에 따라 달라지는 개념으로 B의 예를 보면 B는 A의 자식노드이면서 D와 E의 부모노드이다.

이처럼 서로 다른 계층으로 이어져 있는 노드들 간의 관계를 나타낸 것이라고 볼 수 있다.


형제/자매 노드(Sibling Node)

영어로 Sibling은 brother or sister로 한국말로 형제 노드 또는 자매 노드로 불린다. 만약을 위해 모든 표기법을 알아두자

그림에서는 B와 C는 자매 노드이다. 같은 부모에서 뻗어져 나왔으며 같은 레벨에 위치하고 있으면 자매 노드이다.


조상 노드(Ancestor Node)

특정 노드의 상위에 있는 노드들을 조상노드라고 부른다.

E의 조상 노드는 B와 A라고 할 수 있다.


후손 노드(Descendant Node)

특정 노드의 하위에 있는 노드를 후손노드라고 부른다.

A의 후손노드는 B, C, D, E 노드이다.


루트 노드(Root Node)

부모가 없는 노드를 루트노드라고 부른다. 트리의 시작점이 루트 노드이다.

그림에서는 A가 루트 노드이다.


리프 노드(Leaf Node)

자식이 없는 노드를 리프 노드라고 부른다. 트리의 종점 역할을 한다고 하여 터미널 노드(Terminal Node)라고도 불린다.

그림에서는 C, D, E가 리프노드에 해당한다.


내부 노드(Internal Node)

루트 노드와 리프 노드에 해당하지 않는 모든 노드를 내부 노드라고 부른다.


레벨(Level)

계층의 단계를 나타내는 것으로 루트노드를 레벨 0으로 하고 아래로 내려오면서 레벨 1, 2 ~으로 증가한다.

그림에서는 A는 레벨 0, B와 C는 레벨 1, D와 E는 레벨 2에 해당한다.


높이(Height)

높이는 리프 노드로부터의 최대거리를 의미한다.

그러므로 트리의 높이는 트리의 계층의 개수를 의미하며 최대 레벨의 인덱스와 일치한다.

그림에서의 트리는 레벨 2까지 있으므로 2의 높이를 가진 트리라고 부르며 B까지의 높이는 1이라고 할 수 있다.


차수(Degree)

자식노드의 개수를 의미하며 이 그림에서는 B는 2개의 차수를 가지고 있다.


서브트리(Subtree)

트리의 부분집합을 서브트리라고 한다. 특정 노드와 그 노드에 달린 모든 후손 노드를 합한 것이다.

그림에서는 B, D, E가 서브트리이다. C 자체로 서브트리라고 할 수 있다.


포레스트(Forest)

트리들의 집합을 의미한다. 그림과 같은 트리가 여러가지 있다면 그것들을 총칭하는 것이다.



이진트리(Binary Tree)

모든 노드가 자식 노드를 두개이하로 가지고 있는 트리를 이진트리라고 부른다.

이진트리는 공집합도 노드로 간주하기 때문에 아무런 노드가 없는 것도 이진트리라고 한다.

이진트리의 정의자체가 재귀적으로 자식노드로 내려가면서 리프노드까지의 모든 노드를 확인하는 것이므로 이진트리의 작업은 모두 재귀호출 형태를 띄운다.



컴파일러에서 수식을 분석을 할 때 이진트리를 이용해서 한다. 이때의 용어는 달라지는 데 파스 트리(parse tree)라고 불린다.


포화 이진트리(Full Binary Tree)



높이가 h인 이진트리에서 모든 리프노드가 레벨 h에 있는 트리를 포화 이진트리라고 부른다.

이렇게 되려면 리프노드 위쪽의 모든 노드는 반드시 자식노드 두개를 거느리고 있어야 한다.

영어단어 FULL에서 유추할 수 있듯이 완전히 꽉 찬 트리를 포화 이진트리라고 부른다.

만약 레벨 h의 경우 노드의 개수는 2^(h + 1) - 1개 이다.


완전 이진트리(Complete Binary Tree)



레벨 h-1 까지는 포화 이진 트리이고 마지막 레벨에서 왼쪽부터 리프노드를 채운 것을 완전 이진트리라고 부른다.

그림과 같이 하나라도 건너뛰고 채운다면 완전 이진 트리가 아니다.

그러므로 완전 이진트리 > 포화 이진트리이다.

완전 이진 트리는 힙을 구현할 때 사용한다.


균형트리(Height Balanced Tree)

루트노드를 기준으로 왼쪽 하위 트리와 오른쪽 하위트리 사이의 높이 차이가 1이하이면 균형트리라고 부른다.

위의 그림들은 모두 균형트리라고 할 수 있다.


편향 이진 트리는 리스트???



추상자료형 트리(ADT Tree)

  • 이진 트리 생성
  • 이진 트리 삭제
  • 루트 노드 반환
  • 왼쪽 자식 노드 추가
  • 오른쪽 자식 노드 추가
  • 왼쪽 자식 노드 반환
  • 오른쪽 자식 노드 반환
  • 트리 내부 순회



배열로 구현한 이진트리



트리를 배열로 구현할 수는 있지만 구현의 제약으로 인해 많이 사용되진 않는 방법이다.

일반적으로 루트노드는 데이터를 저장하지 않도록 구현한다.

모든 노드는 인덱스로 접근되며 판단된다. 만약 특정 노드가 삭제되었을 때 부모노드의 인덱스를 알아내기 위해 배열 전체에서 다시 탐색해야한다.

탐색에 소요되는 시간이 너무 오래 걸리기 때문에 배열에 의한 트리는 거의 사용되지 않는다.

그러나 완전 이진 트리는 간단한 계산으로 접근이 가능하므로 배열로 구현해도 효율적이다.

부모노드는 i/2, 왼쪽 자식 노드 인덱스는 2i, 오른쪽 자식 노드 인덱스는 (2i) + 1이다.



포인터로 구현한 이진트리


tree.h

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#ifndef _BIN_TREE_
#define _BIN_TREE_

typedef struct BinTreeNodeType
{
	char data;
	int visited;
	struct BinTreeNodeType* pLeftChild;
	struct BinTreeNodeType* pRightChild;
} BinTreeNode;

typedef struct BinTreeType
{
	struct BinTreeNodeType* pRootNode;
} BinTree;

BinTree* makeBinTree(BinTreeNode rootNode);	
BinTreeNode* getRootNodeBT(BinTree* pBinTree);
BinTreeNode* insertLeftChildNodeBT(BinTreeNode* pParentNode, BinTreeNode element);		
BinTreeNode* insertRightChildNodeBT(BinTreeNode* pParentNode, BinTreeNode element);
BinTreeNode* getLeftChildNodeBT(BinTreeNode* pNode);
BinTreeNode* getRightChildNodeBT(BinTreeNode* pNode);
void	deleteBinTree(BinTree* pBinTree);
void	deleteBinTreeNode(BinTreeNode* pNode);		

void	traverseDLR(BinTree *pBinTree);
void	traverseLDR(BinTree *pBinTree);
void	traverseLRD(BinTree *pBinTree);

#endif

#ifndef _COMMON_TREE_DEF_
#define _COMMON_TREE_DEF_

#define TRUE		1
#define FALSE		0

#endif




func. makeBinTree

SYNOPSIS

  • 함수 원형 : BinTree* makeBinTree(BinTreeNode rootNode);
  • BinTreeNode rootNode : 루트노드 데이터를 담고있는 인자
  • 리턴값 : 동적할당한 트리

DESCRIPTION

트리를 생성하고 루트노드를 만드는 함수

CODE

1
2
3
4
5
6
7
8
9
BinTree *newTree = malloc(sizeof(BinTree));
BinTreeNode *newNode = malloc(sizeof(BinTreeNode));
newNode->pLeftChild = NULL;
newNode->pRightChild = NULL;
newNode->visited = 0;
newNode->data = rootNode.data;

newTree->pRootNode = newNode;
return (newTree);




func. getRootNodeBT

SYNOPSIS

  • 함수 원형 : BinTreeNode* getRootNodeBT(BinTree* pBinTree);
  • BinTree* pBinTree : 트리를 가리키는 포인터 변수
  • 리턴값 : 인자로 들어온 트리의 루트노드

DESCRIPTION

인자로 넣은 트리의 루트노드를 반환하는 함수

CODE

1
2
3
if (!pBinTree)
	return NULL;
return (pBinTree->pRootNode);


func. create_BinTreeNode

SYNOPSIS

  • 함수 원형 : BinTreeNode *create_BinTreeNode(BinTreeNode *left, BinTreeNode *right, char data)
  • BinTreeNode *left : 왼쪽 자식이 가리키고 있는 곳
  • BinTreeNode *right : 오른쪽 자식이 가리키고 있는 곳
  • char data : 생성할 노드의 데이터
  • 리턴값 : 생성한 노드

DESCRIPTION

노드 한개를 생성하는 함수

CODE

1
2
3
4
5
6
7
BinTreeNode *new = malloc(sizeof(BinTreeNode));
if (!new)
	return (NULL);
new->data = data;
new->pLeftChild = left;
new->pRightChild = right;
return (new);


func. insertLeftChildNodeBT

SYNOPSIS

  • 함수 원형 : BinTreeNode* insertLeftChildNodeBT(BinTreeNode* pParentNode, BinTreeNode element)
  • BinTreeNode* pParentNode : 삽입될 노드의 부모노드
  • BinTreeNode element : 삽입될 노드의 데이터를 담고 있는 노드
  • 리턴값 : 삽입된 노드

DESCRIPTION

첫번째 인자로 넣은 부모노드의 왼쪽 자식에 두번째 인자로 넣은 노드를 삽입하는 함수

CODE

1
2
3
BinTreeNode *new = create_BinTreeNode(NULL, NULL, element.data);
pParentNode->pLeftChild = new;
return (new);


func. insertRightChildNodeBT

SYNOPSIS

  • 함수 원형 : BinTreeNode* insertRightChildNodeBT(BinTreeNode* pParentNode, BinTreeNode element)
  • BinTreeNode* pParentNode : 삽입될 노드의 부모노드
  • BinTreeNode element : 삽입될 노드의 데이터를 담고 있는 노드
  • 리턴값 : 삽입된 노드

DESCRIPTION

첫번째 인자로 넣은 부모노드의 오른쪽 자식에 두번째 인자로 넣은 노드를 삽입하는 함수

CODE

1
2
3
BinTreeNode *new = create_BinTreeNode(NULL, NULL, element.data);
pParentNode->pRightChild= new;
return (new);


func. getLeftChildNodeBT

SYNOPSIS

  • 함수 원형 : BinTreeNode* getLeftChildNodeBT(BinTreeNode* pNode)
  • BinTreeNode* pNode : 알고 싶은 노드의 부모노드
  • 리턴값 : 인자로 들어온 노드의 왼쪽 노드

DESCRIPTION

인자로 들어온 노드의 왼쪽 자식 노드를 리턴하는 함수

CODE

1
2
3
if (!pNode)
	return NULL;
return (pNode->pLeftChild);


func. getRightChildNodeBT

SYNOPSIS

  • 함수 원형 : BinTreeNode* getRightChildNodeBT(BinTreeNode* pNode)
  • BinTreeNode* pNode : 알고 싶은 노드의 부모노드
  • 리턴값 : 인자로 들어온 노드의 오른쪽 노드

DESCRIPTION

인자로 들어온 노드의 오른쪽 자식 노드를 리턴하는 함수

CODE

1
2
3
if (!pNode)
	return NULL;
return (pNode->pRightChild);


func. _deleteBinTree

SYNOPSIS

  • 함수 원형 : void _deleteBinTree(BinTreeNode *root)
  • BinTreeNode* root : 루트노드? 부모노드?
  • 리턴값 : void

DESCRIPTION

인자로 들어온 노드를 이용해서 리프노드까지 재귀로 내려가서 모든 노드를 동적해제 시켜주는 함수

CODE

1
2
3
4
5
1
2
3
4
5
if (!root)
	return ;
_deleteBinTree(root->pLeftChild);
_deleteBinTree(root->pRightChild);
free(root);


func. deleteBinTree

SYNOPSIS

  • 함수 원형 : void deleteBinTree(BinTree* pBinTree)
  • BinTree* pBinTree : 삭제할 트리
  • 리턴값 : void

DESCRIPTION

인자로 들어온 트리를 삭제하는 함수

CODE

1
2
3
4
5
1
2
3
4
5
if (!root)
	return ;
_deleteBinTree(root->pLeftChild);
_deleteBinTree(root->pRightChild);
free(root);


func. deleteBinTreeNode

SYNOPSIS

  • 함수 원형 : void deleteBinTreeNode(BinTreeNode* pNode)
  • BinTreeNode* pNode : 삭제할 노드
  • 리턴값 : void

DESCRIPTION

인자로 들어온 노드를 리프노드일때만 삭제하는 함수

CODE

1
2
3
if (pNode->pLeftChild || pNode->pRightChild)
	return ;
free(pNode);



이진 탐색트리

이진 트리를 그대로 사용하면 탐색의 시간에서 장점을 찾기 힘들기 때문에 이진 탐색트리를 만들어서 사용한다.

일종의 피봇을 세우고 재귀적으로 나눠진 상태의 트리를 이진 탐색트리라고 한다.


이진 탐색트리를 만족하기 위한 조건

  • 노드 N에 대해서 N의 왼쪽 하위트리에 있는 노드는 N보다 작고, N의 오른쪽 하위트리에 있는 노드는 N보다 크다.
  • 노드 N에 대해서 N의 왼쪽 하위 트리와 N의 오른쪽 하위트리도 이진 탐색트리이다.

이진 탐색트리의 시간복잡도