이진 트리(Binary Tree)란?

이진 트리(Binary Tree)란?

• 정의 : 이진 트리란 트리의 종류 중 하나로 모든 노드의 자식 노드가 최대 2개의 노드를 가지는 트리를 의미한다.

---

이진 트리(Binary Tree)의 사용 목적

1. 데이터 정렬
   이진 트리는 데이터를 정렬된 순서로 저장하고 검색하는 데 사용된다
   특히 이진 탐색 트리(Binary Search Tree, BST)라고도 알려진 특정 유형의 이진 트리는 정렬된 데이터를 효율적으로 저장하고 검색하는 데 사용된다.

2. 계층 구조 표현
   이진 트리는 계층 구조를 표현하는 데 사용될 수 있다.
   각 노드는 하위 노드를 가리키는 두 개의 포인터를 가지므로, 트리의 위쪽에 있는 노드는 아래쪽에 있는 노드를 가리키는 방식으로 계층 구조를 나타낼 수 있으며 이러한 특성은 파일 시스템, 조직도, HTML 문서 등과 같은 계층적인 데이터 구조를 표현하는 데 사용될 수 있다.

3. 그래프 알고리즘
   이진 트리는 그래프 알고리즘의 기본 구성 요소로 사용된다.
   이진 트리는 트리의 한 종류로 간주할 수 있으며, 그래프 알고리즘을 이용하여 트리 구조를 분석하고 수정하는 데 사용될 수 있고 깊이 우선 탐색(DFS)이나 너비 우선 탐색(BFS)과 같은 그래프 탐색 알고리즘에서도 이진 트리를 사용할 수 있다.

---

이진 트리(Binary Tree)의 종류

• 이진 탐색 트리(Binary Search Tree, BST):
  • 이진 탐색 트리는 각 노드의 왼쪽 서브트리 값이 현재 노드의 값보다 작고, 오른쪽 서브트리 값이 현재 노드의 값보다 큰 조건을 만족하는 트리
  • 이진 탐색 트리는 데이터를 정렬된 순서로 저장하고 검색하는 데 사용

• 균형 이진 트리(Balanced Binary Tree)
  • 균형 이진 트리는 모든 서브트리의 높이 차이가 1 이하인 이진 트리
  • 이러한 트리는 삽입, 삭제, 검색 작업을 보다 효율적으로 수행할 수 있다
  • 균형 이진 트리의 예로 AVL 트리와 레드-블랙 트리가 있다

• 완전 이진 트리(Complete Binary Tree)
  • 완전 이진 트리는 노드가 왼쪽에서 오른쪽으로 채워지는 형태로 모든 레벨에서 노드가 완전히 채워진 이진 트리
  • 마지막 레벨에서는 노드가 왼쪽부터 차례대로 채워져야 한다

• 힙(Heap)
  • 힙은 완전 이진 트리의 한 종류로, 일반적으로 최댓값 또는 최솟값을 효율적으로 찾기 위해 사용한다
  • 최대 힙(Max Heap)은 부모 노드가 자식 노드보다 크거나 같은 값을 가지는 힙
  • 최소 힙(Min Heap)은 부모 노드가 자식 노드보다 작거나 같은 값을 가지는 힙

이외에도 이진 트리의 종류는 다양하며, 각 종류는 특정한 성질과 용도를 가지고 있다.