트리는 계층적인 자료를 표현하는데 적합한 자료구조이다
트리의 구성 요소에 대해 먼저 알아보자
- 트리는 노드와 엣지의 결합으로 이루어 지는데, 트리는 한 개 이상의 노드로 이루어지고 이러한 노드를 엣지로 연결한다
트리는 여러 관계를 지닌다
- 루트 노드 & 서브 트리 : 트리 중 하나의 노드를 루트 노드라고 하면 해당 노드를 제외한 아래 노드들을 서브 트리라고 칭한다
- 부모 관계 : B는 E와 F의 부모 / E와 F는 B의 자식
- 형제 관계 : B와 C와 D는 형제 / E와 F는 형제 / H와 I와 J는 형제
- 조상 & 자손 : D를 기준으로 H, I, J, K는 자손 노드, A는 조상 노드
트리는 여러 정보를 가지고 있다
- 단말 노드 : 자식 노드가 없는 노드 E, F, G, I, J, K
- 비단말 노드 : 자식 노드가 존재하는 노드 A, B, C, D, H
- 차수 (Degree) : 자식 노드의 개수 / 트리의 차수는 트리가 가진 노드의 차수 중 가장 큰 값
ex) 위 트리의 차수는 3 : D의 자식 노드 수가 3이기 때문
- 레벨 (Level) : 층의 갯수
- 높이 (Height) : 최대 레벨
이진트리
모든 노드가 최대 2개의 서브 트리를 가지는 트리
- 구조체 정의
typedef struct Node {
int data;
struct Node *left, *right;
} Node;
- 성질
① n개의 노드를 가진 이진트리는 n - 1개의 엣지로 구성됨
② 높이가 h인 이진트리는 최소 h개의 노드를 가지며 최대 \(2^h\)-1개의 노드를 가짐
③ n개의 노드를 가지는 이진트리의 높이는 최대 n부터 최소 ⌈\(\log n\)⌉
- 종류
① 포화 이진트리 : 트리의 각 레벨에 노드가 꽉 차있는 이진트리
② 완전 이진트리 : 트리의 마지막 전 레벨까지는 노드가 가득 차있고, 마지막 레벨은 노드가 왼쪽부터 순서대로 존재하는 이진트리
③ 기타 이진트리 : 이진트리의 성질만 만족 시키는 트리
- 순회 : 트리는 데이터를 선형으로 저장하고 있지 않기 때문에 순회하는 방법이 4가지 존재한다
① 전위 순회 (pre-order) : P → L → R / 루트 노드가 제일 처음
② 중위 순회 (in-order) : L → P → R / 루트 노드가 가운대
③ 후위 순회 (post-order) : L → R → P / 루트 노드가 제일 마지막
④ 레벨 순회 : 각 노드를 레벨 순으로 검사하는 순회 방법 / 큐를 사용
순회를 수도 코드로 표현하면 아래와 같다
// 전위 순회
pre_order(Node *p)
{
if (p != NULL)
{
print p -> Data
pre_order(p -> left)
pre_order(p -> right)
}
}// 중위 순회
in_order(Node *p)
{
if (p != NULL)
{
in_order(p -> left)
print p -> Data
in_order(p -> right)
}
}// 후위 순회
post_order(Node *p)
{
if (p != NULL)
{
post_order(p -> left)
post_order(p -> right)
print p -> Data
}
}// 레벨 순회
level_order(Node *p)
{
queue 생성
if (p == Null) then return
enqueue(queue, p)
while (큐에 데이터가 존재하면)
{
x <- dequeue(queue)
print x
if (x -> left != NULL) then enqueue(queue, x -> left)
if (x -> right != NULL) then enqueue(queue, x -> right)
}
}
위 그림으로 각각의 순회를 진행하면 아래와 같다
전위 순회 : A → B → D → C → E → G → F
중위 순회 : D → B → A → G → E → C → F
후위 순회 : D → B → G → E → F → C → A
레벨 순회의 경우에는 아래 그림과 같은 방법으로 진행된다
이러한 순회는 데이터 처리 순서를 고려하여 선택하면 된다
이진 탐색 트리 (Binary Search Tree : BST)
이진 탐색 트리는 아래 성질을 만족하는 트리이다
- 성질
① 모든 원소의 키는 유일한 키를 가짐
② 왼쪽 서브 트리 키들은 루트 키보다 작음
③ 오른쪽 서브 트리의 키들은 루트의 키보다 큼
④ 왼쪽과 오른쪽 서브 트리도 이진 탐색 트리
- 탐색
탐색에는 순환과 반복 두가지 방법이 존재한다
// 순환적인 방법
Node* search(Node* 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);
}// 반복적인 방법
Node* search(Node* 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;
}
- 삽입
이진 탐색 트리의 삽입 연산은 탐색 연산을 먼저 수행한 후 진행할 수 있다
탐색 연산을 진행 후, 탐색을 실패한 위치가 새 노드를 삽입할 위치가 된다
Node* insert(Node* node, int key)
{
// 빈 트리일 때
if (node == NULL) return new_node(key);
// 트리가 비어있지 않을 때
if (key < node -> key)
node -> left = insert(node -> left, key);
else if (key > node -> key)
node -> right = insert(node -> right, key);
// 변경된 루트 포인터 반환
return node;
}
Node* new_node(int item)
{
Node* temp = (Node*)malloc(sizeof(Node));
temp -> key = item;
temp -> left = temp -> right = NULL;
return temp;
}
- 삭제
이진 탐색 트리의 삭제 연산도 탐색 연산을 수행한 후 진행할 수 있다
그러나 삭제 연산은 세 가지 경우로 나누어 진행해야 한다
① 삭제하려는 노드가 단말 노드일 경우 → 그냥 삭제
② 삭제하려는 노드가 서브 트리를 하나만 가지고 있는 경우 → 삭제 후 서브 트리를 부모 노드에 붙임
③ 삭제하려는 노드가 두개의 서브 트리를 가지고 있는 경우 → 삭제하려는 노드와 가장 값이 비슷한 노드를 해당 자리에 위치 시켜야 함 (왼쪽 서브트리의 가장 오른쪽 노드 또는 오른쪽 서브트리의 가장 왼쪽 노드)
Node* delete(Node* root, int key)
{
// 빈 트리일 때
if (root == NULL) return root;
// 키 값이 루트노드보다 작을 때
if (key < root -> key)
root -> left = delete(root -> left, key);
// 키 값이 루트노드보다 클 때
else if (key > root -> key)
root -> right = delete(root -> right, key);
// 키 값이 루트노드와 같을 때 → 해당 노드 삭제
else
{
// ①, ②의 경우
// 왼쪽 서브트리가 없을 때
if (root -> left == NULL)
{
Node* temp = root -> right;
free(root);
return temp
}
// 오른쪽 서브트리가 없을 때
else if (root -> right == NULL)
{
Node* temp = root -> left;
free(root)
return temp;
}
// ③의 경우
// temp = 후계자
Node* temp = min_value_node(root -> right);
// 후계자 노드를 삭제하려는 노드에 복사
root -> key = temp -> key;
// 후계자 노드 삭제
root -> right = delete(root -> right, temp -> key);
}
return root;
}
// 후계자 = 왼쪽 서브트리의 가장 오른쪽 값
Node* min_value_node(Node* node)
{
Node* current = node;
while (currnet -> left != NULL)
current = current -> left;
return current;
}
- 성능
이진 탐색 트리에 n개의 노드가 존재한다고 가정했을 때, 해당 트리의 높이는 ⌈\(\log n\)⌉가 된다
이진 탐색 트리의 서브 트리가 균형을 이룰 경우, 모든 연산의 평균 시간 복잡도는 O(\(\log n\))가 된다
그러나 이진 탐색 트리가 균형을 이루지 않는 경우에는 시간 복잡도가 증가하게 된다
대표적으로 최악의 경우인 경사 트리는 O(n)의 시간 복잡도를 가지게 된다
이러한 한계로 인해 트리의 높이를 ⌈\(\log n\)⌉로 한정시키는 균형 기법이 등장했는데, 나중에 다루려고 한다