반응형
SMALL
★ Tree(트리)
1. 정의
트리는 1개 이상의 노드를 갖는 집합으로 노드들은 다음 조건을 만족
* 트리에는 루트(root)라고 부르는 특별한 노드가 있다.
* 다른 노드들은 원소가 중복되지 않는 n개의 부속 트리 (subtree)
노드들을 연결하는 링크(link)들로 같이 구성됨.
자료구조 트리(tree)는 나무를 거꾸로 그리는걸로 이해하면 됨 (위 사진 참조)
2. 왜 필요할까?
트리 구조에 저장하면 더 효율적인 자료들이 있기 때문
ex) 계층적인 데이터 형태들은 트리에 저장하면 자연스럽게 표현됨.
회사, 정부 조직 구조, 나라, 지방, 인덱스 등등...
3. 용어
- 링크(link) : 노드를 연결하는 선 (edge, branch 라고도 함)
- 루트 노드(root node) : 부모가 없는 노드, 트리는 하나의 루트 노드만을 가짐
- 단말 노드(leaf node) : 자식이 없는 노드
- 내부(internal) 노드 : 리프 노드가 아닌 노드
- 형제(sibling) : 같은 부모를 가지는 노드
4. 트리의 기본적인 성질
- 노드가 N개인 트리는 항상 N-1개의 링크(link)를 가짐
- 트리에서 루트에서 어떤 노드로 가는 경로는 유일.
★노드의 차수(degree)
부(하위) 트리 갯수/간선수(degree) = 각 노드가 지닌 가지의 수
A = 2
B = 3
C = 2
E = 2
★노드의 크기(size)
자신을 포함한 모든 자손 노드의 개수
B의 크기 = 6
★ 노드의 깊이(depth)
루트에서 어떤 노드에 도달하기 위해 거쳐야 하는 간선의 수
B의 깊이 = 2
J의 깊이 = 3
★ 노드의 레벨
트리의 특정 깊이를 가지는 노드의 집합
A의 레벨 : 1
B, C의 레벨 : 2
D, E, F, G, H의 레벨 : 3
I, J의 레벨 : 4
★트리의 차수(degree of tree)
트리의 최대 차수
B가 최대 차수를 가짐 = 3
★트리의 높이(height)
루트 노드에서 가장 깊숙히 있는 노드의 깊이 = 3
반응형
LIST