Tree

자료구조

트리란?

• 계층적 구조를 표현하는 데 사용되는 자료구조 중 하나.
• 트리는 노드(Node)와 간선(Edge)로 구성된 비선형 자료구조이다.
• 부모 노드(Parent Node) 와 자식 노드(Child Node)의 관계로 이루어져 있다
• 리프 노드(Leaf Node)는 자식이 없는 노드를 의미

1. 트리의 종류

1. 이진 트리(Binary Tree)
   • 각 노드가 최대 두 개의 자식 노드를 가지는 트리
2. 이진 탐색 트리(Binary Search Tree, BST)
   • 이진 트리의 일종으로, 모든 왼쪽 자식 노드는 부모 노드보다 작고, 모든 오른쪽 자식 노드는 부모 노드보다 큰 값을 가짐
3. 힙(Heap)
   • 완전 이진 트리의 한 종류, 최대 힙(Max Heap)과 최소 힙(Min Heap)이 존재
4. 균형 이진 트리 (Balanced Binary Tree)
   • 트리의 높이가 최소화되어 모든 리프 노드가 거의 같은 깊이를 가지는 트리
5. N-진 트리(N-ary Tree)
   • 각 노트가 N개의 자식 노드를 가질 수 있는 트리

2. 트리의 연산

• 삽입(Insertion): 새로운 노드를 트리에 추가하는 연산
• 삭제(Deletion): 기존 노드를 트리에서 제거하는 연산
• 탐색(Search): 특정 값을 가진 노드를 찾는 연산
• 순회(Traversal): 트리의 모든 노드를 특정한 순서로 방문하는 연산

2-1 순회 방법

1. 깊이 우선 탐색 (Depth-First Search, DFS)
   1. 전위 순회 (Pre-order Traversal)
      • 순서 : 루트 → 왼쪽 서브트리 → 오른쪽 서브트리
   2. 중위 순회 (In-order Traversal)
      • 순서 : 왼쪽 서브트리 → 루트 → 오른쪽 서브트리
   3. 후위 순회 (Post-order Traversal)
      • 순서 : 왼쪽 서브트리 → 오른쪽 서브트리 → 루트
2. 넓이 우선 탐색 (Breadth-First Search, BFS)
   1. 레벨 순회 (Level-order Traversal)
      • 노드를 레벨 단위로 방문