트리 (Tree)

트리(Tree)란 무엇일까?

트리(Tree)는 데이터를 계층적으로 표현하는 자료구조다. 

 

왜 트리를 사용할까?

트리는 주로 검색 연산을 많이 해야 할 경우에 사용된다.

트리가 검색에 특화된 이유는 계층 구조를 사용하기 때문이다. 

 

트리의 조건

1. 하나의 루트 노드를 가진다.

2. 사이클이 존재하지 않는다.

3. 모든 노드는 하나의 부모 노드를 가진다.

4. 노드가 N개인 트리는 항상 N-1개의 간선을 가진다.

---

트리에서 사용되는 용어

앞으로의 편리한 설명을 위해 알아둘 용어이며, 시간을 들여 따로 외울 필요는 없다.

용어	설명
노드 (Node)	데이터를 저장하는 공간
간선 (Edge)	노드 간의 연결
최상위 노드 (Root node)	부모가 없는 트리의 최상위 노드
내부 노드 (Interior node)	최상위 노드도 말단 노드도 아닌 노드
말단 노드 (Leaf node)	자식이 없는 트리의 최하위 노드
부모 노드 (Parent node)	현재 노드의 바로 위 노드
자식 노드 (Child node)	현재 노드의 바로 아래 노드
형제 노드 (Sibling node)	현재 노드와 같은 계층의 같은 부모를 공유하는 노드
삼촌 노드 (Uncle node)	현재 노드와 같은 계층이지만 다른 부모인 노드
조상 (Ancestor)	현재 노드의 부모 노드부터 루트 노드까지 연결된 노드들의 집합
자손 (Descendant, Sub tree)	현재 노드와 연결된 모든 하위 노드
높이 (Depth, Level, Height)	트리의 계층
차수 (Degree)	현재 노드의 자식 노드 개수
트리의 차수 (Degree of tree)	트리의 높이

---

트리의 구현

현재 설명하는 기본 트리는 추상화된 개념이다. 트리는 보통 응용하여 사용하기 때문에 기본 트리의 구현은 다루지 않는다.

만약 기본 트리를 구현한다면 어떻게 구현될까? 이차원 배열을 사용하는 것과 다름없을 것이다.

 

시간 복잡도

기본 트리의 구현은 배열과 같기 때문에 다음의 시간복잡도가 나올 것이다.

연산	평균	최악
삽입	O(n)	O(n)
삭제	O(n)	O(n)
검색	O(n)	O(n)

---

트리의 순회

전위 순회 (preorder traversal)

본인 노드 ->  왼쪽 자식 노드 -> 오른쪽 자식 노드 순으로 순회하는 것을 말한다.

 

예제 코드 :

void preorder(Node *root)
{
	if(root == NULL) return;
	printf("%d", root->key);
	preorder(root->left);
	preorder(root->right);
}

 

중위 순회 (inorder traversal)

왼쪽 자식 노드 -> 본인 노드 -> 오른쪽 자식 노드 순으로 순회하는 것을 말한다.

 

예제 코드 :

void inorder(Node *root)
{
	if(root == NULL) return;
	inorder(root->left);
	printf("%d", root->key);
	inorder(root->right);
}

 

후위 순회 (postorder traversal)

왼쪽 자식 노드 -> 오른쪽 자식 노드 -> 본인 노드 순으로 순회하는 것을 말한다.

 

예제 코드 :

void postorder(Node *root)
{
	if(root == NULL) return;
	postorder(root->left);
	postorder(root->right);
	printf("%d", root->key);
}