자료구조 - Tree, Binary Tree

✅ 트리(Tree) 자료구조

트리(Tree)는 계층적 구조를 표현하는 비선형 자료구조임

• 노드(Node)들이 간선(Edge)으로 연결된 형태로 구성되어 있음
• 최상단 노드를 루트(Root)로 하고, 아래로 계층적으로 뻗어 나감
• 부모-자식 관계가 존재하며, 순환 구조를 가지지 않음 (비순환 그래프)

---

📌 1-1 트리 구조의 특징

https://discuss.boardinfinity.com/t/what-is-a-tree-data-structure/12236

• 루트 노드(Root Node)
  • 트리의 최상단에 위치한 노드
• 부모 노드(Parent Node), 자식 노드(Child Node)
  • 하나의 부모는 여러 개의 자식을 가질 수 있음
  • 하나의 자식은 오직 하나의 부모만을 가질 수 있음
  • 부모에서 자식으로 향하는 단방향 구조를 가짐 (순환 구조 없음)
• 단말 노드(Leaf Node)
  • 자식 노드를 갖지 않는 노드

---

📌 1-2 트리 순회(Tree Traversal)

트리를 일정한 규칙에 따라 노드를 확인(방문)하는 방법으로, 다음의 방식들이 존재함

① 전위 순회 (Pre-order Traversal)

https://builtin.com/software-engineering-perspectives/tree-traversal

방향: Root → 왼쪽 → 오른쪽

• 항상 루트 노드를 가장 먼저 방문함
• 주로 트리 구조를 복제하거나 저장할 때 활용됨

② 중위 순회 (In-order Traversal)

https://builtin.com/software-engineering-perspectives/tree-traversal

방향: 왼쪽 → Root → 오른쪽

• 왼쪽 서브 트리를 먼저 방문한 후 루트, 마지막으로 오른쪽 서브 트리를 방문함
• 주로 이진 탐색 트리(BST)의 노드를 오름차순으로 정렬할 때 활용됨

③ 후위 순회 (Post-order Traversal)

https://builtin.com/software-engineering-perspectives/tree-traversalALT

방향: 왼쪽 → 오른쪽 → Root

• 자식 노드들을 모두 방문한 후 마지막에 부모 노드를 방문함
• 트리의 노드를 삭제하거나 메모리 해제 작업을 수행할 때 주로 활용됨

---

📌 2. 이진 트리(Binary Tree)

각 노드가 최대 두 개의 자식 노드만을 가지는 트리를 이진 트리(Binary Tree)라고 함

• 이진 트리는 가장 널리 사용되는 트리 구조이며, 다양한 응용과 변형 구조의 기반이 됨

---

📌 2-1 이진 트리의 종류

https://medium.com/data-science/5-types-of-binary-tree-with-cool-illustrations-9b335c430254

① 포화 이진 트리 (Full Binary Tree)

• 모든 노드가 0개 또는 정확히 2개의 자식 노드를 가지는 구조
• 모든 레벨(level)에 노드가 가득 차 있어야 함

② 완전 이진 트리 (Complete Binary Tree)

• 모든 레벨이 완전히 채워져 있고, 마지막 레벨은 왼쪽에서부터 연속적으로 채워진 형태의 구조
• 마지막 레벨을 제외하면 모든 레벨은 완전히 채워져 있어야 함

③ 편향 이진 트리 (Skewed / Degenerate Binary Tree)

• 각 노드가 오직 하나의 자식 노드만 갖는 형태의 이진 트리
• 선형적인 구조를 가지고 있어 최악의 경우 연결 리스트(LinkedList)와 유사한 성능을 냄
• 검색 성능이 O(n)으로 떨어져 효율성이 낮아짐

---

해당 게시글은 학습한 내용을 정리하고 복습하며 정리한 글이므로 틀린 부분이 있을 수 있음.