1. 트리(Tree)
개념
- 노드들의 집합
- 노드: 값과 각 노드들을 가리키는 레퍼런스로 구성되어 있음
트리 관련 용어
1. 간선(edge)
- 노드와 노드를 연결하는 선
- 구현 관점에서는 레퍼런스를 의미
2. 루트 노드
- 최상단에 위차한 노드
3. 자녀 노드
- 어떤 노드 밑에 연결된 노드
- 모든 노드는 0개 이상의 자녀 노드를 가진다.
4. 부모 노드
- 자녀 노드를 가지는 노드
5. 형제 노드
- 같은 부모 노드를 가지는 노드
6. 조상 노드
- 부모 노드를 따라 루트 노드까지 올라가며 만나는 모든 노드
7. 자손 노드
- 자녀 노드를 따라 내려가며 만나는 모든 노드
8. 내부 노드
- 자녀 노드를 가지는 노드
9. 외부 노드(단말 노드, 리프 노드)
- 자녀 노드를 가지지 않는 노드
10. 경로(path)
- 한 노드에서 다른 노드 사이의 시퀀스(거쳐가는 경로)
- 경로의 길이: 경로에 있는 모든 노드의 수
11. 노드의 높이
- 특정 노드에서 리프 노드까지의 가장 긴 경로의 간선 수
- 리프 노드의 높이: 0
- 시작 지점이 특정 노드
12. 트리의 높이
- 루트 노드의 높이
13. 노드의 깊이
- 루트 노드에서 특정 노드까지의 경로의 간선 수
- 시작 지점이 루트 노드
14. 트리의 깊이
- 트리에 있는 노드의 깊이들 중 가장 큰 깊이
- 트리의 높이 = 트리의 높이
15. 노드의 차수
- 특정 노드의 자녀 노드 수
16. 트리의 차수
- 트리에 있는 노드의 차수들 중 가장 큰 차수
17. 두 노드 사이의 거리
- 두 노드 사이의 최단 경로의 간선 수
18. 노드의 레벨
- 노드와 루트 노드 사이의 경로에서 간선의 수
- 루트 노드의 레벨을 0으로 본다. (문서에 따라 루트 노드의 레벨을 1로 보는 것도 있다.)
19. width
- 임의의 레벨에서 노드의 수
20. 노드의 크기
- 자신을 포함한 자손 노드의 수
21. 트리의 크기
- 트리의 모든 노드 수
트리 구조의 주요 특징
- 루트 노드는 하나만 존재
- 사이클이 존재하지 않음
- 자녀 노드는 하나의 부모 노드만 가질 수 있음
- 데이터를 순차적으로 저장하지 않는 비선형구조
- 트리에 서브트리가 존재하는 재귀적 구조
- 계층적 구조 (부모 - 자식)
2. 이진트리
개념
- 각 노드의 자녀 노드 수가 최대 2개인 트리
형태에 따른 이진트리의 종류
1. 정 이진트리(Full Binary Tree)
- 모든 노드가 자녀 노드가 아예 없거나 두 개인 트리
2. 완전 이진트리(Complete Binary Tree)
- 마지막 레벨을 제외한 모든 레벨에서 노드가 빠짐없이 채워져있고 마지막 레벨은 왼쪽부터 빠짐없이 노드가 다 채워져 있는 트리
3. 변질 이진트리(Degenerate Binary Tree)
- 모든 부모 노드는 하나의 자녀 노드만 가지는 트리
4. 균형 이진트리(Balanced Binaray Tree)
- 모든 노드에서 왼쪽 서브 트리와 오른쪽 서브 트리의 높이 차이가 최대 1인 트리
[Thanks to]
'CS 공부 > 자료구조' 카테고리의 다른 글
| 이진탐색트리(Binary Search Tree) (0) | 2023.02.13 |
|---|---|
| Set과 HashSet (0) | 2023.02.07 |
| 맵(map)과 해시 테이블(hash table) (0) | 2023.02.06 |
| List - ArrayList, LinkedList (0) | 2023.01.26 |
| 배열, 동적배열, 연관배열 (0) | 2023.01.25 |