트리와 터미널로지
트리 구조
- 자료의 계층적인 성질을 토식으로 표현하는 방법
- Etc): 조직도, 토너먼트, 카테고리, 파일 시스템, etc…
루트가 있는 트리
- 트리 구조를 노드와 간선의 집합으로 표현한 것
(일반적인 트리)트리
- 루트가 없는 트리
→ 사이클이 없고 방향이 없고 연결된 그래프
→ 트리에는 루트가 없지만 루트를 정하면 루티드 트리가 된다.
노드
- 유닛, 노드 혹은 버텍스라고 부른다.
간선
- 두 노드 사이에 있는 연결, 엣지 혹은 아크라고 부른다.
부모 노드
- 노드 X의 부모 노드는 X와 간선으로 연결된 노드 중 루트에 더 가까운 노드
자식 노드
- 노드 X의 부모 노드는 X와 간선으로 연결된 노드 중 루트에서 더 멀리있는 노드
단말 노드
- 자식이 없는 노드, 리프 노드라고 한다.
내부 노드
- 단말 노드가 아닌 노드, 인터널 노드라고 한다.
조상 노드
- 부모 노드는 조상노드
- 조상 노드의 부모 노드 역시 조상 노드
자손 노드
- 자식 노드는 자손 노드
- 자손 노드의 자식 노드 역시 자손 노드
노드의 깊이
- 루트 노드와의 거리(루트 노드의 깊이는 0이다.)
레벨
- 깊이가 같은 노드들의 집합
트리의 높이
- 노드의 최대 깊이
서브트리
- 한 노드와 그 노드의 모든 자손 노드를 포함하는 트리
이진 트리
이진 트리
- 각 노드가 자식 노드를 최대 두 개까지만 가지는 트리
- 두 자식 노드는 각 왼쪽 자식(Left), 오른쪽 자식(Right)이라고 부름
- 엄밀히 말해서 이진 트리는 트리가 아니다.
- 트리는 방향성이 존재하지 않는다.
- 트리에서는 자식들의 순서가 상관 없는데 이진 트리는 순서가 상관있다.
정 이진 트리
- 각 노드의 자식 수가 2 또는 0인 트리
완전 이진 트리
- 가장 깊은 레벨을 제외한 모든 레벨이 가득 차 있음
- 마지막 레벨의 노드들은 가능한 왼쪽에 존재
포화 이진 트리 ⇒ 다 채워진 완전 이진트리
- 모든 단말 노드의 레벨이 같음
- 모든 내부 노드의 자식의 수가 2임
정 이진 트리 정리
⇒ 비어있지 않은 정 이진 트리의 리프 노드 수는 내부 노드의 수보다 한 개 많다.
⇒ Leaf node의 수 = internal node의 수 +1
정 이진 트리의 따름 정리
⇒ 비어있지 않은 이진 트리에서 null pointer의 수는 노드의 수보다 1개 많다.
이진 트리 순회
순회
- 순서대로 정확하게 한 번씩만 노드를 방문하는 과정
열거
- 트리의 각 노드를 정확히 한 번씩 나열하는 순회 방법
전위 순회
- 현재 노드를 방문하고, 자식들을 순회한다.
후위 순회
- 자식들을 방문하고, 현재 노드를 방문한다.
중위 순회
- 왼쪽 서브트리를 방문하고, 현재 노드를 방문하고, 오른쪽 서브트리를 방문한다.
알아야 할 것
- (이진) 트리의 개념 및 그 용어
- 정 이진 트리의 개념과 정리 및 증명
- 지정된 트리에 대해 세 개의 주요 순회를 수행하는 방법, 순회를 구현하는 방법
