간단히 알아보는 트리

트리

• 그래프를 계층화시킨 형태
• 루트 노드라는 최상위 노드가 존재하고, 이는 유일하다
• 사이클이 존재해서는 안 된다

 

---

 

용어

• 루트 노드 (Root node) : 부모 노드가 없는 노드

*위 그림에서는 0번 노드를 루트 노드로 설정하였다

 

• 리프 노드 (Leaf node) : 자식 노드가 없는 노드

*4, 5, 6, 7, 8번 노드는 자식 노드가 없으므로 리프 노드이다

 

• 노드의 차수 (Degree) : 자식 노드의 개수

*1번 노드의 차수는 2이다

 

• 노드의 깊이 (Depth) : 루트 노드로부터의 거리

*8번 노드의 깊이는 3이다

 

• 노드의 높이 (Height) : 리프 노드로부터의 최대 거리

*0번 노드의 높이는 3이다 (2가 아님에 주의하자)

 

• 트리의 차수/깊이/높이 : 트리 내의 노드가 가질 수 있는 최대 차수/깊이/높이

*위 그림에서 트리의 차수, 깊이, 높이는 모두 3이다

 

 

---

 

예시

• 우측 그림은 사이클이 존재하므로 트리가 아니다

 

• 좌측 그림을 정렬하면 우측 그림처럼 트리가 된다

 

• 아무리 단조로워도 조건만 만족하면 트리라고 할 수 있다