개념
트리(tree)
- 노드(node)들의 집합
- 각 노드는 '값(value)'과 다른 노드들을 가리키는 '레퍼런스'로 구성
관련 용어
간선(edge)
- 노드와 노드를 연결하는 선
- 구현 관점에서는 레퍼런스를 의미
- link / branch 라고도 함
루트 노드
- 트리의 최상단에 있는 노드
- 트리의 시작점
자녀 노드
- 모든 노드는 0개 이상의 자녀 노드를 가진다
부모 노드
- 자녀 노드를 가지는 노드
형제(sibling) 노드
- 같은 부모를 가지는 노드들
조상(ancestor) 노드
- 부모 노드를 따라 루트 노드까지 올라가며 만나는 모든 노드
자손(descendant) 노드
- 자녀 노드를 따라 내려가며 만날 수 있는 모든 노드
내부(internal) 노드
- 자녀 노드를 가지는 노드
- branch node 또는 inner node 라고도 함
외부(external) 노드
- 자녀 노드가 없는 노드
- leaf node / outer node / terminal node(단말 노드) 라고도 함
경로(path)
- 한 노드에서 다른 노드 사이의, 노드들의 시퀀스
경로 길이(length of path)
- 경로에 있는 노드들의 수
노드의 높이(height)
- 노드에서 자손 노드 중, leaf node 까지의 가장 긴 경로의 edge 수
/ 간혹 node 수 인 경우도 있으니 유의
트리의 높이
- 루트 노드의 높이
노드의 깊이(depth)
- 루트 노드에서 해당 노드까지 경로의 edge 수
트리의 깊이
- 트리에 있는 노드들의 깊이 중, 가장 긴 깊이
- 트리의 높이 = 트리의 깊이
노드의 차수(degree)
- 노드의 자녀 노드 수
트리의 차수
- 트리에 있는 노드들의 차수 중 가장 큰 차수
두 노드 사이의 거리(distance)
- 두 노드의 최단 경로의 edge 수
노드의 레벨
- 노드와 루트 노드 사이의 경로에서 edge의 수
- 루트 노드의 레벨: 0 (or 1)
width
- 임의의 레벨에서 노드의 수
노드의 크기(size)
- 자신을 포함한 자손 노드의 수
트리의 크기
- 트리의 모든 노드의 수
서브 트리(subtree)
- 각 노드의 자녀 노드들을 재귀적으로 서브 트리를 구성한다
주요 특징
- 루트 노드는 하나만 존재 (대우명제: 하나가 아니라면, 트리가 아님)
- 사이클이 존재하지 않음
- 자녀 노드는 하나의 부모 노드만 존재 (대우명제: 하나가 아니라면, 트리가 아님)
- 데이터를 순차적으로 저장하지 않는 비선형(nonlinear) 구조
- 트리에 서브 트리가 있는 재귀적 구조
- 계층적 구조
이진 트리(binary)
- 각 노드의 자녀 노드 수가 최대 2개 (left child/right child) 인 트리
이진 트리의 다양한 형태
full binary tree (정 이진 트리)
- 모든 노드는 자녀 노드가 0개 or 2개인 트리
complete binary tree (완전 이진 트리)
- 마지막 레벨을 제외한 모든 레벨에서 노드가 빠짐없이 채워져 있고,
마지막 레벨은 왼쪽부터 빠짐없이 노드가 채워져 있는 트리
perfect binary tree (포화 이진 트리)
- 모든 레벨에서 노드가 빠짐없이 채워져 있는 트리
degenerate binary tree (변질 이진 트리)
- 모든 부모 노드는 하나의 자녀 노드만 가지는 트리
- pathological binary tree 라고도 함
- skewed binary tree 라고도 함
degenerate binary tree 의 특수한 예 (2가지)
1) left skewed binary tree: 모든 부모 노드는 왼쪽 자녀 노드만 가지는 트리
2) right skewed binary tree: 모든 부모 노드는 오른쪽 자녀 노드만 가지는 트리
balanced binary tree (균형 이진 트리)
- "모든 노드"에서 왼쪽/오른쪽 서브 트리의 높이 차이가 최대 1인 트리
그 외
(자료 구조의 관점에서) 트리를 '구현'하는 방법
- 노드들을 레퍼런스로 연결하는 방법
- 배열을 통해 구현하는 방법
트리에서 경로(path) 라는 개념
- 엄밀한 또는 좁은 의미에서는 (화살표의 방향을 따라) 위에서 아래로 갈 수 있는 경우로 한정함
- 하지만 넓은 의미로 사용되는 경우도 있음.
즉, 화살표 방향과 상관 없이 edge로 연결만 되면, 경로(path)라고 하는 경우도 있음
