728x90
반응형
SMALL
A
/ \
B C
/ \ \
D E F
/ \
G H
기본 구성 라벨링
- 노드: A, B, C, D, E, F, G, H
- 간선: (A–B), (A–C), (B–D), (B–E), (C–F), (E–G), (E–H)
- 루트: A
- 부모/자식:
- A의 자식 = {B, C}
- B의 자식 = {D, E}
- C의 자식 = {F}
- E의 자식 = {G, H}
- 형제: (B, C), (D, E), (G, H)
- 조상/후손: 예) H의 조상 = {E, B, A}, B의 후손 = {D, E, G, H}
차수(Degree)
- 노드의 차수(자식 수)
- deg(A)=2, deg(B)=2, deg(C)=1, deg(D)=0, deg(E)=2, deg(F)=0, deg(G)=0, deg(H)=0
- 트리의 차수 = max 노드 차수 = 2
- 리프(차수 0): D, F, G, H
- 내부 노드(자식 ≥1): A, B, C, E
깊이/레벨/높이 (간선 수 기준, 루트 깊이=0)
- 깊이(=레벨)
- depth(A)=0
- depth(B)=1, depth(C)=1
- depth(D)=2, depth(E)=2, depth(F)=2
- depth(G)=3, depth(H)=3
- 노드의 높이(해당 노드에서 가장 깊은 리프까지의 간선 수)
- h(D)=0, h(F)=0, h(G)=0, h(H)=0 (리프는 0)
- h(E)=1 (E→G/H)
- h(B)=2 (B→E→G/H 경로)
- h(C)=1 (C→F)
- h(A)=3 (A→B→E→G/H)
- 트리의 높이 = 루트 A의 높이 = 3
경로 길이(Path length)
- A→H 경로: A–B–E–H → 간선 수 3
- A→F 경로: A–C–F → 간선 수 2
- 내부 경로 길이(예: 내부 노드 깊이 합)
- 내부 노드 = {A(0), B(1), C(1), E(2)} → 합 = 0+1+1+2 = 4
간선 수 확인
- 노드 수 n=8 → 간선 수 = n−1 = 7 (트리 성질)
728x90
반응형
LIST