트리
-> 부모-자식 관계의 노드들로 이루어진, 계층적인 관계를 나타내는 특별한 자료구조(비선형 리스트).
▷ 용어
· 노드 : 데이터, 정보가 저장된 트리의 구성 원소
· 에지(간선) : 노드와 노드 사이를 나타내는 구성 원소
· 루트 : 부모가 없는 노드, 최상단 노드
· 리프 : 자식이 없는 노드, 단말 노드
· 레벨 : 트리의 각 층의 번호(루트의 레벨은 0 또는 1)
· 높이(깊이) : 트리의 최대 레벨
· 차수 : 노드가 가지고 있는 자식 노드 개수
이진트리
-> 공집합이거나, 공집합이 아닌 경우 특별히 지정된 노드인 루트가 있고, 각 노드는 최대 2개의 자식 노드가 존재하며, 각 노드가 왼쪽 부분트리 및 오른쪽 부분트리를 가짐.
▷ 분류
· 포화 이진트리(full binary tree) : 트리의 각 레벨마다 노드들이 꽉 차 있는 이진트리를 의미. 리프노드를 제외한 모든 노드가 2개의 자식노드를 갖는 트리.
·완전 이진트리(complete binary tree) : 레벨 0부터 h-1까지는 노드들로 모두 채워져 있고(포화 이진트리이고), 마지막 레벨 h에서는 왼쪽부터 오른쪽으로 노드가 순서대로 채워져 있는 이진트리. 포화 이진트리이면 완전 이진트리임.
· 경사 이진트리(skewed binary tree) : 모든 노드들이 왼쪽 자식노드만 있거나 오른쪽 자식노드만 있는 이진트리.
▷ 성질
1. 노드의 개수가 n개면, 트리의 모양이나 n값에 상관없이 항상 에지의 개수는 n-1개. (루트를 제외하고 간선과 노드를 1:1 대응 시킬 수 있으므로)
2. 높이 h인 이진트리의 경우 최소 h+1(경사이진트리)개의 노드를 가지며 최대 2h+1-1(포화이진트리)개의 노드를 가짐.
3. n개의 노드를 갖는 이진트리의 높이 h는 최대 n-1(경사이진트리)의 값을 가지며 최소 floor(log2n)(포화이진트리)의 값을 가짐.
▷ ADT
| create() :: = 이진트리 생성 |
| is_empty() :: = 이진트리가 공백상태인지 확인 |
| get_root() :: = 이진트리의 루트 반환 |
| get_count() :: = 이진트리의 노드 수 반환 |
| get_height() :: = 이진트리의 높이 반환 |
| insert_node(t) :: = 이진트리에 노드 t 삽입 |
| delete_node(t) :: = 이진트리에서 노드 t 삭제 |
| visit() :: = 이진트리의 모든 노드 데이터 출력 |
▷ 구현
○ 배열
· 개념 : 모든 이진트리를 포화 이진트리라고 가정하고 각 노드에 레벨순위로 번호를 붙여서 그 번호를 배열의 인덱스로 삼아 노드의 데이터를 배열에 저장하는 방법.
· 장점 : 임의의 노드에 대해 부모, 왼쪽/오른쪽 자식노드의 위치 계산이 용이.
노드 i의 부모 노드 인덱스 = floor(i-1/2), (i!=0), 노드 i의 왼쪽 자식노드 인덱스 = 2i+1, (2i+1 <= n-1), 노드 i의 오른쪽 자식노드 인덱스= 2i+2, (2i+2 <= n-1)
·단점 : 완전 이진트리가 아니면 메모리 낭비가 큼. 노드 삽입, 제거시 원소 이동 등 부가 연산 필요.
○ 연결리스트
· 포인터를 이용해 부모노드가 자식노드를 가리키게 하는 방법. 보통 2개의 포인터로 각각 왼쪽 자식과 오른쪽 자식을 가리킴. 부모노드의 위치는 쉽게 알 수 없음. 쉽게 알기 위해서는 포인터를 3개를 두어 하나는 parent를 가리키거나 스택을 사용함.
//노드는 구조체, 링크는 포인터로 표현
typedef struct TreeNode {
int data;
struct TreeNode *left, *right;
} TreeNode;
▷ 운행 방법(순회)
· 운행(traversal) : 이진트리의 노드들을 체계적인 순서로 방문하는 것. 이진트리의 왼쪽 부분트리를 오른쪽 부분트리보다 먼저 방문하는 것을 가정함.
1. 전순위 운행(preorder traversal) : 부분트리보다 루트를 먼저 방문
2. 중순위 운행(inorder traversal) : 루트를 트리 부분트리들 사이에 방문. 이진트리가 아닌 경우에는 이 경우 중간을 무엇으로 볼 것인지가 애매함.
3. 후순위 운행(postorder traversal) : 루트를 가장 마지막에 방문
4. 레벨순위 운행(level order traversal) : 각 노드를 레벨순으로 방문하는 운행 방법. 작은 레벨부터 방문하며 레벨이 같으면 왼쪽부터 오른쪽으로 방문.
1~3번은 세가지 방법 모두 재귀적인 형태의 방문이어서 스택을 사용해야 하고(혹은 재귀함수로 구현), 4번은 큐를 사용해야 함.
//중순위 운행
void inorder(TreeNode *root) {
if(root) {
inorder(root->left);
cout << root->data;
inorder(root->right);
}
}
//전순위 운행
void preorder(TreeNode *root) {
if(root) {
cout << root->data;
preorder(root->left);
preorder(root->right);
}
}
//후순위 운행
void postorder(TreeNode *root) {
if(root) {
postorder(root->left);
postorder(root->right);
cout << root->data;
}
}
//레벨순위 운행
void level_order(TreeNode *root) {
QueType *q;
init(&q);
if(root == NULL) return;
enqueue(&q, root);
while(!is_empty(&q)){
root = dequeue(&q);
cout << root->data;
if(root->left) enqueue(&q, root->left)
if(root->right) enqueue(&q, root->right)
}
}
▷ 응용
○ 수식표현 트리
· 수식표현트리 : 산술식을 트리 형태로 표현한 것. 내부노드는 연산자, 단말노드는 피연산자. 수식표현 트리의 계산에는 후순위 운행을 이용. 양쪽 부분트리의 값을 재귀 호출로 계산하여 해당 노드에 저장된 연산자를 이용해 계산.
int evaluate(TreeNode *root) {
if (root == NULL) return 0;
if (root->left == NULL && root->right == NULL) return root->data //단말노드인 경우
else {
int op1 = evaluate(root->left); //부분트리의 계산값을 구해 피연산자 변수에 저장
int op2 = evaluate(root->right);
switch(root->data) { //연산자에 따라 연산 시행
case '+': return op1+op2;
case '-': return op1-op2;
case '*': return op1*op2;
case '/': return op1/op2;
}
}
}
○ 이진트리의 연산
· 노드 개수
: 각 부분트리에 대해 재귀 호출을 해서 노드 개수를 구하여 더한 다음 여기에 다시 1을 더해 반환.
int get_node_count(TreeNode *node) {
int count=0;
if (node != NULL)
count = 1 + get_node_count(node->left) + get_node_count(node->right)
return count;
}단말노드 수를 n0, 차수가 1인 노드 수를 n1, 차수가 2인 노드 수를 n2라 하면 항상 n0 = n2+1을 만족함. 전체 노드 수 n에 관한 식과 이진트리에서의 링크 수 n-1에 대한 방정식을 연립하면 얻을 수 있음.
| n = n0 + n1 + n2 n-1 = 0*n0 + 1*n1 + 2*n2 |
·높이
: 각 부분트리에 대해 재귀호출을 해서 높이를 구하여 부분트리의 반환값 중 최대값 + 1을 반환
int get_height(TreeNode *root) {
int height=0;
if (root != NULL)
height = 1 + max(get_height(root->left), get_height(root->right));
return height;
}
· 서로 다른 이진 트리의 수
: n개의 노드를 가진 서로 다른 모양의 이진 트리의 개수는 카탈란 수(catalan number)이다. 카탈란 수는 1,2...n의 순서로 스택의 push, pop연산을 이용하여 얻을 수 잇는 서로 다른 순열의 개수를 구하는 문제와 (n+1)개의 행렬을 곱하는 순서의 수, (n+3)각형을 삼각형으로 분할하는 방법의 수를 푸는 경우에도 사용된다.
○ k차 트리의 2차 트리 표현
·k차 트리 : 트리의 최대 차수가 k인 트리. null 링크의 개수가 k의 크기에 비례하여, k가 클수록 메모리 낭비가 큼. 보통 k차 트리는 이진 트리로 변환해서 표현할 수 있음.
·k차 트리의 이진 트리 변환 방법 : 왼쪽 링크는 k개의 자식 노드 중 첫 번째 자식 노드를 가리키도록 하고, 오른쪽 링크는 자신의 오른쪽 형제 노드를 가리키도록 함.
○ 포리스트를 이진트리로 변환
·포리스트 : m(m>=0)개의 트리로 구성된 집합. 여러 개의 트리의 집합도 포리스트이고, 한 트리의 루트를 제거하여도 포리스트.
·포리스트를 이진트리로 변환하는 방법
: m = 0인 경우, 즉 포리스트에 트리가 없는 경우면 대응되는 이진트리는 공집합.
m > 0인 경우, 이진트리의 루트는 포리스트의 첫 번째 트래의 루트이고 왼쪽 부분트리는 첫 번째 트리의 부분트리를 이진트리로 변환한 것이며 오른쪽 부분트리는 나머지 트리를 이진트리로 변환한 것이 됨. (위에서 사용한 k차 트리를 이진트리로 변환하는 방법을 사용하여 변환)
○ 이진탐색트리 (Binary search tree, BST)
·개념 : 탐색 작업을 효율적으로 하기 위한 트리 자료구조. 모든 노드의 키값은 유일하다고 가정하며, key(왼쪽 부분트리) < key(루트) < key(오른쪽 부분트리)의 조건을 만족. 비어있는 NULL트리도 이진탐색트리이고, 이진탐색트리의 왼쪽 부분트리와 오른쪽 부분트리도 각각 이진탐색트리. 이진탐색트리를 중순위 운행하면 오름차순으로 정렬된 값을 얻을 수 있음.
·탐색 연산 : 주어진 키값이 루트의 키갑과 같으면 탐색이 성공적으로 끝나고, 그보다 작으면 왼쪽 부분트리의 루트를 기준으로, 그보다 크면 오른쪽 부분트리의 루트를 기준으로 다시 탐색을 시작함. 최악의 경우 높이 h번만큼 시행.
//반복적 방법
TreeNode *search(TreeNode *node, int key)
{
while (node != NULL) {
if (key == node->data) return node; //성공탐색
else if(key < node->data) node = node->left;
else node = node->right;
}
return NULL; //실패탐색
}
//재귀적 방법
TreeNode *search(TreeNode *node, int key)
{
if (node == NULL) return NULL;
if (key == node->data) return node;
else if (key < node->data) return search(node->left, key);
else return search(node->right, key);
}
·삽입 연산 : 먼저 탐색을 수행하여서 탐색이 성공하면 삽입 연산을 시행할 수 없음. 탐색에 실패한 경우, 실패한 위치에 새로운 노드를 삽입. 최악의 경우 시간복잡도는 O(h)
void insert_node(TreeNode **root, int key)
{
TreeNode *p, *t; //p는 부모노드, t는 현재 노드
TreeNode *n;
t = *root;
p = NULL;
while (t != NULL) { //탐색하여 삽입위치 찾음
if (key == t->key) return; //삽입 불가
p = t;
if (key < t->key) t = t->left;
else t = t->right;
}
n = (TreeNode*)malloc(sizeof(TreeNode));
if (n == NULL) return;
n->key = key; //데이터 복사
n->left = n->right = NULL;
if (p != NULL) { //부모노드와 링크 연결
if (key < p->key) p->left = n;
else p->right = n;
}
else *root = n;
}
·삭제 연산 : 삭제하려는 노드가 단말 노드인 경우, 하나의 부분트리만 가지고 있는 경우, 두 개의 부분트리 모두 가지고 있는 경우를 나누어 연산해야 함. 첫 번째 경우에는 단말노드의 부모노드를 찾아 연결을 끊으면 되고, 두 번째 경우에는 해당 노드를 삭제하고 그 노드의 부분트리를 부모노드에 연결시켜주어야 한다. 마지막 경우에는 삭제노드의 값보다 큰 값들 중에서 가장 작은 값(중순위 계승자, inorder successor)나 삭제노드의 값보다 작은 값들 중에서 가장 큰 값(중순위 선행자, inorder predecessor)을 가진 노드를 삭제 노드 위치로 가져옴.
void delete_node(TreeNode **root, int key)
{
TreeNode *p, *child, *succ, *succ_p, *t; //child:t의 child, succ:successor, succ_p:parent of succ
p = NULL, t = *root; //방문용 t, p는 t의 부모노드
while (t != NULL && t->key != key) { //key를 갖는 노드 t 탐색
p = t;
t = (key < t->key)? t->left : t->right;
}
if (t == NULL) { //탐색트리에 삭제할 키를 가진 노드가 없음
cout << "key is not in the tree";
return;
}
//첫 번째 경우; 삭제할 노드가 단말노드
if ((t->left == NULL) && (t->right == NULL)) {
if (p != NULL) {
if (p->left == t) p->left == NULL;
else p->right == NULL;
}
else *root = NULL; //부모노드가 NULL이면 삭제되는 노드가 루트
}
//두 번째 경우; 삭제할 노드가 하나의 자식만 있는 경우
else if ((t->left == NULL) || (t->right == NULL)) {
child = (t->left != NULL)? t->left : t->right;
if (p != NULL) {
if (p->left == t) p->left = child;
else p->right = child;
}
else *root = child; //부모노드가 NULL이면 삭제되는 노드가 루트
}
//세 번째 경우; 삭제할 노드가 두 개의 자식을 가지는 경우
else {
succ_p = t;
succ = t->right; //오른쪽 부분트리에서 계승자를 찾음
while (succ->left != NULL) { //계승자: 오른쪽 부분트리의 leftmost child
succ_p = succ;
succ = succ->left;
}
//계승자의 부모와 계승자의 자식을 연결
if (succ_p->left == succ)
succ_p->left = succ->right; //계승자는 leftmost child이므로 왼쪽 부분트리가 없음
else
succ_p->right = succ->right;
//계승자의 키 값을 현재노드에 복사
t->key = succ->key;
t = succ; //원래의 계승자 삭제
}
free(t);
}
· 성능분석 : 이진탐색트리에서의 탐색, 삽입, 삭제연산의 시간 복잡도는 트리의 높이 h에 비례함. 최악의 경우(경사 이진트리) 시간복잡도는 O(n) (h가 n에 비례하므로), 평균적인 경우 시간복잡도는 O(log2n)
○ 트레드(thread) 이진 트리
·트레드 이진 트리
: 이진트리의 2n개의 링크 중 실제 링크는 (n-1)개이므로 나머지는 null이어서 그만큼 공간이 낭비됨. null 링크를 트레드 포인터로 사용하여 스택 없이 중순위 운행할 수 있게 한 것이 트레드 이진트리.
·특징
: 왼쪽 자식이 null인 경우에는 그 링크가 해당 노드의 중순위 선행 노드(inorder predecessor)를 가리키도록 하고, 오른쪽 자식이 null인 경우에는 그 링크가 해당 노드의 중순위 계승 노드(inorder successor)를 가리키도록 함.
따라서 실제 자식 노드 포인터 및 트레드 포인터를 구분하는 플래그가 별도로 필요. 두 개의 필드를 추가해 이를 나타내야 함. 그럼에도 운행시 스택이 불필요하므로 메모리가 절약됨. 운행 시간의 복잡도는 O(n).
헤드 노드를 두는 경우, 헤드 노드가 비어있을 때는 isleftThread는 true, isrightThread는 false로 하고 lchild와 rchild 모두 자기 자신을 가리킴
· 구현
typedef struct TreeNode {
struct TreeNode *lchild;
bool isleftThread; //lchild가 트레드 포인터면 true, 자식노드 가리키는 실제 포인터면 false
char data;
bool isrightThred;
struct TreeNode *rchild;
} TreeNode;
TreeNode *insucc(TreeNode *node) { //inorder succesor 찾기
TreeNode *temp;
temp = node->rchild;
if (!node->isrightThread) {
while (!temp->isleftThread) temp = temp->lchild; // isleftThread가 true면 왼쪽 자식이 없는 것이므로
}
return temp;
}
void tinorder(TreeNode *head) {
TreeNode *temp;
temp = head;
for(;;) {
temp = insucc(temp);
if (temp == head) break;
cout << temp->data;
}
}
'CS > 자료구조(DS)' 카테고리의 다른 글
| 그래프의 개념과 종류, 구현 (0) | 2021.03.30 |
|---|---|
| 우선순위 큐의 개념과 구현, 힙의 구현과 응용; 힙정렬 (0) | 2021.03.29 |
| 큐의 구현과 응용; 덱(deque) (0) | 2021.03.22 |
| 스택의 구현과 응용; 괄호 검사, 수식 계산 (0) | 2021.02.16 |
| 기본 자료 구조; 리스트의 구현 (0) | 2021.02.15 |