Special Effects FX 스스로를 감동시켜야 최선을 다 한 것이다.

트리의 개요

트리는 계층적 관계(Hierarchical Realationship) 를 표현하는 자료구조이다.

트리는 가지를 늘려가며 뻗어나가는 자료구조이다.

※ 자료구조는 무엇인가를 '표현'하는 도구이다. 표현을 위해서 저장과 삭제라는 기능이 제공되는 것으로 이해하는 것이 옳다.

트리가 표현할 수 있는 것들

컴퓨터의 디렉토리 구조, 집안의 족보나 기업 및 정부의 조직도 등등

트리 관련 용어

노드:  node

- 트리의 구성요소에 해당하는 요소

간선: edge

- 노드와 노드를 연결하는 연결선

루트 노드: root node

- 트리 구조에서 최상위에 존재하는 노드

단말 노드: terminal node

- 아래로 또 다른 노드가 연결되어 있지 않은 노드

내부 노드: internal node

- 단말 노드를 제외한 모든 노드

참고로 '단말 노드'는 나무의 구조상 잎에 해당한다 하여 '잎사귀 노드(leaf node)' 라고도 불리며, '내부 노드'는 단말 노드가 아니라 하여 '비단말 노드(non-internal node)' 라 불린다.

그리고 노드간에는 부모(parent), 자식(child), 형제(sibling)의 관계가 성립이 된다. 

# 노드 A는 노드 B, C, D의 부모 노드이다.

# 노드 B, C, D는 노드 A의 자식 노드이다.

# 노드 B, C, D는 부모 노드가 같으므로, 서로가 서로에게 형제 노드이다.

그런데 부모와 자식의 관계는 상대적이다. 따라서 노드 B는 노드 A의 자식 노드이지만, 동시에 노드 E와 F의 부모 노드도 된다.

조금 더 나아가서 조상(Ancestor), 후손(Descendant)의 관계도 있다. 특정 노드의 위의 위치한 모든 노드를 가리켜 '조상 노드' 라 하고, 특정 노드의 아래에 위치한 모든 노드를 가리켜 '후손 노드' 라 한다. 

즉 노드 A와 B는 노드 E의 조상 노드이다. 반면 노드 B, C, D, E, F는 모두 노드 A의 후손 노드이다.

이진 트리(Binary Tree)와 서브 트리(Sub Tree)

서브 트리: 큰 트리에 속하는 작은 트리를 가리켜 '서브 트리(sub tree)' 라 한다.

이진 트리: 이진 트리는 다음 두 조건을 만족해야 한다.

1) 루트 노드를 중심으로 두 개의 서브 트리로 나뉘어진다.

2) 나위어진 두 서브 트리도 모두 이진 트리이어야 한다.

※ 이진 트리의 조건 자체가 재귀적이다.

이진트리가 되려면, 루트 노드를 중심으로 둘로 나뉘는 두 개의 서브 트리도 이진 트리이어야 하고, 그 서브 트리의 모든 서브 트리도 이진 트리이어야 한다.

공집합(empty set)

노드가 위치할 수 있는 곳에 노드가 존재하지 않는다면, 공집합(empty set) 노드가 존재하는 것으로 간주한다. 물론 공집합 노드도 이진 트리의 판단에 있어서 노드로 인정한다.

포화 이진 트리(Full Binary Tree)와 완전 이진 트리(Complete Binary Tree)

레벨(level): 트리에서는 각 층별로 숫자를 매겨서 리르 트리의 '레벨'이라 한다.

높이(height): 트리의 최고 레벨을 가리켜 '높이'라 한다.

포화 이진 트리: 모든 레벨이 꽉 찬 이진 트리를 가리켜 '포화 이진 트리'라 한다.

완전 이진 트리: 포화 이진 트리처럼 모든 레벨이 꽉 찬 상태는 아니지만, 차곡차곡 빈 큼 없이 노드가 채워진 이진 트리를 뜻한다. 

즉, 노드가 위에서 아래로, 그리고 외쪽에서 오른쪽으로 순서대로 채워진 트리를 말한다.