[Data Structure] 트리 개념

트리

- 계층적 구조(hierarchical structure)을 가진 자료구조

- 부모-자식 관계의 노드들로 구성

 

 

트리의 용어

- 노드(node) : 트리의 구성요소 → A, B, C, D, E, F, G, H, I, J

- 루트(root) : 각 Tree의 최상위 노드 → A

- 서브 트리(subtree) : 최상위 노드를 제외한 나머지 노드 / 하나의 노드 + 그 노드들의 자식 → {B, E, F, G}, {C, H}, {D, I, J}

- 간선(edge) : 노드들 사이의 선

- 단말 노드(terminal node) : 자식이 없는 노드 → E, F, G, H, I, J

- 비단말 노드(nonterminal node) : 자식이 있는 노드 → A, B, C, D

- 높이(height) : Tree의 최대 레벨 → 3

- 레벨(level) : Tree의 각층의 번호

- 차수(degree) : 노드가 가지고 있는 자식 노드의 개수 → A = 3, B = 3, C = 1, D = 2

- 형제 노드 : 같은 레벨에 있는 노드들의 관계

 

이진 트리 (Binary Tree)

- 모든 노드가 2개의 서브 트리를 보유

- 서브 트리는 공집합도 가능 → 노드를 하나도 갖지 않을 수도 있다

- 모든 노드는 차수가 2 이하이다

 

 

※ Example) 노드의 개수가 k개, 높이가 n

 

- 최소 노드 개수 = n개

- 최대 노드 개수 = 2ⁿ-1개

- 최소 높이 = k

- 최대 높이 = log₂(k+1)개

- 간선의 개수 = k-1개

 

 

이진트리 분류

● 포화 이진 트리 (full binary tree)

• 트리의 각 레벨에 노드가 꽉 차있는 이진트리
• 높이가 n인 포화 이진트리 : 2ⁿ-1개의 노드 보유
• 노드의 각 번호는 레벨 단위로 왼쪽 → 오른쪽으로 번호 부여

 

● 완전 이진 트리 (complete binary tree)

- 높이가 n일때 

• 레벨 1~n-1까지의 노드는 모두 채워져있다
• 마지막 레벨 n에서는 왼쪽 → 오른쪽으로 노드가 순서대로 채워져있다
• 마지막 레벨 n에는 노드가 모두 채워져 있지 않아도 된다, 하지만 중간에 빈곳이 있으면 안된다

 

● 기타 이진 트리

• 포화/완전 이진 트리가 아닌 이진 트리