Data structure 14 - Tree(2)
앞서 살펴본 이진트리는, 자식을 가지지 않는 노드(leaf 노드)들의 pointer 공간이 낭비된다. (자식을 가리키지 않아 NULL 값이므로) 이 낭비되는 공간을 두 가지 정리로 유추할 수 있다.
1. Full binary tree theorem : 비어 있지 않은 포화이진트리(모든 level에 노드가 가득 차 있는 트리)의 leaf node(terminal node) 수는 내부 노드(non-terminal node)수보다 하나 더 많다.
증명 : 이진 트리의 각 레벨 노드 개수는 2의 제곱으로 늘어난다. 따라서 포화이진트리에서 level n 이전까지의 노드를 모두 더하면 2^n-1이고, level n의 노드 수는 2^n 이므로 항상 성립한다.
2. Full binary tree corollary : 비어 있지 않는 트리의 널 포인터 수는 트리의 노드 수보다 하나 더 많다.
이렇게 낭비되는 공간은 space overhead=(non-data space)/(total space)로 나타낼 수 있다. pointer를 위한 공간을 p, data를 위한 공간을 d 라 할 때, 각 노드는 자식 포인터 2개, heap에 저장된 data를 가리키는 포인터 1개, data를 위한 공간 d를 가지므로 총 공간은 (3p+d)가 된다. 따라서 space overhead= 3p/(3p+d)로 나타내고, p=d라면 3/4가 된다.
따라서, 이진트리 정리에 의해 전체 트리의 포인터 중 절반 이상은 null 값을 가지게 된다. 이는 공간의 낭비이므로 해당 포인터로 이전이나 이후 노드를 가리키게 하는 것이 탐색 속도를 증가시킬 수 있다. 이것이 스레드 이진트리이다.
#include<stdio.h> // 스레드 이진트리
#include<stdlib.h>
#include<stdbool.h>//bool쓰기 위한 헤더.
//낭비되는 단말노드의 NULL 포인터 공간을 활용해 다음 노드를 가리키는 트리. 재귀호출을 사용하지 않아도 순환호출이 가능하여 낭비되는 공간도 줄이고, 연산시간도 단축되는 효과가 있다.
typedef struct threadNode {
int data;
struct threadNode* left, * right;
bool is_leftThread, is_rightThread; // 일반 부모노드라면 자식 노드의 위치가 포인터 left,right에 있지만 단말 노드의 경우에는 다음 노드를 가리키는 포인터가 left,right에 들어가있다.
}threadNode; // 이를 구분하기 위해 스레드 노드인지 아닌지를 표시하는 bool 사용. (왜냐하면 이전에는 단말노드일 때 다음 가리키는 자식이 없으므로 순회가 불가능했기 때문).
threadNode* find_successor(threadNode* p) { // 스레드 이진트리 순회하기 위해 주어진 노드 p가 갈 다음 노드를 찾는 함수, inorder이므로 자기자신 다음은 오른쪽 서브트리.
threadNode* q = p->right; // 따라서 오른쪽 서브트리 확인
if (q == NULL || p->is_rightThread == true) return q; // q가 NULL이거나 rightthread가 트루라면 단말 노드 혹은 다음으로 갈 노드를 가리키는 단말노드이므로 q를 반환.
while (q->left != NULL) q = p->left; // 아니라면 inorder 순서대로 왼쪽 서브트리가 남아있으면 먼저가야하므로 왼쪽으로 먼저 이동.
return q;
}
void thread_inorder(threadNode* t) { //inorder 순서로 트리 순회
threadNode* q = t;
while (q->left) q = q->left; //맨왼쪽 아래 먼저 찾기
do {
printf("%d", q->data);
q = find_successor(q); // 위에서 정의한 다음 노드로 갈 노드 찾는 함수 사용해서 재귀함수 안쓰고 다음 경로 이동.
} while (q); //스레드 트리를 사용하면 맨 오른쪽아래 마지막 단말노드를 제외하고는 항상 가리키는 노드가 있으므로 q가 NULL 이 아님(마찬가지로 마지막 노드일 경우에는 return q를 하도록 위에서 정의)
}
댓글
댓글 쓰기