[ALGORITHM] 트리

트리

자료구조 트리는 그래프의 일종으로 최소 연결 트리라고도 불린다.

트리의 구조 및 용어

노드 (Node)

• 트리를 구성하고 있는 기본 요소
• 노드에는 키 또는 값과 하위 노드에 대한 포인터를 가지고 있음.
• A, B, C, D, E, F, G, H, I, J

간선 (Edge)

• 노드와 노드 간의 연결선

루트 노드 (Root Node)

• 트리 구조에서 부모가 없는 최상위 노드
• root node : A

부모 노드 (Parent Node)

• 자식 노드를 가진 노드
• H, I에 부모 노드는 D

자식 노드 (Child node)

• 부모 노드의 하위 노드
• 노드 D의 자식 노드는 H, I

형제 노드 (Sibling node)

• 같은 부모를 가지는 노드
• H, I는 같은 부모를 가지는 형제 노드

외부 노드(external node, outer node), 단말 노드 (terminal node), 리프 노드(leaf node)

• 자식 노드가 없는 노드
• H, I, J, F, G

내부 노드 (internal node, inner node), 비 단말 노드 (non-terminal node), 가지 노드 (branch node)

• 자식 노드 하나 이상 가진 노드
• A, B, C, D, E

노드의 크기 (size)

• 자신을 포함한 모든 자손 노드의 개수
• B의 크기 : 6

노드의 깊이(depth)

• D의 깊이 : 2
• H의 깊이 : 3

노드의 레벨 (level)

• 루트 노드에서 1 level로 시작하여 늘어남

노드의 차수 (degree)

• 각 노드가 가지는 가지의 수
• A의 차수 : 2
• E의 차수 : 1

트리의 차수 (degree of tree)

• 트리의 최대 차수

트리의 높이 (height)

• 루트 노드에서 가장 깊숙히 있는 노드의 깊이

이진 트리

각 노드는 최대 2개의 자식만을 가진다.

서브트리는 공집합일 수 있으며 반드시 왼쪽 서브트리와 오른쪽 서브트리가 구분되어 있다.

이진 트리 종류

1. 포화 이진 트리
   • 트리의 각 레벨에 노드가 완전히 채워져있는 이진트리를 뜻한다.
   • 모든 leaf 노드는 같은 level에 있어야하며, 마지막 level의 노드의 개수는 최대가 되어야 한다.

2. 

3. 완전 이진 트리
   • 마지막 level을 제외한 모든 level의 노드가 완전히 채워져 있으며, 마지막 level의 노드들은 왼쪽부터 순차적으로 채워져 있는 이진트리를 뜻한다.

4. 

이진 트리 성질

1. 이진 트리에서 edge 개수
   • 이진 트리에서 루트 노드를 제외하고 모든 노드는 하나의 부모 노드를 가지고 있다.
   • n개의 노드를 갖는 이진트리에서 간선의 수는 n - 1개 이다.
2. 노드의 개수, 높이
   • 높이가 h인 완전 이진 트리에서 노드의 개수는 2^h -1 개이며 완전 이진 트리의 최대 높이는 log_2(N+1) - 1으로 완전 이진 트리 탐색의 시간 복잡도는 O(log(N))이 된다.