cs/자료구조
[자료구조] 트리란?
천방지축 개발자
2023. 7. 13. 21:19
트리란
- 트리는 계층적인 구조를 표현할 때 사용할 수 있는 자료구조
- cycle을 가지지 않는 그래프

트리 관련 용어
- 노드(node) : 트리 자료구조에서 data의 단위
- 간선(edge): 트리나 그래프에서 정점이나 노드끼리 연결되어 있는 선
- 루트 노드(root node): 부모가 없는 최상위 노드
- 단말 노드 or 말단 노드(leaf node): 자식이 없는 노드
- 크기(size): 트리에 포함된 모든 노드의 개수
- 깊이(depth): 루트 노드로부터의 거리
- 높이(height): 깊이 중 최댓값
- 차수(degree): 각 노드의 (자식 방향) 간선 개수
이런 형태도 트리일까?

이 형태는 cycle이 발생하기 때문에 트리가 아니다.
기본적으로 트리의 크기가 N일 때, 전체 간선의 개수는 N-1 이유는 cycle이 생기지 않기 때문이다.
cycle이란?
- 특정 노드에서 시작하여 다시 특정 노드로 돌아오는 경로
- 예) 위 그림으론 A → B → E → A로 가는 cycle이 발생하여 트리가 아니다.
- 저 자료구조는 그래프라는 자료구조이다.
트리 종류
- 이진트리
- 많아야 두 개의 자식 노드를 갖음
- 왼쪽 자식과 오른쪽 자식으로 구분
- 완전 이진트리
- 자식 노드가 왼쪽부터 순서적으로 채워진 이진트리 높이가 균형을 유지
- 포화이진트리
- 각 레밸에서 자식 노드가 모두 채워진 이진트리
- 높이가 균형을 유지
- 트리는 계층적인 구조를 표현할 때 사용할 수 있는 자료구조