[알고리즘] 트리 (Tree)

트리의 개념

트리는 그래프의 한 종류로서 정점(node)들과 정점들을 연결하는 간선(edge) 들로 구성된다. 

사이클이 없는 하나의 연결 그래프이자 DAG(방향성이 있는 비순환 그래프) 의 한 종류이다.

트리는 하나의 루트 노드를 갖으며 부모 노드 밑에 여러 자식 노드가 연결되고, 자식 노드 각각에 다시 자식 노드가 연결되는 재귀적 형태의 자료구조이다. 

 

트리 관련 용어

 

• 루트 노드(root node) : 부모가 없는 노드. 트리는 하나의 루트 노드만을 가진다.

• 단말 노드(leaf node) : 자식이 없는 노드이다.

• 내부(internal) 노드 : 리프 노드가 아닌 노드.

• 링크(link) : 노드를 연결하는 선 (edge, branch 라고도 부름).

• 형제(sibling) : 같은 부모를 가지는 노드.

• 노드의 크기(size) : 자신을 포함한 모든 자손 노드의 개수.

• 노드의 깊이(depth) : 루트에서 어떤 노드에 도달하기 위해 거쳐야 하는 간선의 수

• 노드의 레벨(level) : 트리의 특정 깊이를 가지는 노드의 집합

• 노드의 차수(degree) : 부(하위) 트리 갯수/간선수 (degree) = 각 노드가 지닌 가지의 수

• 트리의 차수(degree of tree) : 트리의 최대 차수

• 트리의 높이(height) : 루트 노드에서 가장 깊숙히 있는 노드의 깊이

 

트리의 종류

 

1. 이진 트리 (Binary tree)

  : 부모 노드가 자식 노드를 최대 2개씩만 갖고 있는 트리

 

2. 이진 검색 트리 (Binary Search Tree)

 : left child 와 그 이하 노드들의 데이터가 현재 노드의 데이터보다 작아야 하고

 : right child 와 그 이하 노드들의 데이터가 현재 노드의 데이터보다 커야 한다.

 

3. 균형 트리 (Balanced Tree)

 : O(logN) 의 시간에 insert와 find를 할 수 있을 정도로 left노드와 right노드의 갯수가 균형적으로 이루어져 있는 트리

 

4. 완전 이진 트리 (Complete Binary Tree)

 : 트리의 모든 높이에서 노드가 꽉 차 있는 이진 트리(마지막 레벨을 제외하고 모든 레벨이 완전히 채워져 있음)

 : 마지막 레벨은 완전히 채워져 있지 않아도 되지만 노드가 왼쪽에서 오른쪽 순으로 채워져야 한다.

 

5. 정 이진트리 (Full Binary Tree)

 : 모든 노드가 0개 또는 2개의 자식 노드를 갖는 트리

 

6. 포화 이진 트리 (Perfect Binary Tree)

 : 정 이진트리면서 완전 이진트리인 경우

 : 모든 말단 노드는 같은 높이에 있어야 하며, 마지막 단계에서는 노드의 개수가 최대가 되어야 한다.

 : 모든 내부 노드가 두 개의 자식 노드를 가진다.

 : 노드의 개수가 2^(k-1) 개여야 한다. (k: 트리 높이)