트리(tree)란?
트리 구조란 정보의 항목들이 가지로 연결될 수 있게 데이터가 조작되는 것이며, 가계표, 족보, 왕조의 나열 등에서 쉽게 찾아볼 수 있다.
가계표를 예를 들어 설명을 하면 최 상단에 조부모님이 계시고 그 아래로 아버지와 어머니, 동생 친척들이 쭉 나열이 되는데, 이러한 조직 체계를 트리를 통해 나타낼 수 있다.
트리 구조에서 노드 란 각 항목들을 의미하며 한 정보 아이템에서 다른 노드로 뻗어진 가지를 포함한 개념이다.
각 노드는 아래로 계속해서 가지를 뻗어나갈 수 있는데, 한 노드에서 뻗어져 나간 가지들(서브트리) 의 수를 그 노드의 차수 라고 부른다.
또한, 차수가 0인 노드를 리프 혹은 단말 노드 라고 부르며, 뻗어나간 구조의 상위의 노드를 아래 노드의 부모(parent) 라 하고 아래 노드를 상위 노드의 자식(child) 이라고 부른다. 또한 한 노드에서 뻗어져 나온 병렬관계의 노드를 서로의 형제(sibling) 이라고 부른다.
특정 노드의 차수와 구분하여 트리의 차수 트리에 있는 노드의 최대 차수를 말한다.
이진 트리
다시 가계표의 예를 들면 한 부모 밑에는 수많은 자식들이 생길 수 있으나, 컴퓨터가 이를 처리하는 시점에서 특정 부모노드 아래에 숫자를 알 수 없는 자식들이 존재하게 된다면 포인터 필드가 가변적이기에 효율적으로 메모리를 사용할 수 없다. 이 때문에 일정한 크기의 노드를 사용하기 위한 트리의 표현법이 나타나게 되었고, 한 노드가 가지만을 가지도록 만들어진 트리를 이진 트리 라고 한다.
제일 위의 노드(root)로 부터 2배씩 증가하며 가지들이 뻗어나와 크리스마스 트리 형태를 띄는 형태를 이진트리라고 부르며 모든 노드들이 규칙적으로 2개씩 가지를 쳐 나가 각 층의 노드가 꽉꽉 들어차면 이를 포화 이진 트리 라고 한다.
깊이가 k인 포화 이진트리의 노드 수는 (2^k-1)개 이다.
컴퓨터에서는 이러한 이진트리를 메모리에 저장할 방법을 찾게 되었고 최 상단 노드부터 차례로 메모리에 저장을 하게 되면 포화 이진트리가 아닌 대부분의 이진트리에서는 메모리 중간 중간이 비게 되어 효율적인 메모리 사용에 어려움을 겪게 되었는데, 이를 해결하기 위해 열결표현 방식을 사용하여 각 노드가 다른 노드의 링크를 연결하여 포인터를 들고 있는 방식으로 저장하게 되었다.
어떠한 트리도 이진 트리로 표현할 수 있다.
다음은 C 언어를 이용한 이진 트리의 구현이다.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
39
40
41
42
43
44
45
46
47
48
49
50#include <stdlib.h>
#include <stdio.h>
/*node 구조체로 *treePointer 라는 별칭 선언*/
typedef struct node *treePointer;
/*node 구조체를 선언한다.*/
typedef struct node{
char data;
treePointer leftChild, rightChild;
} node;
treePointer createNode(char newData)
{
treePointer newNode = (treePointer)malloc(sizeof(node));
newNode->leftChild = NULL;
newNode->rightChild = NULL;
newNode->data = newData;
return newNode;
}
void inorder(treePointer ptr)
{
if(ptr){
inorder(ptr->leftChild);
printf("%c", (*ptr).data);
inorder(ptr->rightChild);
}
}
/*추가된 노드를 출력하는 부분*/
int main()
{
treePointer nodeA = createNode('A');
treePointer nodeB = createNode('B');
treePointer nodeC = createNode('C');
treePointer nodeD = createNode('D');
treePointer nodeE = createNode('E');
treePointer nodeF = createNode('F');
treePointer nodeG = createNode('G');
treePointer nodeH = createNode('H');
(*nodeA).leftChild=nodeB;
(*nodeA).rightChild=nodeC;
(*nodeB).leftChild=nodeD;
(*nodeB).rightChild=nodeE;
(*nodeD).rightChild=nodeG;
(*nodeC).leftChild=nodeF;
(*nodeF).rightChild=nodeH;
inorder(nodeA);
}
이진 트리 순회
앞서 설명한 이진 트리를 조회하기 위해서 다양한 방법을 사용하는데, 한 노드에서 왼쪽으로 이동(L), 오른쪽으로 이동(R), 노드 방문(V) 의 순서에 따라 중위 순회, 후위 순회, 전위 순회로 구분한다.
먼저 전위 순회(preorder traversal) 는 이름 그대로 노드를 먼저 방문하는 경우 즉, VLR의 순서로 노드를 방문하는 경우이다.
후위 순회(postorder traversal) 은 노드를 제일 마직막에 방문하는 경우 즉, LRV의 순서로 노드를 방문하는 경우이다.
중위 순회 란 노드를 중간에 방문하는 경우 즉, LVR의 순서로 노드를 방문하는 경우이다.
중위 순회를 하는 경우를 C 코드로 나타내면 다음과 같다.1
2
3
4
5
6
7
8void inorder(treePointer ptr)
{
if(ptr){
inorder(ptr->leftChild);
printf("%c", (*ptr).data);
inorder(ptr->rightChild);
}
}
위의 코드를 살펴보면 반복법이 아닌 순환법을 이용하여 즉, 스택의 도움 없이 순회를 진행하는데 이는 스택을 이용하여 스택에 노드를 저장하고 제거하는 방식으로도 순회가 가능하다. 이러한 순회를 반복적 중위 순회 라고 하며 이를 C 코드로 구현하면 다음과 같다.1
2
3
4
5
6
7
8
9
10
11
12
13
14void iterInorder(treePointer ptr){
int top = -1; /*스택 초기화*/
treePointer stack[MAX_STACK_SIZE];
for(;;){
for(;node;node=node->leftChild)
push(node);/*스택에 삽입*/
node=pop();/*스택에서 제거*/
if(!node)/*스택이 비어있는 경우 중지*/
break;
printf("%d", node->data);
node=node->rightChild;
}
}
예제
이진 트리에서 리프 노드의 수를 세는 C 함수를 작성하여라.1
2
3
4
5
6
7
8
9
10
11
12int totalCount=0;
void countLeaf(treePointer ptr){
if(ptr&&(!(*ptr).leftChild)&&(!(*ptr).rightChild)){
totalCount++;
printf("\n리프 노드: %c, count:%d\n", (*ptr).data, totalCount);
}
if(ptr){
countLeaf((*ptr).leftChild);
printf("%c",(*ptr).data);
countLeaf((*ptr).rightChild);
}
}
스레드 이진 트리
2n개의 링크 중 n+1개가 null link 이므로 효율성이 떨어지는 문제가 생기게 되고 이를 해결하기 위해 null link에 포인터를 넣어 다른 노드의 링크를 거는 것을 스레드 라고 한다.
이원 탐색 트리(BST, Binary Search Tree)
이원 탐색 트리는 탐색, 삽입, 삭제 연산에 있어서 지금까지 공부했던 어떤 자료 구조보다도 성능이 좋다.
이원 탐색트리의 모든 원소는 키를 가지고 어떤 두 원소도 동일한 키를 갖지 않으며, 왼쪽 서브트리가 존재한다면 그 키들은 루트의 키보다 작고 오른쪽 서브트리가 존재한다면 루트의 키보다 크다. 또한, 왼쪽과 오른쪽 서브트리도 모두 이원탐색 트리이다.
이원 탐색트리의 탐색
탐색은 루트부터 시작하여 루트와 키 값이 같다면 탐색은 종료된다. 탐색하고자 하는 키 값이 루트의 키보다 작다면 왼쪽 서브트리를 탐색하고 크다면 오른쪽 서브트리를 탐색한다. 왼쪽과 오른쪽 서브트리는 모두 이원탐색 트리이므로 각각을 다시 탐색하는 순환 탐색 방식을 사용한다.
다음은 이원 탐색 트리의 순환적 탐색을 구현한 프로그램이다.1
2
3
4
5
6
7element * search(treePointer tree, int key){
if(!root) return NULL;
if(k == root->data.key) return &(root->data);
if(k<root->data.key)
return search(root->leftChild, k);
return search(root->rightChild, k);
}
아래는 동일한 기능의 반복 함수로 구현한 프로그램이다.1
2
3
4
5
6
7
8
9
10
11element* iterSearch(treePointer tree, int k)
{
white(tree){
if(k==tree->data.key) return &(tree->data);
if(k<tree->data.key)
tree = tree->leftChild;
else
tree = tree->rightChild;
}
return NULL;
}
Time Complexity: O(h)
BST 에서의 찾는 시간은 찾고자 하는 노드의 높이만큼 분기를 수행하므로 O(h) 이다.
INSERTION IN BST
Time Complexity: O(h)
BST 에서의 삭제는 search 후에 단순 삽입으로 search 시의 time complexity와 같은 complexity 를 가진다.
DELETION IN BST
Time Complexity: O(h)
BST 에서의 삭제는 다음과 같이 진행된다.
- BST에서 해당 노드를 찾음
- 해당 노드를 삭제하고, maximum value in left subchild 로 대체 하거나 혹은 minimum in right subchild 로 대체한다.
- 대체된 노드에 대한 삭제를 진행한다. 이 경우 해당 노드는 차수가 0이거나 혹은 1 이므로 삭제는 매우 간편하다.
위의 각 과정별로 시간 소모를 생각해 보면, 노드를 찾는데에 O(h), 삭제하고 서브 트리에서 값을 찾는데에 O(h) 삭제에 1 이므로 BST 에서 deletion 시에 time Complexity 는 O(h) 이다.
선택 트리
승자 트리
다음은 8개의 런(k=8) 을 가진 승자 트리의 개념도 입니다.
패자 트리
다음은 위의 승자 트리에 대응하는 패자 트리의 개념도 입니다.
분리 집합의 표현
이진 트리의 개수 계산
AVL 트리
AVL 트리란 균형 이진 트리의 한 종류이며, 이원 탐색트리가 항상 완전 이진트리로 유지되도록 한 트리입니다.
탐색, 삽입, 삭제 시간: O(logn)
AVL 트리에서 각 노드는 균형 인자(balance factor) 를 가지는데, 이는 왼쪽 트리의 높이에서 오른쪽 트리의 높이를 뺀 값으로 높이의 균형도를 나타냅니다.
balance factor = h_L - h_R
AVL 트리에서는 어떤 서브트리 T 에서도 BF(T) 의 절대값은 1 이하입니다.
AVL 트리에서의 삽입
LL rotation
RR rotation
LR rotation
