1. 트리
주요용어
- 트리 : 트리는 논리적 계층이 있는 구조이며, 트리를 구성하는 항목을 노드(node) 혹은 점(vertex)이라고 함
- 루트 : 트리에서 부모를 갖지 않은 노드
- 진입 차수 : 트리에 있는 어떤 노드에 대해 그 노드로 들어오는 선의 개수
- 진출 차수 : 트리에 있는 어떤 노드에 대해 그 노드에서 나가는 선의 개수
- 내부 노드 : 루트도 잎도 아닌 노드
- 형제(sibling) : 같은 부모를 갖는 노드들
- 포화 이진 트리 : 이진 트리에서 각 레벨이 허용되는 최대 개수 노드를 가지는 트리
- 완전 이진 트리 : 높이가 k인 이진 트리가 레벨 0부터 k-2까지 다 채우고 마지막 k-1 레벨에서 왼쪽부터 오른쪽으로 노들들이 차례로 채워진 트리
- 순회(traverse) : 트리의 각 노드를 빠짐없이 한 번씩만 방문하는 것
내용
- 트리의 정의
- 트리의 구성
- 노드: 트리의 항목/트리에 저장되는 데이터의 묶음
- 부모노드-자식노드: 상하 계층구조가 있고 직접적으로 연결된 노드로서 상위계층의 부모노드와 하위계층의 자식 노드
- 트리의 레벨
- 노드의 레벨: 루트로부터 그 노드까지 이어진 선(경로)의 길이
- 트리의 높이: 루트로부터 가장 멀리 있는 노드까지 이어진 선(경로)의 길이에 1을 더한 값
- 이진 트리
- 이진 트리의 정의
- 모든 노드의 차수가 2 이하인 트리
- 수학적으로 이진트리의 구성에 관한 이론을 정리하기 쉽고, 컴퓨터 내부에서 구현하기도 효율적임
- 모든 노드가 2개 이하의 자식노드를 가지므로 일반성을 잃지 않고 ‘오른쪽’, ‘왼쪽’이라는 방향개념을 부여할 수도 있음
- 오른쪽 노드, 왼쪽 노드의 개념적 접근도 있음
- 포화 이진 트리
- 이진 트리의 각 레벨에서 허용되는 최대 개수 노드를 가지는 트리
- 완전 이진 트리
- 높이가 k인 이진 트리가 ‘0레벨’부터 ‘k-2레벨’까지 다 채우고, 마지막 ‘k-1 레벨’에서 왼쪽부터 오른쪽으로 노드들이 차례로 채워진 이진트리
- 이진 트리의 구현
- 배열을 이용한 이진 트리의 구현
- 트리가 완전 이진 트리 또는 포화 이진 트리인 경우 낭비되는 공간이 없어 효율적임
- 트리가 깊어질수록 기억장소 낭비가 2의 거듭제곱에 비례하며 낭비가 심해짐
- 포인터를 이용한 이진 트리의 구현
이진 트리 연산
-
이진 트리 순회
- 이진 트리의 전위 순회
- 이진 트리의 후위 순회
- 이진 트리의 순회 알고리즘
- 전위 순회(PLR)
struct node *nodeptr;
void preorder(struct node *tree_ptr) {
if (tree_ptr) {
printf("%d", tree_ptr -> info);
preorder(tree_ptr->left);
preorder(tree_ptr->right);
}
}
- 중위 순회(LPR)
struct node *nodeptr;
void preorder(struct node *tree_ptr) {
if (tree_ptr) {
preorder(tree_ptr->left);
printf("%d", tree_ptr -> info);
preorder(tree_ptr->right);
}
}
-
이진 트리 생성/삽입/삭제
- 일반적인 이진 트리를 생성하는 것은 연결 리스트 연산을 사용함
- 첫 노드를 생성하면 루트 노드가 되고, 새로운 노드를 추가하려면 연결 리스트의 삽입 연산을 사용함
- 노드를 삭제할 떄, 삭제하려는 노드가 리프노드인 경우는 해당 노드를 가리키는 포인터를 null로 지정하면 됨
- 리프노드가 아닌 경우에는 삭제하려는 노드의 자식노드에 대한 처리를 추가로 해주어야 함
-
이진 트리 노드 개수 세기
int get_node_count(nodeptr *root) {
if (root == null) return 0;
int result = 1;
result = get_node_count((nodeptr*) root -> left)
+
get_node_count((nodeptr*) root -> right);
reurn result;
}
int get_leaf_count(nodeptr *root) {
int root = 0;
if (root == null) {
return 0;
} elst if (root->left == null && root->right == null) {
return 1;
}
result = get_leaf_count((nodeptr*) root -> left)
+
get_leaf_count((nodeptr*) root -> right);
reurn result;
}
요약
- 트리는 논리적 계층이 있는 구조입니다.
- 트리를 구성하는 항목을 노드 혹은 정점(vertex)이라고 합니다.
- 트리에서 루트는 부모를 갖지 않은 노드입니다.
- 트리에 있는 어떤 노드에 대해 그 노드로 들어오는 선의 개수를 진입 하수, 나가는 선의 개수를 진출 차수라고 합니다.
- 트리에서 각 노드의 차수는 진출 차수로 정의합니다.
- 트리이 차수는 트리 내의 각 노드의 차수 가운데 최대 차수로 정의합니다.
- 루트도 잎도 아닌 노드를 내부 노드라 하고 같은 부모를 갖는 노드를 형제라고 합니다.
- 트리에서 각 노드의 레벨은 루트로부터 그 노드까지 이어진 경로의 길이로 정합니다.
- 트리는 데이터의 계층 관계, 포함 관계 등을 나타내는 자료구조입니다.
- 트리에 속한 모든 노드의 차수가 2 이하인 트리를 이진 트리라고 합니다.
- 이진 트리에서 각 레벨이, 허용되는 최대 개수 노드를 가질 때 그 트리를 포화 이진 트리라고 합니다.
- 높이가 k인 이진 트리가 레벨 0부터 레벨 k-2까지 다 채우고 마지막 k-1레벨에서 왼쪽부터 오른쪽으로 노드들이 차례로 채워졌을 떄 완전 이진 트리라고 합니다.
- 트리의 각 노드를 빠짐없이 한 번씩만 방문하는 것을 순회라고 합니다.
- 루트를 방문하는 순서에 따라 각각 전위 순회, 중위 순회, 후위 순회라고 구분하여 부릅니다.
2. 스레드 트리
주요용어
- 스레드(thread) : 정해진 순회 방법에 따른 방문순서를 유지하는 포인터
- 스레드 트리 : 스레드라는 포인터를 갖는 이진 트리
- 오른쪽 스레드 : 정해진 순회 순서에 따른 그 노드의 후속 노드를 가리킴
- 왼쪽 스레드 : 정해진 순회 순서에 따른 그 노드의 선행 노드를 가리킴
- 이진 트리의 null 포인터 개수 : 2n-(n-1) = n+1개
내용
- 스레드 트리의 정의
- 스레드 트리
- 이진 트리의 노드 순회: 전위 순회, 중위 순회, 후위 순회
- 이진 트리의 노드를 순회할 때, 방문하지 않고 지나쳐 온 노드들은 스택에 저장하여 관리해야하는 번거로움이 발생함
- 스레드 트리: ‘스레드;라는 포인터를 추가하여 트리 순회를 편리하게한 것
- 스레드 트리의 구현
-
포인터 필드의 추가: 스레드를 저장하는 포인터를 추가하는 것
- 왼쪽 스레드 포인터, 왼쪽 자식 포인터 데이터, 오른쪽 자신 포인터 오른쪽 스레드 포인터 필드로 노드 구조를 정의함
-
오른쪽 스레드: 정해진 순회 순서에 따른 그 노드의 추속 노드를 가리키고
-
왼쪽 스레드: 그 노드의 선행 노드를 가리킴
-
포인터 필드의 추가
struct TNode {
int info;
TNode left;
TNode right;
TNode right_thread;
TNode left_thread;
}
-
추가된 포인터 필드를 이용한 중위 순회 연산
void inorder(struct TNode *firstin) {
struct TNode *p;
p = firstin;
while(p != NULL) {
printf("%d", p->info);
p = p->right_thread;
}
}
-
추가된 포인터 필드를 이용한 중위 순회 연산과정
- 순회할 트리의 노드를 가리키는 포인터 firstin을 매개변수로 하는 함수의 이름을 inorder()로 합니다.
- 노드를 가리킬 수 있는 (TNode) 타입의 포인터 p를 생성하고 루트 노드를 가리키도록 합니다.
- 포인터 p가 가리키는 데이터(info)를 출력하고 p를 p의 오른쪽 스레드 값으로 바꾸어 (p → right_thread) 중위 순회에 따른 다음 노드를 가리키도록 수정 합니다.
- 이 과정을 p가 null이 될 때까지 반복합니다.
- 스택을 운영하지 않고도 쉽게 트리에 속한 모든 노드를 순회 할 수 있음
- 하지만 스레드를 위해 추가 기억장소를 사용한다는 부담이 생김
- 스레드의 구현 방법(2)
- 잎 노드의 빈 포인터 필드의 활용
- 이진 트리의 포인터 갯수 (노드이 개수를 n개라 가정함): 왼쪽 서브트리를 가리키는 포인터 n개 + 오른쪽 서브트리를 가리키는 n개 = 2n개의 포인터
- 노드의 빈 포인터 필드의 활용
- 루트 노드를 제외한 각 노드 개수는 모두 진입 차수는 1이 되므로,
- 루트 노드를 제외한 전체 노드 죽, 누군가로부터 가리켜져 야 할 노드의 개수: n-1
- null이 아닌 포인터 개수 : n-1
- 2n - (n-1) = n+1개의 null 포인터가 노드에 존재함
- 2n - (n-1) = n+1개의 null 포인터를 스레드로 활요함
- 이진 트리의 중위 순회: 어떤 노드 x에 대해 오른쪽 포인터가 null이면 이 포인터를 x 노드의 다음으로 순회되는 노드를 가리키도록 하고, 왼쪽 포인터가 null이면 x 노드의 바로 직전에 순회된 노드를 가리키게 함
- 각 노드에 대해 포인터가 스레드로 사용 중인지 아니면 서브트리에 대한 포인터인지 구분하기 위해 태그 필드가 필요함 (삽입/삭제 연산에서 반드시 필요함)
- 전위 순회 : 각 노드의 왼쪽 포인터 필드를 스레드로 사용하는 제한을 가정함
- 어떤 노드의 왼쪽 포인터가 실제 왼쪽 자식을 가리키면 그대로 두고,
- null이면 전위 순회로 순회할 때 다음으로 순회되는 노드를 가리키도록 지정함
- 스레드 트리 삽입 연산
- 스레드 트리 삭제 연산
- 스레드 트리의 내부 노드 삭제: 삭제된 노드의 자식 노드를 처리 방법이 필요함
- 노드의 자식 노드를 모두 삭제하는 방법
- 삭제하려는 노드 x의 왼쪽 서브 트리나 오른쪽 서브 트리의 루트를 x가 있던 우치로 옮기는 방법
- 잎 노드가 아닌 노드를 삭제하지 못하게 하는 것
3. 힢
주요용어
- 힢: 부모노드와 자식노드 사이의 대소관계가 정의되어 구성되는 완전 이진트리로 우선순위 큐와 같은 결과를 제공함
- 최대힢: 루트가 가장 큰 값을 갖고 부모는 자식보다 큰 값을 가지면 됨
- 최소힢: 루트가 가장 작은 값을 갖고 부모는 자식보다 작은 값을 가지면 됨
내용
- 우선순위 큐
- 우선순위 큐의 작동 방식:
- 첫째, 삭제 명령이 실행되면 저장된 데이터 중에서 가장 작은 값(가장 큰 값)이 삭제된다.
- 둘때, 나머지 데이터들은 어떤 순서로 저장되든 문제가 되지 않는다.
- 힢(Heap)
- 힢의 정의
- 피라미드 모양으로 쌓아 올린 더미
- 무엇인가 쌓아놓은 더미이고 항상 가장 위에 있는 것을 우선 꺼내는 구조
- 부모-자식 노드사이에서(부분적으로) 정렬된 완전 이진 트리로 부모노드는 자식노드보다 우선순위가 높음
- 힢의 종류
- 최소 힢: 루트가 전체 노드중에서 최소값인 힙
- 트리의 모든 노드가 자식 노드보다 작은 값을 가짐
- 트리의 레벨에 따라 데이터가 순서를 갖지는 않음
- 탐색 트리처럼 왼쪽 노드와 오른쪽 노드 사이에 크기 제한도 없음
- 루트가 가장 작은 값을 갖고 부모는 자식보다 작은 값을 가짐
- 최대 힢: 루트가 전체 노드중에서 최소값인
- 트리의 모든 노드가 자식 노드보다 큰 값을 가짐
- 트리의 레벨에 따라 데이터가 순서를 갖지는 않음
- 탐색 트리처럼 왼쪽 노드와 오른쪽 노드 사이에 크기 제한도 없음
- 루트가 가장 큰 값을 갖고 부모는 자신보다 큰 값을 가지면 됨
- 힢의 구현
- 힢 구현을 위한 자료구조
- 배열을 이용한 힙의 구현: 완전 이진트리이기 때문에 배열로 구현해도 기억장소 낭비가 없음
- 연결 리스트보다 실행 속도 면에서 효율적임
- 기억장소 측면에서도 장점을 가짐
힢의 노드 삽입
void insert_max_heap(int item, int *n) {
int i;
if (HEAP_FULL(*n)) {
fprintf(stderr, "The heap is full. \n");
exit(1);
}
i = ++(*n);
while((i != 1 && (item > heap[i/2])) {
heap[i] = heap[i/2];
i /= 2;
}
heap[i] = item;
}
힢의 노드 삭제
int delete_max_heap (int *n) {
int parent, child;
int item, temp;
if (HEAP_EMPTY (*n)) {
fprintf(stderr, "The heap is empty\n"); exite(1);
}
item = heap[1];
temp = heap[(*n)--];
parent = 1; child = 2;
while (child <= *n) {
if ((child < *n) && (heap[child] < heap[child+1]))
child++;
if (temp >= heap[child]) brak;
heap[parent] = heap[child];
parent = child;
child *= 2;
}
heap[parent] = temp;
return item;
}