트리란?
트리는 한 개 이상의 노드(node)로 이루어진 유한 집합으로서
- 노드 중에는 루트(root)노드가 한 개 있고
- 나머지 노드들은 n >= 0개의 분리 집합 T1, ...... Tn으로 분할될 수 있다. 여기서 T1, ...... Tn은 각각 하나의 트리이며 루트의 서브트리(subtree)라고 한다
- 차수(degree) : 한 노드가 가지고 있는 서브트리의 수, 차수가 0인 노드는 리프노드(leaf node)
- 트리의 차수(degree of tree) : 트리의 최대 차수, 트리의 차수가 n이면 해당 트리의 구조를 'n진 트리' 라고 함
- 간선(edge) : 노드와 노드의 연결선. 노드가 n개이면 엣지는 n - 1개
- 루트 노드(root node) : 레벨이 1인 노드
- 리프 노드(leaf node) : 차수가 0인 노드
- 자식 노드(child node) : 한 노드가 가진 서브트리의 루트 노드, 그림에서 B의 자식노드는 D와 E
- 부모 노드(parent node) : 자식 노드에서 루트노드 방향으로 직접 연결 된 노드
- 형제 노드(sibling node) : 같은 부모를 갖는 노드
- 조상 노드(ancestor node) : 루트에서 해당 노드로 이르는 경로상의 모든 노드
- 레벨(level) : 루트노드(0 or 1)부터 특정 노드까지 간선의 수, 그림에서 J의 레벨은 3
- 높이(height) : 트리의 최대 레벨, 루트에서의 경로 중 가장 긴 경로
- 링크필드(link field) : 다른 노드의 주소를 저장한 공간(포인터), 그림에서 노드 C는 F와 G를 가리키는 포인터를 가짐
- 노드의 수가 n이고 트리의 차수가 k일 때 총 링크필드의 수는 nk
- 노드의 수가 n일 때 현재 사용중인 링크필드는 n - 1
- 노드의 수가 n이고 트리의 차수가 k일 때 사용하지 않는 링크필드의 수는 (k * n) - (n - 1)이므로 (k - 1)n + 1
- 연결되지 않은, 사용중이지 않은 링크필드는 Null 링크 - 트리의 효율(tree efficiency) : Null링크의 발생율로 계산 가능. ((k - 1)n + 1) / (nk) * 100
- k가 2일 때 (n + 1) / (2n) * 100이므로 시간복잡도로 n이 충분히 크다고 가정하면 1/2, 즉 50%의 Null링크가 발생
- k가 3일 때 (2n + 1) / (3n) * 100이므로 n이 충분히 클 때 2/3, 즉 66.67%의 Null링크가 발생
1. 트리의 리스트 표현
2. 이진트리
이진트리란 다음의 성질을 만족하는 노드의 집합
- 공백이거나
- 루트노드와 서로 분리된 두 개의 이진트리, 즉 왼쪽 부트리와 오른쪽 부트리로 구성됨
- A의 왼쪽자식이 B인 트리와 A의 오른쪽자식이 B인 트리는, 일반 트리의 관점에서는 같지만 이진트리의 관점에서는 각각 오른쪽 공백과 왼쪽 공백을 가지므로 다른 트리로 봄
2-1. 이진트리의 성질
- 이진트리의 레벨 i에서의 최대 노드 수는 2의 i-1승 개 이다 (i >= 1)
- 높이가 k인 이진트리의 최대 노드 수는 2^k - 1 개 이다 (k >= 1)
- 높이가 k이고 노드의 수가 2^k - 1 개인, 모든 노드가 가득 찬 이진트리를 포화이진트리 라고 한다
2-2. 이진트리의 종류
- 편향 이진 트리(skewed binary tree) : 왼쪽 혹은 오른쪽 서브트리만 갖는 이진트리
- 완전 이진트리(complete binary tree) : 모든 노드가 위에서 아래로, 왼쪽에서 오른쪽의 순서대로 채워져 있는 트리
- 전 이진트리(full binary tree) : 채워져 있는 순서에 상관 없이, 모든 노드가 자식을 0개 혹은 2개를 갖고 있는 이진 트리
- 포화 이진트리(perfect binary tree) : 높이가 k일 때(k >= 1) 2^k - 1개의 노드(최대 노드의 수만큼)를 가지는 트리
