자료구조 트리 (tree)

트리는 그래프의 일종으로서 순환 관계 (= cycle)가 존재하지 않으며, 노드 간의 부모 자식 관계가 추가된 자료구조이다.

 

나무를 뒤집어 놓은 것과 비슷하게 생겼다 하여 이름 붙여진 트리는, 알고리즘 문제를 풀 때 단골로 등장하는 자료구조이다.

다음은 이진트리를 이용해 정렬된 숫자들을 탐색하는 이진 탐색 트리의 예시이다.

 

이진 탐색 트리 (binary search tree)의 예시

 

 

위에서 언급했듯 트리는 그래프의 일종이므로 그래프의 특성을 공유한다.

거기에 추가되는 노드 간 부모 - 자식 관계가 더해지는 것이 트리의 특징이다.

 

 

 

 

 

 

 

트리는 그래프 이상의 다양한 종류로 분류된다. 종류를 분류할 기준을 크게 3가지로 나누어 적어보았다.

1. 자식의 개수별 분류
   
   1. 트리 : 자식의 개수에 대한 제한이 없는 트리
   2. 이진트리 : 모든 노드에 대하여 자식의 개수가 2개 이하인 트리
   3. N진 트리 : 자주 사용되는 표현은 아니다. 하지만 만약 자식의 개수를 최대 3개로 제한한다면 3진 트리로 표현한다.
2. 트리의 모양별 분류
   1. 포화 트리 : 트리의 모든 층(= level)에 노드가 가득 찬 상태
   2. 완전 트리 : 트리의 모든 층에 노드가 가득 차지 않았더라도, 마지막 층 전까지는 가득 차 있으며, 마지막 층의 노드가 좌측부터 채워져 있는 상태
   3. 편향 트리 : 한쪽 방향으로 치우친 상태
   4. 균형 트리 : 임의의 노드에서 좌, 우측 자식의 서브 트리의 높이( = height = 서브 트리의 층 수 + 1) 차이가 1 이하인 상태
   5. 등등...
3. 기능별 분류
   1. 탐색 트리 : 노드들이 임의의 기준으로 정렬되어 있어 노드를 탐색할 때 log 시간을 보장하는 트리 (예시로 보인 이진 탐색 트리 등)
   2. 자동 균형 트리 : 스스로 균형 트리가 되도록 벨런싱 하는 트리 (AVL 트리, 레드 블랙 트리 등)
   3. 구간 대표 트리 : 임의의 노드가 특정한 구간을 대표하게 되는 트리 (세그먼트 트리, 스패닝 트리 등)
   4. 등등...

 

 

 

 

트리의 기능별 분류는 종류도 다양하고, 각각의 내용이 많기 때문에 하나하나 독립적으로 정리할 예정이다.

 

 

 

트리는 그래프와 동일하게 노드와 간선으로 이루어진다.

하지만 몇 가지 특별한 노드, 특별한 차이를 부르는 용어가 있다.

• 뿌리 노드 (root node) : 트리의 가장 첫 노드, 부모가 없는 노드이다.
• 잎 노드 (leaf node) : 트리의 가장 끝 노드, 자식이 없는 노드이다.
• 층 (level) : 트리의 층이다.
• 깊이 (depth) : 해당 노드에서부터 루트까지의 층 차이를 말한다. 아래의 예시에서 20번 노드의 깊이는 3이다. 
• 높이 (height) : 해당 노드에서부터 리프 노드까지의 층 차이를 말한다. 아래 예시에서 3번 노드의 높이는 1이다. 그러므로 리프 노드의 높이는 0이 된다.