자료구조 - 트리(tree)

본문

• 트리란?
• 트리와 관련 용어

---

트리란?

트리는 이름처럼 나무를 닮으 자료구조다. 나무의 뿌리처럼 한 나무에서서 가지들이 뻗어나와서 분기되는 모습을 보입니다. 이러한 트리 구조는 계층적인 관계를 가진 자료의 표현에서 유용하게 사용됩니다. 트리는 효율적인 탐색을 위해서도 유용합니다. 큐를 효율적으로 구현하기 위해 트리가 사용되기도 합니다.

트리의 모양

---

트리와 관련 용어

트리에서 각각의 요소를 노드라고 합니다. 노드와 노드의 연결 관계는 간선 또는 에지로 나타냅니다. 그리고 노드 중에서 가장 높은 곳에 있는 노드를 루트 노드라고 불립니다.

추가로 노드 관련 용어를 보겠습니다.

• 부모 노드: 간선으로 직접 연결된 상위 노드
• 자식 노드: 간선으로 직접 연결된 하위 노드
• 형제 노드: 같은 부모 노드를 가진 노드
• 조상 노드: 어떤 노드에서 루트 노드까지의 경로상에 있는 모든 노드
• 자손 노드: 어떤 노드 하위에 연결된 모든 노드
• 단말 노드: 자식 노드가 없는 노드, 자식이 있으면 비단말 노드
• 노드의 차수: 노드가 가지고 있는 자식의 수, 단말노드는 항상 0
• 트리의 차수: 트리에 포함된 모든 노드의 차수 중에서 가장 큰 수
• 레벨: 트리에 각 층에 번호를 매기는 것, 루트가 1레벨이고 아래로 내려갈수록 1씩 증가
• 트리의 높이: 트리가 가지고 있는 최대 레벨