트리(Tree)

트리란?

• 계층적(Hierarchical)인 구조를 나타내는 비선형 자료구조
• 나무를 뒤집어놓은 모양과 닮았다고 해서 붙여진 이름
• 부모-자식 관계의 노드들로  이루어진다.
  • ex) Decision Tree(의사 결정 트리) in AI
• 리스트, 스택, 큐 등은 선형 구조

트리 용어

• 노드(node): 트리의 구성요소
• 루트(root): 부모가 없는 노드(A)
• 서브트리(subtree): 하나의 노드와 그 노드들의 자손들로 이루어진 트리
• 단말노드(terminal node): 자식이 없는 노드
• 비단말노드(leaf node): 적어도 하나의 자식을 가지는 노드
• 레벨(level): 트리의 각층의 번호
• 높이(height): 트리의 최대 레벨
• 차수(degree): 노드가 가지고 있는 자식 노드의 개수

1. A는 루트 노드이다.
2. B는 D와 E의 부모노드이다. 
3. C는 B의 형제 노드이다. 
4. D와 E는 B의 자식노드이다. 
5. B의 차수는 2이다. 
6. 위의 트리의 높이는 4이다. 

이진 트리(Binary Tree)

• 모든 노드가 2개의 (공집합일 수도 있는) 서브 트리를 가지고 있는 트리
• 최대 2개까지의 자식 노드가 존재
• 모든 노드의 차수가 2 이하
• 높이가 h인 이진트리의 경우 최소 h개의 노드를 가지며 최대 2^(h) - 1개의 노드를 가진다.

이진트리의 분류

• 포화 이진 트리(full binary tree)
  • 트리의 각 레벨에 노드가 꽉 차있는 이진트리
• 완전 이진 트리(complete binary tree)
  • 레벨 1부터 k-1까지는 노드가 모두 채워져 있고 마지막 레벨 k에서는 왼쪽부터 오른쪽으로 노드가 순서대로 채워져 있는 이진 트리, 포화 이진 트리와 노드 번호가 일치
• 기타 이진 트리

이진트리의 표현

• 배열표현법
  • 모든 이진 트리를 포화 이진 트리라고 가정하고 각  노드에 번호를 붙여서 그 번호를 배열의 인덱스로 삼아 노드의 데이터를 배열에 저장하는 방법
    • 노드 i의 부모 노드 인텍스 = i/2
    •  노드 i의 왼쪽 자식 노드 인텍스 = 2i
    • 노드 i의 오른쪽 자식 노드 인텍스 = 2i+1
• 링크표현법
  • 포인터를 이용하여 부모노드가 자식노드를 가리키게 하는 방법
    • 노드는 구조체로 표현
    • 링크는 포인터로 표현

이진트리의 순회

순회(traversal): 트리의 노드들을 체계적으로 방문하는 것

• 전위순회(preorder traversal)
  • 자손노드보다 루트노드를 먼저 방문한다.
  • 루트노드 -> 왼쪽 서브트리 -> 오른쪽 서브트리

void preorder(TreeNode* root) {
	if (root) {
		printf("%d", root->data);
		preorder(root->left);
		preorder(root->right);
	}
}

• 중위순회(inorder traversal)
  • 왼쪽 자손, 루트, 오른쪽 자손 순으로 방문한다.
  • 왼쪽 서브트리 -> 루트노드 -> 오른쪽 서브트리

void inorder(TreeNode* root) {
	if (root) {
		inorder(root->left);
		printf("%d", root->data);
		inorder(root->right);
	}
}

• 후위순회(postorder traversal)
  • 루트노드보다 자손을 먼저 방문한다.
  • 왼쪽 서브트리 -> 오른쪽 서브트리 -> 루트노드

void postorder(TreeNode* root) {
	if (root) {
		postorder(root->left);
		postorder(root->right);
		printf("%d", root->data);
	}
}

이진탐색트리

