[자료구조] 트리 개념

트리란?

데이터의 상하관계(계층관계)를 저장하는 자료구조.

데이터에 하나 이상의 데이터들이 단방향으로 연결되어 있다.

이러한 구조가 마치 나무의 모습과 같아서, 트리구조라고 부른다.

비선형 구조이다.

(선형 구조는 배열/리스트와 같이 순서를 갖는 데이터를 갖는다.)

트리 구조

노드를 데이터를 가지고 있는 점으로 보고, 노드 사이를 선으로 연결시킨다.

선으로 연결되어 있는 각 노드를 부모노드/자식노드 라고 부른다.

(위에 있는 노드가 부모노드)

이 중, 가장 최상단에 위치하는 노드를 root 노드라고 부른다.

트리 구조

트리 용어

• 노드 : 그래프에서 각 데이터
• root 노드(뿌리 노드) : 트리 최 상단의 노드. 트리의 시작점. 위의 그림에서 F에 해당한다.
• 부모 노드 : 상하 관계에 있는 데이터들 중에서, 윗쪽에 있는 데이터
• 자식 노드 : 상하 관계에 있는 데이터들 중에서, 아랫쪽에 있는 데이터
  • 예)B는 A와 D의 부모노드. A와 D는 B의 자식 노드.
• 형제 노드 : 수평 관계에 있는 데이터. 부모가 같은 노드.
  • 예)A와 D는 서로 형제 노드
• leaf 노드(잎사귀 노드/말단 노드) : 트리 그래프에서 가장 말단에 있는 노드.(자식을 갖지 않는 노드)
  • 위의 그림에서 A, C, E, H가 잎사귀 노드이다.
• 깊이(depth) : root 노드로 부터 떨어져 있는 거리. 노드간 연결되어있는 간선의 수. 단, root 노드는 깊이가 0
  • 예)A의 깊이는 1, E의 깊이는 3
• 레벨(level) : 같은 깊이에 있는 노드들을 묶어서 말할때 쓰는 용어. 깊이값 + 1 로 표현한다.
  • 예) F의 레벨은 1, A, D, I는 레벨이 3
• 높이(height) : root 노드로부터 트리의 가장 말단에 있는 노드까지의 깊이.
  • 위의 그래프에서는 높이가 3이 된다.
• 부분 트리(sub tree) : 트리를 이루고 있는 트리 내부의 작은 단위의 트리.