트리 (tree)
- 원소들 간 1 : 多 관계를 가지는 비선형 자료구조
- 원소들 간 계층 관계를 가지는 계층형 자료구조
- 상위 원소에서 하위 원소로 내려가면서 확장되는 나무 모양의 구조
ex)
☞ 노드 - 트리의 원소 : A, B, C, D, E, F, G, H, I, J, K, L
☞ 루트 노드 - 트리의 시작 노드 : A
☞ 간선 - 노드를 연결하는 선(= 부모 노드와 자식 노드를 연결하는 선)
☞ 형제 노드 - 같은 부모 노드의 자식 노드들 : (B, C, D), (E, F), (H, I, J), (K, L)
☞ 조상 노드 - 간선을 따라 루트 노드까지 이르는 경로에 있는 모든 노드들 : K의 조상 노드 = F, B, A
☞ 서브 트리 - 부모 노드와 연결된 간선을 끊었을 때 생성되는 트리 : 자식 노드의 개수만큼 서브 트리 생성
☞ 자손 노드 - 서브 트리에 있는 하위 레벨의 노드들 : B의 자손 노드 = E, F, K, L
☞ 차수
ㄴ 노드의 차수 - 노드에 연결된 자식 노드의 수 : A의 차수 = 3, B의 차수 = 2, C의 차수 = 1
ㄴ 트리의 차수 - 트리에 있는 노드의 차수 중 가장 큰 값 : 트리 A의 차수 = 3
ㄴ 단말 노드(리프 노드) - 차수가 0인 노드(= 자식 노드가 없는 노드) : E, K, L, G, H, I, J
☞ 높이
ㄴ 노드의 높이 - 루트에서 노드에 이르는 간선의 수(= 노드의 레벨) : B의 높이 = 1, F의 높이 = 2
ㄴ 트리의 높이 - 트리에 있는 노드의 높이 중 가장 큰 값(= 최대 레벨) : 트리 A의 높이 = 3
☞ 포리스트 - 서브 트리의 집합
이진트리 (Binary Tree)
- 트리의 노드 구조를 일정하게 정의하여 트리의 구현과 연산이 쉽도록 정의한 트리
- 모든 노드는 왼쪽 자식 노드와 오른쪽 자식 노드만을 가짐
ㄴ 부모 노드 : 자식 노드 수 = 1 : 2
ㄴ 공백 노드도 자식 노드로 취급
ㄴ 0 ≤ 노드의 차수 ≤ 2
- 이진트리의 서브 트리도 이진트리
- 특성
ㄴ n개의 노드를 가진 이진트리는 항상 n-1개의 간선을 가진다.
ㄴ 높이가 h인 이진트리가 가질 수 있는 노드의 최소 개수는 h+1개가 되며, 최대 개수는 2^(h+1) -1개가 된다.
- 종류
① 포화 이진트리
> 모든 레벨에 노드가 포화상태로 차 있는 이진트리
> 높이가 h일 때, 최대의 노드 개수인 2^(h+1) -1개의 노드를 가진 이진트리
> 루트를 1번으로 하여 2^(h+1)-1까지 정해진 위치에 대한 노드 번호를 가진다.
② 완전 이진트리
> 높이가 h이고 노드 수가 n개일 때 (단, h+1 ≤ n ≤ 2^(h+1)) , 포화 이진트리의 노드 번호 1번부터 n번까지 빈 자가 없는 이진트리
③ 편향 이진트리
> 높이 h에 대한 최소 개수의 노드를 가지면서 한쪽 방향의 자식 노드만을 가진 이진트리
> (좌) 왼쪽 편향 이진트리, (우) 오른쪽 편향 이진트리
순차 자료구조를 이용한 이진트리의 구현
- 1차원 배열의 순차 자료구조 사용
ㄴ 높이가 h인 포화 이진트리의 노드 번호를 배열의 인덱스로 사용
ㄴ 인덱스 0번 : 실제로 사용하지 않고 비워둠
ㄴ 인덱스 1번 : 루트 노드
| 노드 | 인덱스 | 성립 조건 |
| 노드 i의 부모 노드 | ⌊ i / 2 ⌋ | i > 1 |
| 노드 i의 왼쪽 자식 노드 | 2 X i | (2 X i) ≤ n |
| 노드 i의 오른쪽 자식 노드 | (2 X i) + 1 | (2 X i + 1) ≤ n |
| 루트 노드 | 1 | 0 < n |
단점
- 편향 이진트리의 경우 사용하지 않는 배열 원소에 대한 메모리 공간 낭비 발생
- 트리의 원소 삽입/삭제에 대한 배열 크기 변경 어려움
연결 자료구조를 이용한 이진트리의 구현
- 연결 리스트를 사용하여 구현
[자료구조] 이중 연결 리스트
이중 연결 리스트(doubly linked list) - 양쪽 방향으로 순회할 수 있도록 노드를 연결한 리스트 - 이중 연결 리스트의 노드 구조 ㄴ 두 개의 링크 필드와 한 개의 데이터 필드로 구성 ㄴ llink(left link
kwin0825.tistory.com
이진트리의 순회(traversal)
- 계층적 구조로 저장되어 있는 트리의 모든 노드를 방문하여 데이터를 처리하는 연산
ㄴ 현재 노드를 방문하여 데이터를 읽는 작업
ㄴ 현재 노드의 왼쪽 서브 트리로 이동하는 작업
ㄴ 현재 노드의 오른쪽 서브 트리로 이동하는 작업
- 이진트리가 순환적으로 정의되어 구성되어 있으므로, 순회 작업도 서브 트리에 대해서 순환적으로 반복하여 완성
- 왼쪽 서브 트리에 대한 순회를 오른쪽 서브 트리보다 먼저 수행한다.
- 순회의 종류
ㄴ 전위 순회 : 노드 데이터 읽기 > 왼쪽 서브 트리 이동 > 오른쪽 서브 트리 이동
ㄴ 중위 순회 : 왼쪽 서브 트리 이동 > 노드 데이터 읽기 > 오른쪽 서브 트리 이동
ㄴ 후위 순회 : 왼쪽 서브 트리 이동 > 오른쪽 서브 트리 이동 > 노드 데이터 읽기
전위 순회(preorder traversal) >>> A - B - D - H - E - I - J - C - F - G - K
- 노드 데이터 읽기 > 왼쪽 서브 트리 이동 > 오른쪽 서브 트리 이동
① 루트 A에서 시작하여 현재 노드 A의 데이터를 읽고, 왼쪽 서브 트리 B로 이동한다.
② 현재 노드 B의 데이터를 읽고, 왼쪽 서브 트리 D로 이동한다.
③ 현재 노드 D의 데이터를 읽는다.
④ 현재 노드 D의 왼쪽 단말 노드 H의 데이터를 읽고, 오른쪽 노드인 공백 노드를 읽는 것으로 노 드 D에 대한 순회가 끝난다. 이제 현재 노드 D의 이전 경로인 노드 B의 오른쪽 서브 트리 E로 이동한다.
⑤ 현재 노드 E의 데이터를 읽는다.
⑥ 현재 노드 E의 왼쪽 단말 노드 I의 데이터를 읽는다.
⑦ 현재 노드 E의 오른쪽 단말 노드 J의 데이터를 읽는 것으로 노드 E에 대한 순회가 끝나고, 이것으로 노드 E의 이전 경로인 노드 B의 오른쪽 서브 트리의 순회가 끝난다.
⑧ 현재 노드 C의 데이터를 읽는다.
⑨ 현재 노드 C의 왼쪽 단말 노드 F의 데이터를 읽고, 오른쪽 서브 트리 G로 이동한다.
⑩ 현재 노드 G의 데이터를 읽는다.
⑪ 공백 노드인 왼쪽 단말 노드를 읽고, 현재 노드 G의 오른쪽 단말 노드 K의 데이터를 읽는다.
중위 순회(inorder traversal) >>> H - D - B - I - E - J - A - F - C - G - K
- 왼쪽 서브 트리 이동 > 노드 데이터 읽기 > 오른쪽 서브 트리 이동
① 루트 A에서 시작하여 노드 A의 왼쪽 서브 트리 B로 이동한다. 현재 노드 B의 왼쪽 서브 트리 D로 이동한다. 현재 노드 D의 왼쪽 단말 노드 H의 데이터를 읽는다.
② 현재 노드 D의 데이터를 읽고, 오른쪽 단말 노드인 공백 노드를 읽고 이전 경로인 노드 B로 돌아간다.
③ 현재 노드 B의 왼쪽 서브 트리 순회가 끝났으므로, 현재 노드 B의 데이터를 읽고, 오른쪽 서브 트리 E로 이동한다.
④ 현재 노드 E의 왼쪽 단말 노드 I의 데이터를 읽는다.
⑤ 현재 노드 E의 데이터를 읽는다.
⑥ 현재 노드 E의 오른쪽 단말 노드 J의 데이터를 읽고, 이전 경로인 노드 B로 이동한다.
⑦ 노드 B는 이미 방문했으므로 다시 이전 경로인 노드 A로 이동한다. 이로써 현재 노드 A의 왼쪽 서브 트리에 대한 순회가 끝났으므로 현재 노드 A의 데이터를 읽고, 오른쪽 서브 트리 C로 이동한다.
⑧ 현재 노드 C의 왼쪽 단말 노드 F의 데이터를 읽는다.
⑨ 현재 노드 C의 데이터를 읽고, 오른쪽 서브 트리 G로 이동한다.
⑩ 현재 노드 G의 왼쪽 단말 노드인 공백 노드를 읽고, 현재 노드 G의 데이터를 읽는다.
⑪ 현재 노드 G의 오른쪽 단말 노드 K의 데이터를 읽는다.
후위 순회(postorder traversal) >>> H - D - I - J - E - B - F - K - G - C - A
- 왼쪽 서브 트리 이동 > 오른쪽 서브 트리 이동 > 노드 데이터 읽기
①루트 A에서 시작하여 노드 A의 왼쪽 서브 트리 B로 이동한다. 현재 노드 B에서 왼쪽 서브 트리 D로 이동한다. 현재 노드 D의 왼쪽 단말 노드 H의 데이터를 읽는다.
② 현재 노드 D의 오른쪽 단말 노드인 공백 노드를 읽는다. 현재 노드 D의 데이터를 읽고, 이전 경로 인 노드 B로 이동한다.
③ 현재 노드 B의 왼쪽 서브 트리에 대한 순회가 끝났으므로 현재 노드 B의 오른쪽 서브 트리 E로 이 동한다. 현재 노드 E의 왼쪽 단말 노드 I의 데이터를 읽는다.
④ 현재 노드 E의 오른쪽 단말 노드 J의 데이터를 읽는다.
⑤ 이제 현재 노드 E의 데이터를 읽고, 이전 경로인 노드 B로 이동한다.
⑥ 현재 노드 B의 오른쪽 서브 트리에 대한 순회가 끝났으므로, 현재 노드 B의 데이터를 읽고, 이전 경로인 노드 A로 이동한다.
⑦ 현재 노드 A의 왼쪽 서브 트리에 대한 순회가 끝났으므로, 오른쪽 서브 트리 C로 이동한다. 현재 노 드 C의 왼쪽 단말 노드 F의 데이터를 읽는다.
⑧ 현재 노드 C의 오른쪽 서브 트리 G로 이동한다. 현재 노드 G의 왼쪽 단말 노드인 공백 노드를 읽고, 오른쪽 단말 노드 K의 데이터를 읽는다.
⑨ 이제 현재 노드 G의 데이터를 읽고, 이전 경로인 노드 C로 이동한다.
⑩ 현재 노드 C의 오른쪽 서브 트리에 대한 순회가 끝났으므로, 현재 노드 C의 데이터를 읽고, 이전 경로인 노드 A로 이동한다.
⑪ 루트 노드 A에 대한 오른쪽 서브 트리에 대한 순회가 끝났으므로, 현재 노드 A의 데이터를 읽는다.