Code States | 자료구조(2) - Tree

1. Tree

---

단방향 그래프로, 나무를 거꾸로 뒤집어 놓은 것과 같은 구조를 보인다.
사이클이 없고, 서로 다른 두 노드를 잇는 길이 하나뿐인 그래프이다.

출처: https://ko.wikipedia.org/wiki/%ED%8A%B8%EB%A6%AC_%EA%B5%AC%EC%A1%B0

2. Tree의 구조

---

계층적인 비선형 구조로 사이클이 존재하지 않는다.

• 노드(Node) : 트리의 모든 데이터를 의미하며, 트리 구조를 구성

• 루트(Root) : 트리의 시작 노드 → 2

• 부모 노드(Parent node) : 두 노드가 연결되어 있을 때 상대적으로 루트 노드에서 가까운 노드 → 2, 7, 5, 6, 9

• 자식 노드(Child node) : 두 노드가 연결되어 있을 때 상대적으로 루트 노드에서 먼 노드 → 7, 5, 2, 6, 5, 11 등

• 리프 노드(Leaf node) : 트리 구조의 끝 노드로 자식 노드가 없다. → 2, 5, 11, 4

• 형제 노드(Sibling Node): 같은 레벨 노드

• 깊이 (depth)

  • 루트부터 하위 계층의 특정 노드까지의 깊이

  • 루트 노드는 깊이 0

  • 예) 그림에서 루트 2의 깊이는 0 이며, 7, 5의 깊이는 1이다.

• 레벨(Level)

  • 같은 깊이를 가지는 노드들의 집합

  • 예) 그림에서 5, 11, 4는 모두 같은 레벨 4

• 높이(Height)

  • 리프 노드 기준으로 루트까지의 높이

  • 리프 노드의 높이 0

  • 예) 그림에서 5는 0, 6은 1,7은 2, 2는 3의 높이를 가진다.

• 서브 트리(Sub tree)

  • 전체 트리 내부에 존재하는 트리 구조를 갖춘 트리

  • 예) 7, 2, 6, 9, 4

3. 참고 자료

---

트리 구조