트리
정의
- 원소 사이의 1:n의 관계를 가지는 비선형 자료구조
- 자료가 저장되는 노드와 노드를 연결하는 간선으로 이루어짐
특성
트리 T가 있을 때,
- 1개 이상의 노드로 이루어진 유한 집합
- 반드시 하나의 루트 노드가 존재함
- 루트 노드 이외의 노드는 n>=0의 부분집합
- T1, T2, … Tn으로 나누어지며, 이들은 각각 하나의 트리가 될 수 있음(서브 트리)
용어
- 루트 노드 (root) : 트리의 최상위 노드
- 1번 노드
- 리프 노드 (leaf, terminal) : 트리의 가장 아래쪽 노드, 차수가 0인 노드
- 5,6,7,8,9번 노드
- 내부 노드 (non-terminal) : 리프 노드 이외의 노드, 차수가 0이 아닌 노드
- 1,2,3,4번 노드
- 자식 노드 (child) : 간선으로 연결된 아래 노드. 여러 개 존재 가능함
- 2번 노드의 자식 노드는 4,5,6번 노드
- 부모 노드 (parent) : 간선으로 연결된 위 노드. 하나만 존재 가능함
- 5번 노드의 부모 노드는 2번 노드. 7번 노드의 부모 노드는 3번 노드
- 형제 노드 (sibling) : 부모 노드가 같은 노드들
- 4,5,6번 노드는 부모 노드가 2번 노드라는 공통점을 가지고 있기 때문에, 형제 노드이다.
- 조상 노드 (ancestor) : 간선을 따라 위로 올라가면서 만나는 모든 노드들
- 8번 노드의 조상 노드는 4,2,1번 노드
- 자손 노드 (descendant) : 간선을 따라 아래로 내려가면서 만나는 모든 노드
- 2번 노드의 자손 노드는 4,5,6,8,9번 노드
- 레벨 (level) : 루트 노드의 레벨을 1로 하고, 간선을 뻗을 때마다 1씩 증가한다
- 1번 노드는 레벨1 / 2,3번 노드는 레벨 2 …
- 차수 (degree) : 각 노드가 가지는 자식 노드의 수
- 1번 노드의 차수는 2, 2번 노드의 차수는 3
- 높이 (height) : 트리의 최대 레벨
- 이 트리의 높이는 4
트리의 순서
형제 노드 사이에 순서가 있는 경우 순서 트리
형제 노드 사이에 순서가 없는 경우 비순서 트리