[자료구조] 트리 (Tree)
1) 트리 (Tree)
- 원소들 간에 1:多 관계를 가지는 비선형 자료구조
- 원소들 간에 계층관계를 가지는 계층형 자료구조
- 상위 원소에서 하위 원소로 내려가면서 확장되는 트리(나무) 모양의 구조
용어 정리
- 노드(Node) :
- 트리의 원소
- 루트 노드(Root Node) :
- 트리의 시작 노드
- 간선(Edge) :
- 노드를 연결하는 선, 부모 노드와 자식 노드를 연결
- 형제 노드(Sibling Node) :
- 같은 부모 노드의 자식 노드들
- 조상 노드(Ancestor Node) :
- 간선을 따라 루트 노드까지 이르는 경로에 있는 모든 노드들
- 서브 트리(Subtree) :
- 간선을 따라 루트 노드까지 이르는 경로에 있는 모든 노드들
- 자손 노드 :
- 서브 트리에 있는 하위 레벨의 노드들
- 차수(Degree) :
- 노드의 차수 : 노드에 연결된 자식 노드의 수
- 트리의 차수 : 트리에 있는 노드의 차수 중에서 가장 큰 값
- 단말 노드(리프 노드) : 차수가 0인 노드, 자식 노드가 없는 노드
- 노드의 높이 :
- 루트에서 노드에 이르는 간선의 수
- 트리의 높이 :
- 트리에 있는 노드의 높이 중에서 가장 큰 값
- 숲(Forest) :
- 서브 트리의 집합
2) 이진 트리
- 트리의 노드 구조를 일정하게 정의하여 트리의 구현과 연산이 쉽도록 정의한 트리
- 이진 트리의 모든 노드는 왼쪽 자식 노드와 오른쪽 자식 노드 만을 가짐
- 부모 노드와 자식 노드 수와의 관계는 1:2
- 공백 노드도 자식 노드로 취급
- 0 ≤ 노드의 차수 ≤ 2
- 노드의 왼쪽 자식 노드를 루트로 하는 왼쪽 서브 트리도 이진 트리
- 노드의 오른쪽 자식 노드를 루트로 하는 오른쪽 서브 트리도 이진 트리
특성
- n개의 노드를 가진 이진 트리는 항상 (n-1)개의 간선을 가짐
- 루트를 제외한 (n-1)개의 노드가 부모 노드와 연결되는 한 개의 간선을 가짐
- 이진 트리의 높이가 h가 되려면 한 레벨에 최소한 한 개의 노드가 있어야 함
- 높이가 𝒉인 이진 트리가 가질 수 있는 노드의 최소 개수는 (𝒉+1)개
- 하나의 노드는 최대 2개의 자식 노드를 가질 수 있음
- 레벨 i에서 노드의 최대 개수는 2i개
- 최대 개수는 (𝒉𝟐 + 𝒉 + 𝟏)개가 됨
3) 이진트리 배열로 구현
- 높이가 h인 포화 이진 트리의 노드 번호를 배열의 인덱스로 사용
- 인덱스 0번 : 실제로 사용하지 않고 비워둠
- 인덱스 1번 : 루트 저장
색인적 할당
순차 자료구조 표현의 단점
- 편향 이진 트리의 경우에 사용하지 않는 배열 원소에 대한 메모리 공간 낭비 발생
- 트리의 원소 삽입/삭제에 대한 배열의 크기 변경 어려움
- 할당 받은 배열의 크기가 한정되어 있음
- [삽입 시] 배열의 크기를 늘리는데 복잡하고 시간이 많이 걸림
- [삭제 시] 배열 원소가 발생하므로 메모리가 낭비
4) 이진트리 연결리스트로 구현
- 이진 트리의 모든 노드는 최대 2개의 자식 노드를 가지므로 일정한 구조의 단순 연결 리스트 노드를 사용하여 구현
typedef struct treeNode
{
char data;
treeNode *left;
treeNode *right;
}treeNode;
편향 이진 트리의 표현
- 이진 트리의 연결 자료구조 표현
- 왼쪽 포인터는 왼쪽 자식 노드를 참조
- 오른쪽 자식 노드는 없으므로 오른쪽 포인터는 null로 저장
- 왼쪽 자식 노드가 없는 경우 해당 포인터를 null로 저장
5) 이진 트리의 순회
- 계층적 구조로 저장되어있는 트리의 모든 노드를 방문하여 데이터를 처리하는 연산
- 순회를 위해 수행할 수 있는 작업 정의
- 현재 노드를 방문하여 데이터를 읽는 작업 D
- 현재 노드의 왼쪽 서브 트리로 이동하는 작업 L
- 현재 노드의 오른쪽 서브 트리로 이동하는 작업 R
- 이진 트리 순회의 연산 방법 및 우선순위
- 계층적 구조로 저장되어있는 트리의 모든 노드를 방문하여 데이터를 처리하는 연산
- 이진 트리가 순환적으로 정의되어 구성되어 있으므로, 순회작업도 서브 트리에 대해서 순환적으로 반복하여 완성함
- 왼쪽 서브 트리에 대한 순회를 오른쪽 서브 트리 보다 먼저 수행함
전위 순회(Preorder Traversal)
- 현재 노드 n을 방문하여 처리함 D
- 현재 노드 n의 왼쪽 서브 트리로 이동함 L
- 현재 노드 n의 오른쪽 서브 트리로 이동함 R
preorder(T)
{
if (T != null)
{
visit T.data;
preorder(T.left);
preorder(T.right);
}
}
중위 순회(Inorder Traversal)
- 현재 노드 n의 왼쪽 서브 트리로 이동함 L
- 현재 노드 n을 방문하여 처리함 D
- 현재 노드 n의 오른쪽 서브 트리로 이동함 R
inorder(T)
{
if (T != null)
{
inorder(T.left);
visit T.data;
inorder(T.right);
}
}
후위 순회(Inorder Traversal)
- 현재 노드 n의 왼쪽 서브 트리로 이동함 L
- 현재 노드 n의 오른쪽 서브 트리로 이동함 R
- 현재 노드 n을 방문하여 처리함 D
postorder(T)
{
if (T != null)
{
postorder(T.left);
postorder(T.right);
visit T.data;
}
}
6) 이진 트리의 탐색
- 루트에서 시작함
- 탐색할 키 값 x를 루트 노드의 키 값과 비교함
- 키 값 x = 루트 노드의 키 값
- 원하는 원소를 찾았으므로 탐색 연산 성공
- 키 값 x < 루트 노드의 키 값
- 루트 노드의 왼쪽 서브 트리에 대해서 탐색 연산 수행
- 키 값 x > 루트 노드의 키 값
- 루트 노드의 오른쪽 서브 트리에 대해서 탐색 연산 수행
- 서브 트리에 대해서 순환적으로 탐색 연산을 반복함
searchBST(bsT, x)
{
p ← bsT;
if (p = null)
return null;
if (x = p.key)
return p;
if (x < p.key)
return searchBST(p.left, x);
else
return searchBST(p.right, x)
}
7) 이진 트리의 삽입
- 먼저 탐색 연산을 수행
- 삽입할 원소와 같은 원소가 트리에 있으면 삽입할 수 없으므로, 같은 원소가 트리에 있는지 탐색하여 확인함
- 탐색에서 탐색 실패가 결정되는 위치가 삽입 위치가 됨
- 탐색 실패한 위치에 원소를 삽입함
insertBST(bsT, x)
{
p = bsT;
while (p != null)
{
if (x = p.key)
return;
q = p;
if (x < p.key)
p = p.left;
else
p = p.right;
}
new = getNode();
new.key = x;
new.left = null;
new.right = null;
if (bsT = null)
bsT = new;
else if (x < q.key)
q.left = new;
else
q.right = new;
return;
}
8) 이진 트리의 삭제
- 먼저 탐색 연산을 수행
- 삭제할 노드의 위치를 알아야 하므로 트리를 탐색함
- 탐색하여 찾은 노드를 삭제함
- 노드의 삭제 후에도 이진 탐색 트리를 유지해야 하므로 삭제 노드의 경우에 대한 후속 처리가 필요함
- 후속 처리 : 이진 탐색 트리의 재구성 작업
- 삭제할 노드의 경우
- 삭제할 노드가 단말 노드인 경우 : 차수가 0인 경우
- 삭제할 노드가 하나의 자식 노드를 가진 경우 : 차수가 1인 경우
- 삭제할 노드가 두 개의 자식 노드를 가진 경우 : 차수가 2인 경우
deleteBST(bsT, x)
{
p = 삭제할 노드;
parent = 삭제할 노드의 부모 노드;
if (p == null)
return;
if (p.left == null && p.right == null)
{
if (parent.left == p)
parent.left = null;
else
parent.right = null;
}
else if (p.left == null || p.right == null)
{
if (p.left != null)
{
if (parent.left == p)
parent.left = p.left;
else
parent.right = p.left;
}
}
else
{
if (parent.left == p)
parent.left = p.right;
else
parent.right = p.right;
}
else if (p.left != null && p.right != null)
{
q = maxNode(p.left);
p.key = q.key;
deleteBST(p.left, p.key);
}
}
9) 이진 트리의 구현
#include<stdio.h>
#include<stdlib.h>
typedef struct treeNode
{
char key;
treeNode *left;
treeNode *right;
} treeNode;
typedef char element;
treeNode* insertNode(treeNode *p, char x)
{
treeNode *newNode;
if (p == NULL)
{
newNode = (treeNode*)malloc(sizeof(treeNode));
newNode->key = x;
newNode->left = NULL;
newNode->right = NULL;
return newNode;
}
else if (x < p->key)
p->left = insertNode(p->left, x);
else if (x > p->key)
p->right = insertNode(p->right, x);
else
printf("\n 이미 같은 키가 있습니다. \n");
return p;
}
void deleteNode(treeNode* root, element key)
{
treeNode* parent, * p, * succ, * succ_parent;
treeNode* child;
parent = NULL;
p = root;
while ((p != NULL) && (p->key != key))
{
parent = p;
if (key < p->key)
p = p->left;
else
p = p->right;
}
if (p == NULL)
{
printf("\n 찾는 키가 이진트리에 없습니다. \n");
return;
}
if ((p->left == NULL) && (p->right == NULL))
{
if (parent != NULL)
{
if (parent->left == p)
parent->left = NULL;
else
parent->right = NULL;
}
else
root = NULL;
}
else if ((p->left == NULL) || (p->right == NULL))
{
if (p->left != NULL)
child = p->left;
else
child = p->right;
if (parent != NULL)
{
if (parent->left == p)
parent->left = child;
else
parent->right = child;
}
else
root = child;
}
else
{
succ_parent = p;
succ = p->left;
while (succ->right != NULL)
{
succ_parent = succ;
succ = succ->right;
}
if (succ_parent->left == succ)
succ_parent->left = succ->left;
else
succ_parent->right = succ->left;
p->key = succ->key;
p = succ;
}
free(p);
}
treeNode* searchBST(treeNode *root, char x)
{
treeNode* p;
p = root;
while (p != NULL)
{
if (x < p->key)
p = p->left;
else if (x == p->key)
return p;
else
p = p->right;
}
printf("\n 찾는 키가 없습니다. \n");
return p;
}
void displayInorder(treeNode* root)
{
if (root)
{
displayInorder(root->left);
printf("%c_", root->key);
displayInorder(root->right);
}
}
void menu()
{
printf("\n*-----------------------------*");
printf("\n\t1 : 트리 출력");
printf("\n\t2 : 문자 삽입");
printf("\n\t3 : 문자 삭제");
printf("\n\t4 : 문자 검색");
printf("\n\t5 : 종료");
printf("\n*-----------------------------*");
printf("\n메뉴입력 >> ");
}
int main()
{
treeNode *root = NULL;
treeNode *foundedNode = NULL;
char choice, key;
root = insertNode(root, 'G');
insertNode(root, 'I');
insertNode(root, 'H');
insertNode(root, 'D');
insertNode(root, 'B');
insertNode(root, 'M');
insertNode(root, 'N');
insertNode(root, 'A');
insertNode(root, 'J');
insertNode(root, 'E');
insertNode(root, 'Q');
while (1)
{
menu();
choice = getchar(); getchar();
switch (choice - '0')
{
case 1: printf("\t[이진트리 출력] ");
displayInorder(root);
break;
case 2: printf("삽입할 문자를 입력하세요 : ");
key = getchar(); getchar();
insertNode(root, key);
break;
case 3: printf("삭제할 문자를 입력하세요 : ");
key = getchar(); getchar();
deleteNode(root, key);
break;
case 4: printf("찾을 문자를 입력하세요 : ");
key = getchar(); getchar();
foundedNode = searchBST(root, key);
if (foundedNode != NULL)
printf("\n %c를 찾았습니다. \n", foundedNode->key);
else
printf("\n 문자를 찾지 못했습니다. \n");
break;
case 5:
return 0;
default: printf("\n 없는 메뉴입니다. 메뉴를 다시 선택하세요. \n");
break;
}
}
}