-
Tree
- 스택이나 큐와 같은 선형 구조가 아닌 비선형 자료구조
- 계층적 관계 (Hierarchical Relationship)을 표현하는 자료구조
Tree 관련 용어
- Node (노드) : 트리를 구성하고 있는 각각의 요소
- Edge (간선) : 트리를 구성하기 위해 노드와 노드를 연결하는 선
- Root Node (루트 노드) : 트리 구조에서 최상위에 있는 노드
- Leaf Node (Terminal Node, 단말 노드) : 하위에 다른 노드가 연결되어 있지 않은 노드
- Internal Node (내부 노드, 비단말 노드) : 단말 노드를 제외한 모든 노드로 루트 노드도 포함
- Sibling Node (Brother Node, 형제 노드) : 동일한 부모를 가지는 노드
- Path (경로) : 한 노드에서 다른 한 노드에 이르는 길 사이에 있는 노드들의 순서
- Level (레벨) : 루트 노드(level = 0)부터 노드까지 연결된 간선 수
- Depth (깊이) : 루트 경로의 길이
- Height (높이) : 가장 긴 루트 경로의 길이 (트리의 최대 레벨)
- Degree (차수) : 각 노드의 자식 노드의 개수
- Degree of Tree (트리의 차수) : 트리에 있는 노드의 최대 차수
- Subtree (서브트리) : 큰 트리에 속하는 작은 트리
- Forest (포레스트) : 서로 독립인 트리들의 모임
Binary Tree (이진 트리)
- 부모 노드 밑의 자식 노드의 개수를 차수(degree)라고 해요
- 차수를 최대 2로 제한하는, 트리의 가장 간단한 형태에요
- 보통 왼쪽 자식과 오른쪽 자식으로 구분지어요
- 따라서
값 - 왼쪽 자식 노드 포인터 - 오른쪽 자식 노트 포인터 로써 구현할 수 있어요
- 모든 트리는 이진 트리로 재구성할 수 있기 때문에 일반적으로 트리 구조는 이진 트리로 구현돼요
Full Binary Tree (정 이진 트리)
- 모든 노드의 자식이 0개이거나 2개인 이진 트리에요. 즉, 자식이 1개인 노드는 없어요
Perfect Binary Tree (포화 이진 트리)
- 모든 리프 노드의 높이가 같고 리프 노드가 아닌 노드는 모두 2개의 자식을 가져요
- 즉, 완전한 이등변삼각형 모양으로 표현할 수 있는 이진 트리에요
- 보통 리프 노드 중 사용되지 않는 노드는 default값 (0, null, false 등) 이 들어가요
Complete Binary Tree (완전 이진 트리)
- 트리의 노드들이 좌측 상단부터 차곡차곡 하나씩 쌓인 형태의 트리에요
- 즉, 왼쪽 자식 노드가 먼저 채워지고 그 후에 오른쪽 자식 노드가 채워져요
- 수학적 성질을 사용하기 용이하고, 배열을 이용해 구현하기도 용이하기 때문에 많이 쓰이는 트리 구조에요