트리(Tree)
- 선형 자료 구조(linear data structure) : 자료들이 직선과 같이 나열되어 있는 구조 (리스트, 스택, 큐 등)
- 트리는 계층적인 구조(hierarchical structure) 또는 비선형 자료 구조(nonlinear data structure)를 가지고 있으며, 계층적인 자료를 표현하는 데 이용되는 자료 구조.
- 인공 지능 문제에서도 트리가 사용되는데 대표적인 것으로 결정 트리(decision tree)가 있음.
- 결정 트리는 인간의 의사 결정 구조를 표현하는 한 가지 방법.
[트리에서 쓰이는 용어]
- 노드(node) : 트리의 구성 요소
- 트리는 한 개 이상의 노드로 이루어진 유한 집합임.
- 이들 중 하나의 노드는 루트(root) 노드라고 불리고, 나머지 노드들은 서브 트리(subtree)라고 불림.
- 계층적인 구조에서 가장 높은 곳에 있는 노드가 루트가 됨.
- 트리에서 루트와 서브 트리는 선으로 연결됨. 이 연결선을 간선(edge)이라고 함.
- 노드들 간에는 부모 관계, 형제 관계, 조상과 자손 관계가 존재함.
○ 부모 노드(parent node)
/ ＼
○ ○ 자식 노드(children node) -> 형제 관계(sibling)
- 조상 노드(ancestor node) : 루트 노드에서 임의의 노드까지의 경로를 이루고 있는 노드들.
- 자손 노드(descendent node) : 임의의 노드 하위에 연결된 모든 노드들. -> 어떤 노드의 서브 트리에 속하는 모든 노드들은 자손 노드임.
- 단말 노드(terminal node 또는 leaf node) : 자식 노드가 없는 노드, 차수가 0인 노드
- 비단말 노드(nonterminal node) : 자식 노드가 있는 노드
- 노드의 차수(degree) : 어떤 노드가 가지고 있는 자식 노드의 개수
- 트리의 차수(degree) : 트리가 가지고 있는 노드의 차수 중에서 가중 큰 차수
- 레벨(level) : 트리의 각 층에 번호를 매기는 것
- 트리의 높이(height) : 트리가 가지고 있는 최대 레벨
- 포리스트(forest) : 트리들의 집합
레벨
1 A
/ ＼
2 B C
/ |＼ / | ＼
3 D E F G H I
/ / ＼ ＼
4 J K L M
-> A는 B의 부모 노드(parent node)
-> B는 A의 자식 노드(children node)
-> B는 C의 형제 노드(sibling node)
-> D, E, F, G, H, I, J, K, L, M은 자손 노드(descendent node)
-> A는 조상 노드(ancestor node)
-> J, K, F, G, L, M은 단말 노드(terminal node)
-> D, E, H, I는 비단말 노드(nonterminal node)
-> B노드의 차수(degree)는 3 (자식 노드의 수가 3개이므로)
-> B노드와 C노드의 차수가 3으로 가장 크므로 전체 트리의 차수는 3
-> 위의 트리의 높이(height)는 4
[트리의 종류]
- 트리를 컴퓨터 메모리상에서 표현하는 방법은 여러 가지가 있을 수 있음.
- 트리를 표현하는 가장 일반적인 방법은 각 노드가 데이터를 저장하는 데이터 필드와 자식 노드를 가리키는 링크 필드를 가지게 하는 것.
(일반트리) [데이터] [링크1] [링크2] ..... [링크n] // n : 자식 노드의 개수(노드의 차수)
(이진트리) [데이터] [링크1] [링크2]
- 일반적인 트리에서 각 노드들은 서로 다른 개수의 자식 노드를 가지므로 노드에 따라서 링크 필드의 개수가 달라짐.
- 이 방법의 문제점은 노드의 크기가 고정되지 않는다는 것. -> 노드에 부터 있는 서브 트리의 개수에 따라서 노드의 크기가 커지기도 하고 작아지기도 함.
- 이와 같이 자식 노드의 개수가 일정하지 않으면 프로그램이 복잡하게 됨.
- 일반 트리도 이진 트리로 변환할 수 있는 방법이 존재함.
이진 트리(Binary Tree)
- 이진 트리(Binary Tree) : 트리 중에서 가장 많이 쓰이는 트리로, 모든 노드가 2개의 서브 트리를 가지고 있는 트리.
- 서브 트리는 공집합일 수도 있음.
- 이진 트리의 노드에는 최대 2개까지의 자식 노드가 존재할 수 있고 모든 노드의 차수는 2 이하가 됨.
- 공집합도 이진 트리라는 점에 주의.
- 이진 트리에는 서브 트리 간의 순서가 존재함. -> 왼쪽 서브 트리와 오른쪽 서브 트리는 서로 구별됨.
- 이진 트리의 정의
1. 공집합이거나
2. 루트의 왼쪽 서브 트리, 오른쪽 서브 트리로 구성된 노드들의 유한 집합. 이진 트리의 서브 트리들은 모두 이진 트리여야 함.
- 이진 트리와 일반 트리의 차이점
1. 이진 트리의 모든 노드는 차수가 2 이하임. 즉, 자식 노드의 개수가 2 이하임. 반면 일반 트리는 자식 노드의 개수에 제한이 없음.
2. 일반 트리와는 달리 이진 트리는 노드를 하나도 갖지 않을 수도 있음.
3. 이진 트리는 서브 트리간에 순서가 존재함. 따라서 왼쪽 서브 트리와 오른쪽 서브 트리를 구별함.
○
/ ＼
○ ○
/ ＼ / ＼
○ 공 공 공
/ ＼
공 공
-> 공 : 공집합
[이진 트리의 성질]
1) n개의 노드를 가진 이진 트리는 정확하게 n-1개의 간선을 가짐.
why? 이진 트리에서의 노드는 루트를 제외하면 정확하게 하나의 부모 노드를 가짐.
why? 부모와 자식 간에는 정확하게 하나의 간선만이 존재함.
2) 높이가 h인 이진 트리의 경우, 최소 h개의 노드를 가지며 최대 2^h - 1개의 노드를 가짐.
why? 한 레벨에는 적어도 하나의 노드는 존재해야 하므로 높이가 h인 이진 트리는 적어도 h개의 노드를 가짐.
why? 하나의 노드는 최대 2개의 자식을 가질 수 있으므로, 레벨 i에서의 노드의 최대 개수는 2^i-1. 따라서 전체 노드의 개수는,
3) n개의 노드를 가지는 이진 트리의 높이는 최대 n이거나 최소 `┌log_2(n+1)┐`이 됨.
why? 레벨당 최소한 하나의 노드는 있어야 하므로 높이가 n을 넘을 수는 없음.
why? 앞의 성질에서 높이 h의 이진 트리가 가질 수 있는 노드의 최댓값은 `2^{h} - 1.`
따라서 `n≤2^{h} - 1` 의 부등식이 성립하고 양변에 log를 취하면 `h ≥ log_{2}(n+1)`
`h`는 정수이므로 `h ≥┌log_2(n+1)┐`이 됨. (┌...┐는 소수점 올림 연산자)
[이진 트리의 분류]
1) 포화 이진 트리(full binary tree)
- 트리의 각 레벨에 노드가 꽉 차 있는 이진 트리
- 즉, 높이 k인 포화 이진 트리는 정확하게 2^k - 1개의 노드를 가짐.
- 일반적으로 포화 이진 트리에서의 노드의 개수는 다음과 같이 계산됨.
- 포화 이진 트리에는 다음과 같이 각 노드에 번호를 붙일 수 있음.
- 노드에 번호를 부여하는 방법은 레벨 단위로 왼쪽에서 오른쪽으로 번호를 붙이면 됨. 그리고 이 번호는 항상 일정함.
- 루트 노드의 오른쪽 자식 번호는 항상 3임.
1 -------------- 1
/ ＼
2 3 --------------2
/ ＼ / ＼
4 5 6 7 ---------4
/ ＼ / ＼ / ＼ / ＼
8 9 10 11 12 13 14 15 ------8
전체 노드의 개수 : 15
2) 완전 이진 트리(complete binary tree)
- 높이가 k일 때 레벨 1부터 k-1까지는 노드가 모두 채워져 있고, 마지막 레벨 k에서는 왼쪽부터 오른쪽으로 노드가 순서대로 채워져 있는 이진 트리.
- 마지막 레벨에서는 노드가 꽉 차 있지 않아도 되지만, 중간에 빈 곳이 있어서는 안 됨.
- 따라서 포화 이진 트리는 항상 완전 이진 트리이지만 그 역은 항상 성립하지 않음.
- 포화 이진 트리의 노드 번호와 완전 이진 트리의 노드 번호는 1대1로 대응함.
○
/ ＼
○ ○
/ ＼ / ＼
○ ○ ○
(완전 이진 트리 O)○
/ ＼
○ ○
/ ＼ / ＼
○ ○ ○
(완전 이진 트리 X)-> 마지막 레벨에서 중간이 비어 있으므로 완전 이진트리가 아님.
3) 기타 이진 트리
- 경사 이진 트리 (왼쪽/오른쪽 편향 이진 트리) 등
○
/
○
/
○
(경사 이진 트리(=왼쪽 편향 이진 트리))
[이진 트리의 표현]
1) 배열 표현법 (배열을 이용하는 방법)
- 주로 포화 이진 트리나 완전 이진 트리의 경우 많이 쓰이는 방법이지만 그 외의 이진 트리도 저장이 불가능한 것은 아님.
- 이 방법은 저장하고자 하는 이진 트리를 일단 완전 이진 트리라고 가정하고, 이진 트리의 높이가 k이면 최대 2^k - 1개의 공간을 연속적으로 할당한 다음, 완전 이진 트리의 번호대로 노드들을 저장함.
- 완전 이진 트리가 아닌 일반적인 이진 트리인 경우에는 배열 표현법을 사용하면 저장은 가능하지만 기억 공간의 낭비가 심해짐.
- 배열 표현법에서는 인덱스만 알면 노드의 부모나 자식을 쉽게 알 수 있음.
- 부모와 자식의 인덱스 사이에는 다음과 같은 공식이 성립됨.
① 노드 i의 부모 노드 인덱스 `└ i/2 ┘` (└...┘ 는 소수점 내림 연산자)
② 노드 i의 왼쪽 자식 노드 인덱스 = `2i`
③ 노드 i의 오른쪽 자식 노드 인덱스 = `2i+1`
2) 링크 표현법 (포인터를 이용하는 방법)
- 노드가 구조체로 표현되고, 각 노드가 포인터를 가지고 있어서 이 포인터를 이용하여 노드와 노드를 연결하는 방법
- 이진 트리를 링크 표현법으로 표현하면 하나의 노드가 데이터를 저장하는 필드와 왼쪽 자식 노드와 오른쪽 자식 노드를 가리키는 2개의 포인터 필드를 가짐.
- 이 2개의 포인터를 이용하여 부모 노드와 자식 노드를 연결함.
왼쪽 자식 노드 ← [ ][ 데이터 ][ ] → 오른쪽 자식 노드
- 이진 트리를 링크 표현에 의해 나타내기 위해서는 C언어의 구조체와 포인터를 이용하여야 함.
- 먼저 구조체를 이용하여 노드의 구조를 정의하고 링크는 포인터를 이용하여 정의하면 됨.
// 링크 표현법으로 생성된 이진 트리
#include <stdio.h>
#include <stdlib.h>
#include <memory.h>
typedef struct TreeNode {
int data;
struct TreeNode *left, *right;
} TreeNode;
// n1
// / ＼
// n2 n3
void main() {
TreeNode *n1, *n2, *n3;
n1 = (TreeNode *)malloc(sizeof(TreeNode));
n2 = (TreeNode *)malloc(sizeof(TreeNode));
n3 = (TreeNode *)malloc(sizeof(TreeNode));
n1->data = 10; // 첫 번째 노드를 설정
n1->left = n2;
n1->right = n3;
n2->data = 20; // 두 번째 노드를 설정
n2->left = NULL;
n2->right = NULL;
n3->data = 30; // 세 번째 노드를 설정
n3->left = NULL;
n3->right = NULL;
}
[이진 트리의 순회]
- 이진 트리를 순회하는 표준적인 방법에는 전위, 중위, 후위의 3가지 방법이 있음.
- 이는 루트와 왼쪽 서브 트리, 오른쪽 서브 트리 중에서 루트를 언제 방문하느냐에 따라 구분됨.
- 루트를 방문하는 작업을 V(visted)라고 하고 왼쪽 서브 트리 방문을 L, 오른쪽 서브트리 방문을 R이라고 하면 다음과 같이 3가지 방법을 생각할 수 있음.
1) 전위 순회(preorder traversal) : 루트를 서브 트리에 앞서서 먼저 방문. (VLR)
2) 중위 순회(inorder traversal) : 루트를 왼쪽과 오른쪽 서브 트리 중간에 방문. (LVR)
3) 후위 순회(postorder traversal) : 루트를 왼쪽과 오른쪽 서브 트리 방문 후에 방문. (LRV)
V
(루트)
/ ＼
L 왼쪽 서브 트리 오른쪽 서브 트리 R
- 트리 순회 알고리즘은 순환 기법을 사용함.
- 트리의 자료구조가 순환적으로 정의되기 때문에 트리를 다루는 알고리즘을 순환적으로 작성하는 것이 매우 자연스러움.
① 전위 순회
- 루트 노드 방문 -> 왼쪽 서브 트리 방문 -> 오른쪽 서브 트리 방문
- 방문 순서
1
/ ＼
2 7
/ ＼ / ＼
3 6 8 9
/ ＼ / ＼
4 5 10 11
② 중위 순회
- 왼쪽 서브 트리 방문 -> 루드 노트 방문 -> 오른쪽 서브 트리 방문
- 방문 순서
6
/ ＼
4 8
/ ＼ / ＼
2 5 7 10
/ ＼ / ＼
1 3 9 11
③ 후위 순회
- 왼쪽 서브 트리 방문 -> 오른쪽 서브 트리 방문 -> 루드 노트 방문
- 방문 순서
11
/ ＼
5 10
/ ＼ / ＼
3 4 6 9
/ ＼ / ＼
1 2 7 8
- 순서는 중요치 않고 노드를 전부 방문하기만 하면 된다면 위의 3가지의 방법 중에 어느 것이건 관계 없음.
- 그러나 자식 노드를 처리한 다음에 부모 노드를 처리해야 한다면 후위 순회를 사용해야 하고, 부모 노드를 처리한 다음에 자식 노드를 처리해야 한다면 전위 순회를 사용해야 함.
- 전위, 중위, 후위 순회 구현
// 링크 표현법으로 생성된 이진 트리의 순회
#include <stdio.h>
#include <stdarg.h>
#include <memory.h>
typedef struct TreeNode {
int data;
struct TreeNode *left, *right;
} TreeNode;
// 15
// 4 20
// 1 16 25
TreeNode n1 = { 1, NULL, NULL };
TreeNode n2 = { 4, &n1, NULL };
TreeNode n3 = { 16, NULL, NULL };
TreeNode n4 = { 25, NULL, NULL };
TreeNode n5 = { 20, &n3, &n4 };
TreeNode n6 = { 15, &n2, &n5 };
TreeNode *root = &n6;
// 중위 순회
void inorder(TreeNode *root) {
if (root) {
inorder(root->left); // 왼쪽 서브 트리 순회
printf("%d ", root->data); // 노드 방문
inorder(root->right); // 오른쪽 서브 트리 순회
}
}
// 전위 순회
void preorder(TreeNode *root) {
if (root) {
printf("%d ", root->data); // 노드 방문
preorder(root->left); // 왼쪽 서브 트리 순회
preorder(root->right); // 오른쪽 서브 트리 순회
}
}
// 후위 순회
void postorder(TreeNode *root) {
if (root) {
postorder(root->left); // 왼쪽 서브 트리 순회
postorder(root->right); // 오른쪽 서브 트리 순회
printf("%d ", root->data); // 노드 방문
}
}
void main() {
printf("중위 순회 : ");
inorder(root);
printf("\n");
printf("전위 순회 : ");
preorder(root);
printf("\n");
printf("후위 순회 : ");
postorder(root);
printf("\n");
}
- 레벨 순회(level order) : 각 노드를 레벨 순으로 검사하는 순회 방법.
-> 루트 노드의 레벨이 1이고 아래로 내려갈 수록 레벨은 증가함.
-> 동일한 레벨의 경우에는 좌에서 우로 방문함.
-> 지금까지의 순회법이 스택을 사용했던 것에 비해(코드에는 스택이 나타나지는 않았지만 순환 호출을 하였기 때문에 간접적으로 스택을 사용) 레벨 순회는 큐를 사용.
-> 레벨 순회 프로그램
// 레벨 순회 프로그램
#include <stdio.h>
#include <stdarg.h>
#include <memory.h>
typedef struct TreeNode {
int data;
struct TreeNode *left, *right;
} TreeNode;
typedef TreeNode * element;
typedef int element; // 요소의 타입
typedef struct QueueNode { // 큐의 노드 타입
element item;
struct QueueNode *link;
} QueueNode;
typedef struct { // 큐 ADT 구현
QueueNode *front, *rear;
} QueueType;
// 오류 함수
void error(char *message) {
fprintf(stderr, "%s\n", message);
exit(1);
}
// 초기화 함수
void init(QueueType *q) {
q->front = q->rear = NULL;
}
// 공백 상태 검출 함수
int is_empty(QueueType *q) {
return (q->front == NULL);
}
// 삽입 함수
void enqueue(QueueType *q, element item) {
QueueNode *temp = (QueueNode *)malloc(sizeof(QueueNode));
if (temp == NULL) {
error("메모리를 할당할 수 없습니다.");
}
else {
temp->item = item; // 데이터 저장
temp->link = NULL; // 링크 필드를 NULL로 설정
if (is_empty(q)) { // 큐가 공백이라면
q->front = temp;
q->rear = temp;
}
else { // 큐가 공백이 아니면
q->rear->link = temp; // 순서가 중요
q->rear = temp;
}
}
}
// 삭제 함수
element dequeue(QueueType *q) {
QueueNode *temp = q->front;
element item;
if (is_empty(q)) { // 공백 상태
error("큐가 비어 있습니다.");
}
else {
item = temp->item; // 데이터를 꺼낸다.
q->front = q->front->link; // front를 다음 노드를 가리키도록 한다.
if (q->front == NULL) { // 공백 상태
q->rear = NULL;
}
free(temp); // 노드 메모리 해제
return item; // 데이터 반환
}
}
// peek 함수
element peek(QueueType *q) {
if (is_empty(q)) {
error("큐가 비어있습니다.");
}
else {
return q->front->item; // 데이터 반환
}
}
// 레벨 순회
void level_order(TreeNode *ptr) {
QueueType q;
init(&q);
if (ptr != NULL) return;
enqueue(&q, ptr);
while (!is_empty(&q)) {
ptr = dequeue(&q);
printf("%d", ptr->data);
if (ptr->left) {
enqueue(&q, ptr->left);
}
if (ptr->right) {
enqueue(&q, ptr->right);
}
}
}
- 이진 트리는 수식 트리(expression tree)를 처리하는 데 사용될 수 있음.
-> 수식 트리는 산술식이나 논리식의 연산자와 피연산자들로부터 만들어짐.
-> 피연산자들은 단말 노드가 되며 연산자는 비단말 노드가 됨.
-> 각 이진 연산자에 대하여 왼쪽 서브 트리는 왼쪽 피연산자가 되며 오른쪽 서브 트리는 오른쪽 피연산자를 나타냄.
-> 이들 수식 트리를 전위, 중위, 후위의 순회 방법으로 읽으면 각각 전위 표기 수식, 중위 표기 수식, 후위 표기 수식이 됨.
| 수식 | a+b | a-(bXc) | (a<b) or (c<d) |
| 전위 순회 | +ab | -aXbc | or<ab<cd |
| 중위 순회 | a+b | a-(bXc) | (a<b) or (c<d) |
| 후위 순회 | ab+ | abcX- | ab<cd<or |
-> 수식 트리의 루트 노드는 연산자이므로 이 연산자의 피연산자인 서브 트리들만 계산되면 전체 수식을 계산할 수 있음.
-> 각각의 서브 트리에서도 마찬가지로 서브 트리들만 계산되면 전체 수식을 계산할 수 있음.
-> 따라서 여러 가지 순회 방법 중에서 가장 적합한 순회 방식은 자식 노드를 먼저 방문하는 후위 순회.
+
/ ＼
* *
/ ＼ / ＼
3 2 5 6
=> (3*2)+(2*6)
-> 수식 트리 계산 프로그램
// 수식 트리 계산 프로그램
#include <stdio.h>
#include <stdlib.h>
#include <memory.h>
typedef struct TreeNode {
int data;
struct TreeNode *left, *right;
} TreeNode;
// +
// * +
// 1 4 16 25
TreeNode n1 = { 1, NULL, NULL };
TreeNode n2 = { 4, NULL, NULL };
TreeNode n3 = { '*', &n1, &n2 };
TreeNode n4 = { 16, NULL, NULL };
TreeNode n5 = { 25, NULL, NULL };
TreeNode n6 = { '+', &n4, &n5 };
TreeNode n7 = { '+', &n3, &n6 };
TreeNode *exp = &n7;
// 수식 계산 함수
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;
}
}
return 0;
}
void main() {
printf("%d", evaluate(exp));
}
- 이진 트리 순회는 디렉터리의 용량을 계산하는 데도 사용될 수 있음.
-> 단, 이진 트리를 사용하여야 하기 때문에 하나의 디렉터리 안에 다른 디렉터리가 2개를 초과하여 있으면 안됨.
-> 후위 순회를 사용함.
-> 트리의 노드를 동적으로 생성하는 편이 좋음.
-> 디렉터리 용량 계산 프로그램
// 디렉터리 용량 계산 프로그램
#include <stdio.h>
#include<stdlib.h>
#include <memory.h>
typedef struct TreeNode {
int data;
struct TreeNode *left, *right;
} TreeNode;
int calc_direc_size(TreeNode *root) {
int total_size = 0;
if (root) {
total_size = root->data + calc_direc_size(root->left) + calc_direc_size(root->right);
}
return total_size;
}
void main() {
TreeNode n4 = { 500, NULL, NULL };
TreeNode n5 = { 200, NULL, NULL };
TreeNode n3 = { 100, &n4, &n5 };
TreeNode n2 = { 50, NULL, NULL };
TreeNode n1 = { 0, &n2, &n3 };
printf("디렉토리의 크기 = %d \n", calc_direc_size(&n1));
}
[스레드 이진 트리]
- 이진 트리 순회는 순환 호출을 사용함. 그러나 순환 호출은 함수를 호출해야 되므로 상당히 비효율적일 수가 있음.
- 이진 트리 순회도 노드의 개수가 많아지고 트리의 높이가 커지게 되면 상당히 비효율적일 수도 있음.
- 스레드 이진 트리(threaded binary tree) : NULL 링크에 중위 순회 시에 선행 노드인 중위 선행자(inorder predecessor)나 중위 순회 시에 후속 노드인 중위 후속자(inorder successor)를 저장시켜 놓은 트리. 스레드(thread), 즉 실을 이용하여 노드를 순회 순서대로 연결시켜 놓은 트리.
- 스레드 이진 트리 순회 프로그램
#include <stdio.h>
#define TRUE 1
#define FALSE 0
typedef struct TreeNode {
char data;
struct TreeNode *left, *right;
int is_thread; // 스레드이면 TRUE
} TreeNode;
// G
// C F
// A B D E
TreeNode n1 = { 'A', NULL, NULL, 1 };
TreeNode n2 = { 'B', NULL, NULL, 1 };
TreeNode n3 = { 'C', &n1, &n2, 0 };
TreeNode n4 = { 'D', NULL, NULL, 1 };
TreeNode n5 = { 'E', NULL, NULL, 0 };
TreeNode n6 = { 'F', &n4, &n5, 0 };
TreeNode n7 = { 'G', &n3, &n6, 0 };
TreeNode *exp = &n7;
TreeNode *find_successor(TreeNode *p) {
// q는 p의 오른쪽 포인터
TreeNode *q = p->right;
// 만약 오른쪽 포인터가 NULL이거나 스레드이면 오른쪽 포인터를 반환
if (q == NULL || p->is_thread == TRUE) {
return q;
}
// 만약 오른쪽 자식이면 다시 가장 왼쪽 노드로 이동
while (q->left != NULL) q = q->left;
return q;
}
void thread_inorder(TreeNode *t) {
TreeNode *q;
q = t;
while (q->left != NULL) q = q->left; // 가장 왼쪽 노드로 간다.
do {
printf("%c", q->data); // 데이터 출력
q = find_successor(q); // 후속자 함수 호출
} while (q != NULL); // NULL이 아니면
}
void main() {
// 스레드 설정
n1.right = &n3;
n2.right = &n7;
n4.right = &n6;
// 중위 순회
thread_inorder(exp);
}
[이진 탐색 트리]
- 이진 탐색 트리(binary search tree) : 이진 트리 기반의 탐색을 위한 자료구조.
- 탐색(search)은 가장 중요한 컴퓨터 응용의 하나이며, 컴퓨터 응용 프로그램에서도 많이 사용될 뿐만 아니라, 가장 시간이 많이 걸리는 작업 중의 하나이므로 탐색을 가능한 효율적으로 수행하는 것은 무척 중요함.
- 탐색은 레코드(record)의 집합에서 특정한 레코드를 찾아내는 작업을 의미함.
- 레코드는 하나 이상의 필드(field)로 구성됨.
- 일반적으로 레코드들의 집합을 테이블(table)이라고 함.
- 레코드들은 보통 키(key)라고 불리는 하나의 필드에 의해 서로 구별됨.
- 일반적인 경우 각각의 키는 다른 키와 중복되지 않는 고유한 값을 가지며 이러한 키를 사용하면 각각의 레코드들을 구별할 수 있을 것임.
- 이러한 키를 주요 키(primary key)라고 부름.
- 탐색 작업을 할 때는 이러한 키가 입력이 되어 특정한 키를 가진 레코드를 찾게 됨.
- 이진 탐색 트리는 이러한 탐색 작업을 효율적으로 하기 위한 자료 구조임.
- 이진 탐색 트리의 정의
1. 모든 노드의 키는 유일함.
2. 왼쪽 서브 트리의 키들은 루트의 키보다 작음.
3. 오른쪽 서브 트리의 키들은 루트의 키보다 큼.
4. 왼쪽과 오른쪽 서브 트리도 이진 탐색 트리임.
- 찾고자 하는 키 값이 이진 트리의 루트 노드의 키 값과 비교하여 작으면 원하는 키 값은 왼쪽 서브 트리에 있고, 루트 노드보다 크면 원하는 키값은 오른쪽 서브 트리에 있음.
18
. / | ＼
. 7 | 26
/ ＼ | ＼
3 12 | 31
| /
| 27
루트보다 작은 값 | 루트보다 큰 값
- 이진 탐색 트리에서 특정 키 값을 가진 노드를 찾기 위해서는 먼저 주어진 탐색 키 값과 현재의 루트 노드의 키 값을 비교함.
- 비교한 결과에 따라 다음의 3가지로 나누어짐.
1. 비교한 결과가 같으면 탐색이 성공적으로 끝남.
2. 주어진 키 값이 루트 노드의 키 값보다 작으면 탐색은 이 루트 노드의 왼쪽 자식을 기준으로 다시 시작함.
3. 주어진 키 값이 루트 노드의 키 값보다 크면 탐색은 이 루트 노드의 오른쪽 자식을 기준으로 다시 시작함.
->즉, 루트 노드보다 작으면 왼쪽 서브 트리로, 루트 노드보다 크면 오른쪽 서브 트리로 진행하면 됨.
- 이진 탐색 트리 프로그램
// 이진 탐색 트리 프로그램
#include <stdio.h>
#include <stdlib.h>
typedef struct TreeNode {
int key;
struct TreeNode *left, *right;
} TreeNode;
// 순환적인 탐색 함수
TreeNode *search(TreeNode *node, int key) {
if (node == NULL) return NULL;
if (key == node->key) return node;
else if (key < node->key) {
return search(node->left, key);
}
else {
return search(node->right, key);
}
}
// 반복적인 탐색 함수
TreeNode *search(TreeNode *node, int key) {
while (node != NULL) {
if (key == node->key) return node;
else if (key < node->key) {
node = node->left;
}
else {
node = node->right;
}
}
return NULL; // 탐색에 실패했을 경우 NULL 반환
}
// key를 이진 탐색 트리 root에 삽입한다.
// key가 이미 root 안에 있으면 삽입되지 않는다.
void insert_node(TreeNode **root, int key) {
TreeNode *p, *t; // p는 부모 노드, t는 현재 노드
TreeNode *n; // n은 새로운 노드
t = *root;
p = NULL;
// 탐색을 먼저 수행
while (t != NULL) {
if (key == t->key) return; // 이미 존재
p = t;
if (key < p->key) t = p->left;
else t = p->right;
}
// key가 트리 안에 없으므로 삽입 가능
// 트리 노드 구성
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;
}
// 삭제 함수
void delete_node(TreeNode **root, int key) {
TreeNode *p, *child, *succ, *succ_p, *t;
// key를 갖는 노드 t를 탐색. p는 t의 부모 노드
p = NULL;
t = *root;
// key를 갖는 노드 t를 탐색한다.
while (t != NULL && t->key != key) {
p = t;
t = (key < p->key) ? p->left : p->right;
}
// 탐색이 종료된 시점에 t가 NULL이면 트리 안에 key가 없음
if (t == NULL) { // 탐색 트리에 없는 키
printf("key is not in the tree");
return;
}
// 첫 번째 경우 : 단말 노드인 경우
if ((t->left == NULL) && (t->right == NULL)) {
if (p != NULL) {
// 부모 노드의 자식 필드를 NULL로 만든다.
if (p->left == t) {
p->left = NULL;
}
else p->right = NULL;
}
else { // 만약 부모 노드가 NULL이면 삭제되는 노드가 루트
*root = 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 { // 만약 부모 노드가 NULL이면 삭제되는 노드가 루트
*root = child;
}
}
// 세 번째 경우 : 두 개의 자식을 가지는 경우
else {
// 오른쪽 서브 트리에서 후계자를 찾는다.
succ_p = t;
succ = t->right;
// 후계자를 찾아서 계속 왼쪽으로 이동한다.
while (succ->left != NULL) {
succ_p = succ;
succ = succ->left;
}
// 후속자의 부모와 자식을 연결
if (succ_p->left == succ) {
succ_p->left = succ->right;
}
else {
succ_p->right == succ->right;
}
// 후속자가 가진 키 값을 현재 노드에 복사
t->key = succ->key;
// 원래의 후속자 삭제
t = succ;
}
free(t);
}
내용 출처 : C언어로 쉽게 풀어쓴 자료구조 (천인국 외 지음, 생능출판사)
'Computer Science > Data Structure' 카테고리의 다른 글
| [C] 해싱(Hashing) (0) | 2017.06.20 |
|---|---|
| [C] 그래프(Graph) (0) | 2017.06.19 |
| [C] 정렬(Sorting) (0) | 2017.06.18 |
| [C] 우선순위 큐(Priority Queue) (0) | 2017.06.17 |
| [C] 큐(Queue) (0) | 2017.05.23 |
| [C] 스택(Stack) (0) | 2017.05.11 |
| [C] 이중 연결 리스트(Doubly Linked List) (0) | 2017.05.06 |
| [C] 원형 연결 리스트(Circular Linked List) (0) | 2017.05.02 |
