c언어로 쉽게 풀어쓴 자료구조 — 8장 트리

8.1 트리(TREE)

먼저 트리는 부모-자식 관계의 노드들로 이루어진다.

리스트, 스택, 큐는 선형 자료구조인 반면에, 트리는 계층적인 구조를 나타내는 비선형 자료구조이다.

여기서 선형 자료구조는 자료를 구성하는 원소들의 앞뒤관계가 1:1인 구조를 말하고 비선형 자료구조는 자료를 구성하는 원소들의 앞뒤 관계가 1:N 또는 N:N인 구조를 말한다.

트리의 용어들

노드 : 트리의 구성요소

루트 : 부모가 없는 노드

레벨 : 트리의 각층 번호

높이 : 트리의 최대레벨

차수 : 노드가 가지고있는 자식노드의 개수

간선 : 트리에 연결된 모든선

서브트리 : 하나의 노드와 자손들로 이루어진 트리

형제노드 : 같은 레벨의 노드

후손노드 : 임의의 노드 하위에 연결된 모든 노드

단말노드 : 자식이 없는 노드

비단말노드 : 하나이상의 자식을 가지는 노드

8.2 트리의 종류

트리를 컴퓨터 메모리상에서 표현하는 방법에는 ➊일반트리와 ➋이진트리 방식이 있다.

➊일반트리 : 각 노드들은 서로 다른 개수의 자식노드를 가진다. 단점으로는 노드의 크기가 일정하지 않아 프로그램이 복잡해진다.

➋이진트리 : 모든 노드가 2개의 서브트리를 가지고 있는 트리이다.

이진트리의 성질

➊n개의 노드를 가진 이진트리는 n-1의 간선을 가진다

➋높이가 h인 이진트리는 최소 h(높이)개의 노드를 가지며, 최대 2의 h승 -1개의 노드를 가진다.

➌n개의 노드를 가지는 이진트리의 높이는 최대 n이거나 최소[log2(n+1)]이 된다.

이진트리의 분류

❶포화 이진트리 : 트리의 각 레벨에 노드가 꽉 차있는 이진트리

❷완전 이진트리 : 레벨 1부터 k-1까지는 노드가 모두 채워져 있고 마지막 레벨 k에서는 왼쪽부터 오른쪽으로 노드가 순서대로 채워져 있는 이진트리

❸기타 이진트리

8.3 이진트리의 표현

➊배열 표현법 : 모든 이진트리를 포화 이진트리라고 가정하고 각 노드에 번호를 붙여서 그 번호를 배열의 인덱스로 삼아 노드의 데이터를 배열에 저장하는 방법

➋링크 표현법 : 포인터를 이용하여 부모노드가 자식노드를 가리키게 하는 방법

링크의 구현

노드는 구조체로 표현하고 링크는 포인터로 표현한다.

❶헤더파일 선언

#include <stdio.h>

#include <stdlib.h>

❷트리의 요소를 구조체로 정의

typedef struct TreeNode {

struct TreeNode *left;

int data;

struct TreeNode *right;

}TreeNode;

❸main함수

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;

free(n1);

free(n2);

free(n3);

8.4 이진트리의 순회

순회한다는 것은 이진트리에 속하는 모든 노드를 한번씩 방문하여 노드가 가지고 있는 데이터를 목적에 맞게 처리하는 것을 의미한다.

이진트리를 순회하는 표준적인 방법에는 ❶전위, ❷중위, ❸후위등 3가지와 ❹레벨 순회가 있다.

❶전위 순회 : 루트를 먼저 방문하고 그 다음에 왼쪽서브트리, 마지막으로 오른쪽 서브트리를 방문하는 것이다.

void preorder(TreeNode *root) { //전위 순회 함수

if (root != NULL) {

printf(“[%d] “, root->data);

preorder(root->left);

preorder(root->right);

}

}

❷중위 순회 : 먼저 왼쪽 서브트리, 루트, 오른쪽 서브트리 순으로 방문한다.

void inorder(TreeNode *root) {

if (root != NULL) {

inorder(root->left);

printf(“[%d] “, root->data);

inorder(root->right);

}

}

❸후위 순회 : 왼쪽 서브트리, 오른쪽 서브트리, 루트 순으로 방문한다.

void postorder(TreeNode *root) {

if (root !=NULL) {

postorder(root->left);

postorder(root->right);

printf(“[%d] “, root->data);

}

}

❹레벨 순회 : 큐를 사용하여 각 노드를 레벨 순으로 검사하는 순회 방법이다.

8.5 트리의 응용

수식 트리, 디렉토리 용량계산, 스레드 이진트리 등에 활용되고 있습니다.

8.6 이진 탐색 트리

이진탐색 트리(binary search tree)는 이진트리 기반의 탐색을 위한 자료 구조이다.

이진탐색 트리의 정의

key(왼쪽서브트리) ≤ key(루트노드) ≤ key(오른쪽서브트리)

❶왼쪽 서브트리 키들은 루트키보다 작다

❷오른쪽 서브트리 키들은 루트키보다 크다

❸왼쪽과 오른쪽 서브트리도 이진탐색트리이다.

이진탐색 트리 구현방법

❶반복적 방법

TreeNode *search_while(TreeNode *node, element 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, element 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);

}

이진탐색 트리에서의 삽입연산

❶같은 키값을 갖는 노드가 없어야 하므로 탐색수행

TreeNode* insert_node(TreeNode* node, element key) {

if (node == NULL) {

return new_node(key);

}

if (key < node->data) {

node->left = insert_node(node->left, key);

}

else if (key > node->data) {

node->right = insert_node(node->right, key);

}

return node;

}

❷탐색이 실패한 위치에 원소 삽입

TreeNode* new_node(element item) {

TreeNode *temp = (TreeNode*)malloc(sizeof(TreeNode));

temp->data = item;

temp->left = NULL;

temp->right = NULL;

return temp;

}

이진탐색 트리에서의 삭제연산

삭제하려는 노드가 ❶단말노드일 경우. ❷왼쪽이나 오른쪽 서브트리중 하나만 가지고 있는 경우. ❸두 개의 서브트리 모두 가지고 잇는 경우로 나뉜다.

❶삭제하려는 노드가 단말노드인 경우

단말노드의 부모노드를 찾아서 부모노드안의 링크필드를 NULL로 만들어서 연결을 끊으면 된다.

❷삭제하려는 노드가 하나의 서브트리만 연결된 경우

자기노드는 삭제하고 서브트리는 자기 노드의 부모노드에 붙여주면 된다.

if(root->left == NULL){

TreeNode *temp = root->right;

free(root);

return temp;

}

else if (root->right == NULL) {

TreeNode *temp = root->left;

free(root);

return temp;

}

❸삭제하려는 노드가 두 개의 서브르리와 연결된 경우

삭제노드와 가장 비숫한 값을 가진 노드를 삭제노드 위치로 가져온다.

(왼쪽 서브트리에서 가장 큰값 또는 오른쪽 서브트리에서 가장 작은 값)

TreeNode *temp = min_value_node(root->right);

root->data = temp->data;

root->right = delete_node(root->right, temp->data);

8.7 이진 탐색 트리의 분석

이진 탐색 트리에서의 탐색, 삽입, 삭제 연산의 시간 복잡도는 트리의 높이를 h라고 했을때 h에 비례하므로 O(log2h)이다.

최악의 경우인 경사트리는 높이가 n이 되므로 시간복잡도는 O(n)이 된다.