• 탐색작업을 효율적으로 하기 위한 자료구조
• key(왼쪽서브트리) ≤ key(루트노드) ≤ key(오른쪽서브트리)
• 이진탐색를 중위순회하면 오름차순으로 정렬된 값을 얻을 수 있다.

탐색 구현

//순환적인 탐색 함수
TreeNode *search(TreeNode *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);
}

// 반복적인 탐색 함수
TreeNode *search(TreeNode *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; // 탐색에 실패했을 경우 NULL 반환
}

삽입 연산

• 이진 탐색 트리에 원소를 삽입하기 위해서는 먼저 탐색을 수행하는 것이 필요
• 탐색에 실패한 위치가 바로 새로운 노드를 삽입하는 위치

TreeNode* new_node(int item) {
	TreeNode* temp = (TreeNode*)malloc(sizeof(TreeNode));
	temp->key = item;
	temp->left = temp->right = NULL;
	return temp;
}

TreeNode* insert_node(TreeNode *node, int key) {
	// 트리가 공백이면 새로운 노드를 반환한다. 
	if (node == NULL) return new_node(key);

	// 그렇지 않으면 순환적으로 트리를 내려간다. 
	if (key < node->key) node->left = insert_node(node->left, key);
	else if (key > node->key) node->right = insert_node(node->right, key);

	// 변경된 루트 포인터를 반환한다. 
	return node;
}

삭제 연산

1. 삭제하려는 노드가 단말 노드일 경우: 단말노드의 부모노드를 찾아서 연결을 끊으면 된다.
2. 삭제하려는 노드가 하나의 서브트리만 갖고 있는 경우: 삭제되는 노드가 왼쪽이나 오른쪽 서브 트리중 하나만 갖고 있을 때, 그 노드는 삭제하고 서브 트리는 부모 노드에 붙여준다.
3. 삭제하려는 노드가 두개의 서브트리를 갖고 있는 경우: 삭제노드와 가장 비숫한 값을 가진 노드(왼쪽 서브트리에서 가장 큰 값 또는 오른쪽 서브트리에서 가장 작은 값)를 삭제노드 위치로 가져온다.

#include <math.h>
#define MIN(a, b) a < b ? a : b
TreeNode* min_value_node(TreeNode* node) {
	TreeNode* current = node;
	while (current->left != NULL) {
		current = current->left;
	}
	return current;
}
TreeNode* max_value_node(TreeNode* node) {
	TreeNode* current = node;
	while (current->right != NULL) {
		current = current->right;
	}
	return current;
}
TreeNode* delete_node(TreeNode* node, int data) {
	if (node == NULL) return node;
	if (data < node->data) {
		node->left = delete_node(node->left, data);
	}
	else if (data > node->data) {
		node->right = delete_node(node->right, data);
	}
	else {
		// 첫 번째나 두 번째 경우
		if (node->left == NULL) {
			TreeNode* tmp = node->right;
			free(node);
			return tmp;
		}
		else if (node->right == NULL) {
			TreeNode* tmp = node->left;
			free(node);
			return tmp;
		}
		// 세 번째 경우
		else {
			TreeNode* tmp_right = min_value_node(node->right);
			TreeNode* tmp_left = max_value_node(node->left);
			TreeNode* close = abs(data - tmp_right->data) < abs(data - tmp_left->data) ? tmp_right : tmp_left;
			node->data = close->data;
			close == tmp_right ? (node->right = delete_node(node->right, close->data)) : (node->left = delete_node(node->left, close->data));
		}
	}
	return node;
}

이진탐색트리의 성능분석

• 탐색, 삽입, 삭제 연산의 시간 복잡도는 트리의 높이를 h라고 했을때 h에 비례한다.

• 최선의 경우
  • 이진 트리가 균형적으로 생성되어 있는 경우
  • h=⌈log2(n)⌉
• 최악의 경우
  • 한쪽으로 치우친 경사이진트리의 경우
  • h=n
  • 순차탐색과 시간복잡도가 같다.