트리
- 그래프를 계층화시킨 형태
- 루트 노드라는 최상위 노드가 존재하고, 이는 유일하다
- 사이클이 존재해서는 안 된다
용어
- 루트 노드 (Root node) : 부모 노드가 없는 노드
*위 그림에서는 0번 노드를 루트 노드로 설정하였다
- 리프 노드 (Leaf node) : 자식 노드가 없는 노드
*4, 5, 6, 7, 8번 노드는 자식 노드가 없으므로 리프 노드이다
- 노드의 차수 (Degree) : 자식 노드의 개수
*1번 노드의 차수는 2이다
- 노드의 깊이 (Depth) : 루트 노드로부터의 거리
*8번 노드의 깊이는 3이다
- 노드의 높이 (Height) : 리프 노드로부터의 최대 거리
*0번 노드의 높이는 3이다 (2가 아님에 주의하자)
- 트리의 차수/깊이/높이 : 트리 내의 노드가 가질 수 있는 최대 차수/깊이/높이
*위 그림에서 트리의 차수, 깊이, 높이는 모두 3이다
예시
- 우측 그림은 사이클이 존재하므로 트리가 아니다
- 좌측 그림을 정렬하면 우측 그림처럼 트리가 된다
- 아무리 단조로워도 조건만 만족하면 트리라고 할 수 있다
댓글