트리
트리
트리의 정의
트리란 노드와 간선으로 이루어진 계층형 자료구조이다.
트리의 특징
- 트리는 N개의 노드와 N-1개의 간선으로 이루어져 있다.
- 사이클이 존재하지 않는다.
- 모든 노드는 서로 유일한 경로로 연결되어 있다.
- 모든 트리는 1개의 루트 노드를 갖는다.
- 루트 노드를 제외한 모든 노드는 1개의 부모 노드를 갖는다.
트리의 용어
노드
트리를 이루고 있는 구성요소. A, B, C, D… 등이 노드이다.
간선
노드와 노드를 이어주는 연결선.
루트 노드
부모 노드가 없는 최상위 노드. 트리는 1개의 루트노드를 가진다. 위 트리의 루트 노드는 A이다.
부모 노드
자신과 연결된 상위 계층의 노드. 루트 노드를 제외한 모든 노드는 1개의 부모 노드를 가진다. E, F의 부모 노드는 B이고, B의 부모 노드는 A이다.
자식 노드
자신과 연결된 하위 계층의 노드들. A의 자식 노드는 B, C, D이고, C의 자식 노드는 G이다.
형제 노드
동일한 부모 노드를 가지고 있는 노드들. B의 형제 노드는 C, D이다
조상 노드
임의의 노드 상위에 연결된 모든 노드들. 임의의 노드에서 루트 노드까지의 경로를 구성하는 노드이다. 임의의 노드가 E일 때, E의 조상 노드는 B, A이다.
자손 노드
임의의 노드 하위에 연결된 모든 노드들. B의 자손 노드는 E, F이다.
리프 노드
자식 노드가 없는 노드. “단말노드”라고도 한다. E, F, G, H, I가 리프 노드이다.
내부 노드
리프 노드가 아닌 노드. “비단말 노드” 라고도 한다. A, B, C, D가 내부 노드이다.
차수
“노드의 차수”는 어떤 노드가 가지고 있는 자식 노드의 개수를 의미한다. A의 차수는 3, B의 차수는 2, C의 차수는 1, F의 차수는 0이다. 당연히 리프 노드의 차수는 항상 0이다. “트리의 차수”는 트리의 노드들의 차수 중 가장 큰 값을 의미한다. 위 트리에서 차수가 가장 큰 노드는 A로 3의 차수를 가지고 있다. 따라서 트리의 차수는 3이다.
레벨
각 계층에 번호를 매겨놓은 것이다. 루트 노드의 레벨을 1로 시작하여 아래 계층으로 갈수록 1씩 늘어난다. A의 레벨은 1 B, C, D의 레벨은 2 E, F, G, H, I의 레벨은 3이다.
높이
“트리의 높이”는 트리가 가지고 있는 최대 레벨을 의미한다. 위 트리의 높이는 3이다.
서브 트리
임의의 노드를 루트 노드로 선택하고, 그 노드와 그 노드의 자손 노드들로만 구성된 트리가 있다고 생각해보자. 이 때 루트 노드를 제거하면 루트 노드의 자식 노드들을 루트 노드로 하는 트리들이 만들어진다. 이 트리들을 서브 트리라고 한다. A를 선택했을 때 서브트리는 {B, E, F}, {C, G}, {D, H, I}이고, B를 선택했을 때 서브 트리는 {E}, {F}이다.
포레스트
여러 개의 트리들의 집합. 루트 노드 A를 제거하면 {B, E, F}, {C, G}, {D, H, I}로 구성된 서브 트리 3개가 나온다. 이 때 이 트리들의 집합을 포레스트라고 한다.