[ch 08-1] 트리의 개요

[트리의 개념]

- 트리는 계층적 관계(Hierarchical Relationship)를 표현하는 자료구조

■ 그림(트리의 계층 개념)

■ 중요 포인트

- 데이터의 저장, 검색 및 삭제 등의 기능의 정의보다, 무엇인가를 표현하기에 적절히 정의되었는지가 더 중요

[트리 관련 용어]

■ 그림(트리 표현)

■ 관계

- 노드간에는 '부모(Parent), 자식(Child), 형제(Sibling)'의 관계가 성립되어 있음

- 노드 'A'는 노드 'B, C, D'의 부모 노드

- 노드 'B, C, D'는 노드 'A'의 자식 노드

- 노드 'B, C, D'는 부모 노드가 같으므로, 서로가 서로에게 형제 노드

1. 노드(Node)

- 트리의 구성요소에 해당하는 'A, B, C, D, E, F'와 같은 요소

2. 간선(Edge)

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

3. 루트 노드(Root Node)

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

4. 단말 노드(Terminal Node, Leaf Node)

- 아래로 또 다른 노드가 연결되어 있지 않은 'E, F, C, D'와 같은 노드

5. 내부 노드(Internal Node, Nonterminal Node)

- 단말 노드를 제외한 모든 노드로 'A, B'와 같은 노드

6. 조상 노드(Ancestor Node)

- 특정 노드의 위에 위치한 모든 노드. 노드 'A, B'는 노드 'E'의 조상 노드

7. 후손 노드(Descendant Node)

- 특정 노드의 아래에 위치한 모든 노드. 'B, C, D, E, F'는 모두 노드 'A'의 후손 노드

[트리의 종류]

1. 서브 트리(Sub Tree)

■ 그림(서브 트리)

- 큰 트리에 속하는 작은 트리를 말함

  ※ 'D, E, F'는 노드 'B'의 서브 트리

2. 이진 트리(Binary Tree)

■ 그림(기본 이진 트리)

■ 규칙

- 루트 노드를 중심으로 두 개의 서브 트리로 나뉘어짐

- 나뉘어진 두 서브 트리도 모두 이진 트리어야 함

- 서브 트리의 모든 서브 트리도 이진 트리어야 함

- 형제 노드가 최대 2개까지 존재하는 상태만 이진 트리로 인정

※ 노드가 위치할 수 있는 곳에 노드가 존재하지 않는다면, 공집합(Empty set) 노드가 존재하는 것으로 간주

■ 그림(공집합이 표현된 이진 트리)

3. 포화 이진 트리(Full Binary Tree)

■ 그림(레벨과 높이)

- 트리에서는 각 층별로 숫자를 매겨서 이를 트리의 '레벨'이라고 말함

- 트리의 최고 레벨을 가리켜 '높이'라고 말함

  ※ 그림의 최고 높이 = '3'

■ 그림(포화 이진 트리)

- 모든 레벨이 꽉 찬 이진 트리를 말함

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

■ 그림(완전 이진 트리)

- 모든 레벨이 꽉 찬 상태가 아니라도, 차곡차곡 빈 틈 없이 채워진 이진 트리를 말함

- 노드가 위에서 아래로, 왼쪽에서 오른쪽의 순서로대로 채워진 상태