1. 트리 기본
트리는 한 개 이상의 노드로 이루어진 유한 집합으로, 계층적인 자료를 표현하는데 적합한 자료구조이다. 항목들이 순차적으로 저장되는 선형 자료구조는 각 항목간의 관계를 표현하기 어려워 더이상 적합하지 않게 된다.
트리 자료구조와 관련된 용어는 위 그림으로 정리하면 된다. 위 그림에 더하여, 노드의 차수는 어떤 노드가 가지고 있는 자식 노드의 개수를 의미한다는 것만 추가적으로 정리하자.
(더하여, 책에서는 루트의 레벨을 1로 놓고 트리의 높이 등을 계산하고 있다는 점이 위 그림의 표현과 차이점이다)
2. 이진트리
(1) 정의
이진 트리는 모든 노드가 2개의 서브 트리를 가지고 있는 트리로, 가장 많이 쓰이는 트리라고 한다. 여기서 서브 트리는 공집합일 수 있기 때문에 모든 노드의 차수는 2 이하가 된다.
이진트리는 다음과 같이 순환적으로 정의된다.
(1) 공집합 이거나
(2) 루트와 왼쪽 서브 트리, 오른쪽 서브 트리로 구성된 노드들의 유한 집합. 여기서 이진트리의 서브트리들은 모두 이진트리여야 한다.
이진트리의 정의로부터 다음과 같은 특징이 도출된다.
- 이진트리의 모든 노드는 차수가 2이하이다.
- 일반 트리와 달리 이진트리는 노드를 하나도 갖지 않을 수 도 있다.
- 일반 트리와 달리 이진트리에서는 서브 트리간에 순서가 존재하여 왼쪽 서브 트리와 오른쪽 서브 트리를 구별한다.
- n개의 노드를 가진 이진트리는 정확하게 n-1의 간선을 갖는다.
(2) 이진트리의 분류
- 포화 이진트리(Full Binary Tree)는 트리의 각 레벨에 노드가 꽉 차있는 이진트리이다.
(그림에서 처럼 포화 이진트리를 Perfect BT라 하고, Full BT를 전 이진트리라 하여 모든 노드의 차수가 0 또는 2인 트리라고 정리된 곳이 굉장히 많아 이것이 보편적인 정리같긴 하지만, 일단은 교재를 기준으로 정리하였음) - 완전 이진트리(Complete Binary Tree)는 마지막 레벨 전까지는 노드가 모두 채워져 있고 마지막 레벨에서는 왼쪽부터 노드가 순서대로 채워져 있는 이진트리이다.
(3) 이진트리의 표현
컴퓨터 프로그램 안에서 이진트리는 두 가지 방법으로 표현할 수 있는데, 각각 1) 배열을 이용하는 방법과 2) 포인터를 이용하는 방법이다.
배열 표현법은 노드에 번호를 부여하고 해당 번호를 배열의 인덱스가 되도록 구현하는 방법으로, 위 그림을 보면 직관적으로 이해할 수 있다. 배열로 이진트리를 표현하면 완전 이진트리 같은 경우와 달리 일반적인 트리는 공간의 낭비가 커지게 된다. 그림에서 0번째 인덱스를 비워놓았는데, 이로 인해 다음과 같은 공식이 성립하게 된다.
- 노드 i의 부모 노드 인덱스 = i / 2
- 노드 i의 왼쪽 자식 노드 인덱스 = i * 2
- 노드 i의 오른쪽 자식 노드 인덱스 = i * 2 + 1
링크 표현법에서는 트리의 노드가 구조체로 표현되고, 각 노드는 포인터를 갖고 있다. 이 포인터를 통해 노드를 연결하여 트리를 표현할 수 있게 된다. 하나의 노드는 그림에서와 같이 3개의 필드를 갖는데, 각각 데이터를 저장하는필드와 왼쪽 자식노드, 오른쪽 자식노드를 가리키는 필드이다. 이 링크 표현법으로 표현한 트리는 연결 리스트와 아주 유사한데, 연결 리스트가 1차원적인 연결된 구조라면 링크 표현법으로 구현한 이진 트리는 2차원적으로 연결된 구조라고 할 수 있다.
(4) 이진트리의 순회
이진트리의 순회라 함은 이진트리에 속하는 모든 노드를 방문하여 노드가 가지고 있는 데이터를 목적에 맞게 처리하는 것을 말한다. 데이터를 선형적으로 저장하고 있는 선형 자료구조와 달리 트리에서는 여러가지 순서로 노드의 데이터에 접근할 수 있다.
- 전위순회 : 루트 -> 왼쪽 서브트리 -> 오른쪽 서브트리 순으로 방문
- 중위순회 : 왼쪽 서브트리 -> 루트 -> 오른쪽 서브트리 순으로 방문
- 후위순회 : 왼쪽 서브트리 -> 오른쪽 서브트리 -> 루트 순으로 방문
생각보다 순회방법이 간단하게 표현되었는데, 이진트리의 순환적인 정의로부터 비롯된 것으로 생각하면 된다. 즉, 왼쪽과 오른쪽 서브트리 모두 이진트리이기 때문에 각 서브트리에서 다시 순환적으로 순회를 반복하게 되는 것이다.
3. 이진 탐색 트리와 그 구현
(1) 정의
이진 탐색 트리는 이진트리의 특성을 가지면서 각 노드에 저장된 키(값)이 이진 탐색이 가능하도록 구성된 트리이다. 이진 탐색 트리는 모든 노드에 대해 다음 조건을 만족한다.
- 왼쪽 서브트리의 모든 노드의 값은 루트 키보다 작다
- 오른쪽 서브트리의 모든 노드의 값은 루트 키보다 크다
- 왼쪽과 오른쪽 서브 트리도 이진 탐색 트리이다
이러한 특성에 의해 BST는 중위순회를 통해 저장된 값을 오름차순 정렬된 형태로 출력할 수 있다는 중요한 특징이 있다. 즉, 정렬된 데이터를 다룰 때 유리한 자료구조이다.
(2) 기본 연산
- 탐색 : 루트부터 시작하여 현재 노드의 키와 찾는 키를 비교해가며 왼쪽 또는 오른쪽 서브트리로 이동한다. 최악의 경우 트리의 높이만큼 탐색하게 되므로 시간복잡도는 O(h)이다. 일반적으로 h = log n 이므로 O(log n)이 될 것이나, 이는 좌우의 서브 트리가 균형을 이룰 경우이다. 만약 한쪽으로 치우치는 경사 트리와 같은 최악의 경우에는 거의 선형 탐색과 같이 O(n)이 된다.
- 삽입 : 탐색과 같은 방식으로 적절한 위치를 찾아 새로운 노드를 삽입한다.
- 삭제 : 삭제할 노드의 위치를 찾고, 1) 단말 노드는 그냥 삭제, 2) 자식이 하나인 노드는 자식을 부모와 연결, 3) 자식이 둘인 노드는 오른쪽 서브트리에서 가장 작은 값 또는 왼쪽 서브트리에서 가장 큰 값을 찾아 교체한 뒤 해당 노드를 삭제한다.
(3) 구현 : 연락처 시스템
BST를 활용하여 다음과 같은 동작을 하는 프로그램을 구현하였다.
binary_search_tree.c
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <string.h>
#include "./binary_search_tree.h"
TreeNode* create_tree() {
TreeNode* root = malloc(sizeof(TreeNode));
if (root == NULL){
printf("Error: malloc failed\n");
return NULL;
}
root->left = NULL;
root->right = NULL;
return root;
}
int compare(char name1[], char name2[]) {
return strcmp(name1, name2);
}
TreeNode* new_node(element item) {
TreeNode* node = malloc(sizeof(TreeNode));
node->key = item;
node->right = NULL;
node->left = NULL;
return node;
}
TreeNode* insert(TreeNode* tree, element item) {
if (tree == NULL) return new_node(item);
else {
if (compare(item.name, tree->key.name) < 0) tree->left = insert(tree->left, item);
else if (compare(item.name, tree->key.name) > 0) tree->right = insert(tree->right, item);
return tree; // 겹치는 키는 없다고 가정했음을 기억!
}
}
TreeNode* delete_node(TreeNode* tree, element item) {
if (tree == NULL) return tree;
else {
if (compare(item.name, tree->key.name) < 0) tree->left = delete_node(tree->left, item);
else if (compare(item.name, tree->key.name) > 0) tree->right = delete_node(tree->right, item);
else {
if (tree->left == NULL) {
TreeNode* tmp = tree->right;
free(tree);
return tmp;
}
else if (tree->right == NULL) {
TreeNode* tmp = tree->left;
free(tree);
return tmp;
}
else {
TreeNode* tmp = tree->right;
while (tmp->left != NULL) {
tmp = tmp->left;
}
tree->key = tmp->key;
tree->right = delete_node(tree->right, tmp->key);
}
}
return tree;
}
}
TreeNode* search(TreeNode* tree, char name[]) {
while (tree != NULL) {
if (compare(name, tree->key.name) == 0) return tree;
else if (compare(name, tree->key.name) < 0) tree = tree->left;
else tree = tree->right;
}
return tree;
}
bool is_empty(TreeNode* tree) {
return tree == NULL;
}
void clear(TreeNode* tree) {
if (tree == NULL) return;
clear(tree->left);
clear(tree->right);
free(tree);
}
void print_tree(TreeNode* tree, int* counter) {
if (tree != NULL) {
print_tree(tree->left, counter);
printf("%d. Name: %s, Phone Number: %s, Email: %s\n", (*counter)++, tree->key.name, tree->key.phone, tree->key.email);
print_tree(tree->right, counter);
}
}
address.c
#include <stdio.h>
#include "address.h"
TreeNode* create_address() {
TreeNode* address = create_tree();
return address;
}
TreeNode* add_address(TreeNode* address) {
element data;
printf("Name : ");
scanf(" %[^\n]", data.name);
printf("Phone Number : ");
scanf(" %[^\n]", data.phone);
printf("Email : ");
scanf(" %[^\n]", data.email);
printf("Contact '%s' added successfully.\n\n", data.name);
return insert(address, data);
}
void search_address(TreeNode* address) {
char keyName[NAME_LEN + 1];
printf("Search Name : ");
scanf(" %[^\n]", keyName);
TreeNode* target;
target = search(address, keyName);
printf("Search Result : \n");
if (target == NULL) printf("There is no one named %s.\n\n", keyName);
else {
display_node(target);
printf("\n");
}
}
TreeNode* delete_address(TreeNode* address) {
char keyName[NAME_LEN + 1];
printf("Delete Name : ");
scanf(" %[^\n]", keyName);
TreeNode* target;
target = search(address, keyName);
if (search(address, keyName) == NULL) {
printf("There is no one named %s.\n\n", keyName);
return address;
}
else {
printf("Contact '%s' deleted successfully.\n\n", keyName);
return delete_node(address, target->key);
}
}
void display_node(TreeNode* target) {
printf("Name : %s, Phone Number : %s, Email : %s\n", target->key.name, target->key.phone, target->key.email);
}
void display_address(TreeNode* address) {
if (is_empty(address)) printf("There is no contact!!!\n");
else {
int counter = 1;
printf("Displaying all contacts:\n");
print_tree(address, &counter);
}
printf("\n");
}
main.c
#include <stdio.h>
#include <stdbool.h>
#include "./include/binary_search_tree.h"
#include "./include/address.h"
int main() {
TreeNode* address = NULL;
while (true) {
printf("Please enter a command [1: add, 2: search, 3: delete, 4: display all, 5: quit]:");
int command;
if (scanf("%d", &command) != 1) {
printf("wrong input!!!\n");
while (getchar() != '\n');
continue;
}
switch (command) {
case 1:
address = add_address(address);
break;
case 2:
search_address(address);
break;
case 3:
address = delete_address(address);
break;
case 4:
display_address(address);
break;
case 5:
clear(address);
return 0;
default:
printf("wrong input!!!\n");
break;
}
}
}
(4) 구현 후기
- BST와 같이 정의 자체가 재귀적으로 되어 있는 자료구조의 경우, 많은 동작 함수들이 재귀적으로 구현된다는 점이 인상적이었다.
- BST 구현의 경우 이처럼 재귀적으로 구현된다는 점과 함께, delete_node 함수의 구현을 유의해야 한다는 점을 기억하면 될 것 같다.
'독서 > C언어로 쉽게 풀어쓴 자료구조' 카테고리의 다른 글
| [CDS] chapter 10 : 그래프 ① (0) | 2025.04.17 |
|---|---|
| [CDS] chapter 9 : 우선순위 큐 (0) | 2025.03.10 |
| [CDS] chapter 7 : 연결리스트 ② (0) | 2025.02.12 |
| [CDS] chapter 6 : 연결리스트 ① (0) | 2025.01.27 |
| [CDS] chapter 5 : 큐 (0) | 2025.01.11 |
