[자료구조] 트리란?

이거 정말 쉬운건데 그 몇몇 개념때문에 계속 헷갈린다.

---

📌 트리란?

노드끼리 전부 연결되어 있으면서 사이클이 존재하지 않는 그래프

🔍 트리 용어

이부분이! 정말! 가끔씩 헷갈린다

• 정점(Node): 각 요소
• 간선(Edge): 각 노드를 연결하는 선
• 루트노드: 트리의 맨 꼭데기
• 부모, 자식 노드: 연결된 두 노드 간의 관계
  • 부모 노드: 상대적으로 위에 위치한 노드
  • 자식 노드: 상대적으로 아래에 위치한 노드
• ✨차수: 특정 노드의 자식 수
• 깊이: 루트 노드에서 떨어져있는 정도
• 높이: 전체 트리의 높이. 가장 깊은 노드의 깊이+1 한 값
• ✨리프 노드: 자식 노드가 없는 노드

📌 Rooted Tree, Unrooted Tree?

여기!! ! 내가 대학 새내기 시절 제일 머리 어지러웠던 개념이다. 사실 지금보면 정말 아무렇지 않지만.. 그땐 어려웠다.

🔍 Rooted Tree

루트 노드가 미리 설정되어 있는 트리이다.
다시 등장하지만,

이렇게 생긴 트리를 rooted tree라고 한다.

🔍 Unrooted Tree

그럼 아래와 같이 생긴 그래프도 트리일까?

당연! 이것도 트리다. 사이클이 없고, 노드끼리 전부 연결되어있기 때문이다.
다만 이런 경우에는 루트 노드가 미리 설정되지 않았기에 내가 설정하는게 루트 노드이다.

🙌 참고(unrooted tree의 경우)

• 차수: 노드에 연결된 모든 간선의 개수
• 리프노드: 차수가 1인 노드

🔍 트리가 아닌 경우

그럼 트리가 아닌 경우는 트리의 정의를 반대로 한,

모두 이어져있지 않은 경우

사이클이 존재하는 경우

이 경우를 예시로 들 수 있겠다.
여기서 사이클은 2-1-5 처럼 서로 연결된 경우를 말한다.

---

출처

https://www.codetree.ai/missions/6/problems/tree-introduction/introduction