[자료구조] 트리

정의

트리는 노드(node)라는 항목들이 계층적으로 배치되어 구성된다. 계층의 가장 상위 노드를 루트(root)라고 한다.

루트의 바로 아래 노드들은 루트의 자식들(children)이고, 보통 이 노드들도 자식이 있다.

루트를 제외한 모든 노드들은 하나의 부모(parent)를 갖는데 부보는 바로 상위 노드이다.

부모가 가질 수 있는 자식 노드의 수는 트리의 형태에 따라 다른다.

트리에서 이 숫자를 분기계수(branching factor)라고 한다.

응용

1. 이진트리

자식을 두 개까지 가질 수 있는 노드들로 이루어진 트리이다.

2. 트리 평형

주어진 수의 노드들에 대해 트리를 가능한 짧게 유지하는 데 사용되는 방법이다.

트리의 높이가 전체 성능에 영향을 미치기 때문에 필요한 부분이다.

3. 사용자 인터페이스

 계층적 파일 시스템의 디렉토리

 

4. 데이터베이스 시스템

빈번한 삽입과 삭제를 수행하면서 효율적인 순차, 임의의 접근을 모두 필요로하는 시스템이다.

일반적으로 큰 분기 계수를 갖는 평형 탐색 트리로 묘사되는 트리인 B-트리가 이 경우에 특히 좋다.

전형적으로 데이터베이스의 레코드에 접근할 떄 디스크 입출력이 최소화되도록 B-트리의 분기 계수는 최적화된다.

5. 식처리

 컴파일러와 휴대용 계산기에서 자주 수행되는 작업이다.

6. 인공지능

 결정트리(decision tree)를 사용해서 많은 인공지능 문제들을 푼다.

 결정트리는 상태를 표현하는 노드들로 이루어진다. 각 노드는 계속 진행하기 위해서 결정을 해야 하는 지점이다.

 각 분기는 일련의 결정들에서 나온 하나의 결론을 의미한다.

7. 이벤트 스케쥴러

 실시간 이벤트들의 순서를 관리하고 시작하게 하는 애플리케이션이다.

 흔히 실시간 시스템은 이벤트가 시작될 때 그 이벤트와 관련된 최근의 정보를 조회하는 것을 필요로 한다.???

관련

1. 이진트리

 하위 노드를 2개까지 가질 수 잇는 노드들의 계층적 배치이다.

 노드의 하위 노드를 자식(child)이라고 한다.

 노드의 상위 노드를 부모(parent)라고 한다.

 트리와 관련된 성능은 주로 노드들이 존재한는 단계의 수인 트리의 높이(height)에 의해 논의된다.

 트리의 각 노드는 세 부분으로 구성되는데 자료 멤버와 왼쪽, 오른쪽 포인터라고 불리는 두 개의 포인터이다.(각 포인터가 자식노드를 가리킨다.)

 노드가 왼쪽 또는 오른쪽에 자식을 갖지 않으면 해당 포인터에 분기의 마지막을 표시하는 NULL을 넣는다.

 잎 노드(leaf node)는 트리의 가장자리의 노드로서 자식을 갖지 않는다.

순회방법

1. 전위 순위(preorder)

 이진 트리를  전위 방식으로 순회하려면 먼저 루트 노드를 방문하고 루트 노드의 왼쪽 부분 트리를 전위 방식으로 순회한 다음에 루트 노드의 오른쪽 트리를 전위 방식으로 순회한다.

2. 중위 순위(inorder)

 먼저 루트 노드의 왼쪽 부분 트리를 중위 방식으로 순회하고 루트 노드를 방문한 다음에 루트 노드의 오른쪽 부분 트리를 중위방식으로 순회한다.

3. 후위 순위(Postorder)

 루트 노드의 왼쪽 부분 트리를 후위 방식으로 순회하고 루트 노드의 오른쪽 부분 트리를 후위 방식으로 순회한 다음에 루트 노드를 방문한다.

이진트리 분석

// 이진트리 노드의 구조체

typedef struct BiTreeNode_ {

void        *data;

struct BiTreeNode_ *left;

struct BiTreeNode_ *right;

} BiTreeNode;

// 이진트리 구조체

typedef struct BiTree_ {

int        size;

int        (*compare)(const void *key1, const void *key2);

void      (*destroy)(void *data);

BiTreeNode    *root;

} BiTree;

// node의 왼쪽에 data를 집어 넣고자 할 때.

int bitree_ins_left(BiTree *tree, BiTreeNode *node, const void *data){

// node의 오른쪽에 data를 집어 넣고자 할 때.

int bitree_ins_right(BiTree *tree, BiTreeNode *node, const void *data){

BiTreeNode    *new_node,

  **position;

// 노드를 삽입할 위치 결정

if (node == NULL) {

// 빈 트리에서만 루트에 삽입 허용

if (bitree_size(tree) > 0 )

return -1;

position = &tree->root;

}

else {

// 보통은 분기의 끝에만 삽입을 허용.

if (bitree_left(node) != NULL)

return -1;

position = &node->left;

}

// 노드에 메모리 할당

if ((new_node = (BiTreeNode *)malloc(sizeof(BiTreeNode))) == NULL)

return -1;

// 트리에 노드 삽입

new_node->data = (void*) data;

new_node->left = NULL;

new_node->right = NULL;

*position = new_node;

// 삽입된 노드를 반영하기 위해 트리의 크기 조정.

tree->size++;

return 0;

}

// node 왼쪽에 있는 sub tree를 모두 삭제

void bitree_rem_left(BiTree *tree, BiTreeNode *node) {

BiTreeNode        **position;

// 빈 트리에서 삭제 금지.

if(bitree_size(tree) == 0)

return;

// 삭제할 노드의 위치 결정

if (node == NULL)

position = &tree->root;

else

position = &node->left;

// 노드 삭제

if (*position != NULL) {

bitree_rem_left(tree, *position);

bitree_rem_right(tree, *position);

if (tree->destroy != NULL) {

// 동적으로 할당된 자료를 해제하기 위해 사용자 정의 함수 호출

tree->destroy((*position)->data);

}

free(*position);

*position = NULL;

// 삭제된 노드를 반영하기 위해 트리의 크기 조정.

tree->size--;

}

return ;

}

int bitree_merge(BiTree *merge, BiTree *left, BiTree *right, const void *data) {

// 합병 트리 초기화

bitree_init(merge, left->destroy);

// 합병 트리의 루트에 자료 삽입

if (bitree_ins_left(merge, NULL, data) != 0) {

bitree_destroy(merge);

return -1;

}

// 두 이진 트리를 하나의 이진 트리로 합병

bitree_root(merge)->left = bitree_root(left);

bitree_root(merge)->right = bitree_root(right);

// 새로운 이진 트리의 크기 조정

merge->size = merge->size + bitree_size(left) + bitree_size(right);

// 원래의 트리들이 합병 트리의 노드에 접근하는 것을 금지

left->root = NULL;

left->size = 0;

right->root = NULL;

right->size = 0;

return 0;

}