[Algorithm] 트리 (Tree)

트리 (Tree)

- 계층적 관계를 표현하는 자료 구조

- 단순한 데이터의 저장을 넘어서, 데이터의 표현을 위한 도구

---

트리 용어 정리

트리 예시

노드 (Node)

• 트리의 구성 요소에 해당하는 A, B, C, D, E, F와 같은 요소

 

간선 (Edge)

• 노드와 노드를 연결하는 선

 

루트 노드 (Root Node)

• 트리 구조에서 최상위에 존재하는 노드 (사진에서 A에 해당)

 

단말 노드 (Terminal Node)

• 아래로 다른 노드가 연결되어 있지 않은 노드 (사진에서 C, D, E, F에 해당)

 

내부 노드 (Internal Node)

• 단말 노드를 제외한 모든 노드 (A, B와 같은 노드)

---

트리 노드간 관계

트리 노드 관계 예시

- 노드 A는 노드 B, C, D의 부모 노드(Parent Node)

- 노드 B, C, D는 노드 A의 자식 노드 (Child Node)

- 노드 B, C, D는 부모 노드가 같음, 서로가 서로에게 형제 노드 (Sibling Node)

---

트리의 레벨과 높이

트리의 레벨과 높이

- 트리의 높이 == 레벨의 최대 값

---

 

서브 트리의 이해

서브 트리 예시

- 하나의 트리를 구성하는 왼쪽과 오른쪽의 작은 트리

- 서브 트리 또한 다른 서브 트리로 이루어짐

• 트리는 구조가 재귀적

---

출처

1. https://code-overflow.tistory.com/entry/%EC%9C%A4%EC%84%B1%EC%9A%B0%EC%9D%98-%EC%97%B4%ED%98%88-%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0%ED%8A%B8%EB%A6%ACTree-%ED%8A%B8%EB%A6%AC%EC%9D%98-%EC%9D%B4%ED%95%B4