[자료구조] 트리란?

트리란

• 트리는 계층적인 구조를 표현할 때 사용할 수 있는 자료구조
• cycle을 가지지 않는 그래프

 

트리 관련 용어

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

 

이런 형태도 트리일까?

 

이 형태는 cycle이 발생하기 때문에 트리가 아니다.

기본적으로 트리의 크기가 N일 때, 전체 간선의 개수는 N-1 이유는 cycle이 생기지 않기 때문이다.

cycle이란?

• 특정 노드에서 시작하여 다시 특정 노드로 돌아오는 경로
• 예) 위 그림으론 A → B → E → A로 가는 cycle이 발생하여 트리가 아니다.
• 저 자료구조는 그래프라는 자료구조이다.

트리 종류

• 이진트리
  • 많아야 두 개의 자식 노드를 갖음
  • 왼쪽 자식과 오른쪽 자식으로 구분
• 완전 이진트리
  • 자식 노드가 왼쪽부터 순서적으로 채워진 이진트리 높이가 균형을 유지
• 포화이진트리
  • 각 레밸에서 자식 노드가 모두 채워진 이진트리
  • 높이가 균형을 유지
    • 트리는 계층적인 구조를 표현할 때 사용할 수 있는 자료구조