Binary Tree (DFS, BFS) vs. Binary Search Tree

1. Binary Tree (이진 트리)

• 정의: 각 노드가 최대 두 개의 자식 노드를 가질 수 있는 트리 구조
• 특징:
  • 자식 노드의 값에 대한 제약 없음.
  • 트리 구조에서 각 노드는 왼쪽과 오른쪽 자식 노드를 가질 수 있음. → 노드가 있을 수도 없을 수도 있음.
  • 트리의 순서나 정렬에 대한 규칙 없음.

 

 

2. Binary Search Tree (이진 검색 트리)

• 정의: 이진 트리의 일종으로, 왼쪽 서브트리는 해당 노드보다 작은 값들로 구성되고, 오른쪽 서브트리는 해당 노드보다 큰 값들로 구성됨.
• 특징:
  • 왼쪽 자식 노드의 값은 부모 노드보다 작고, 오른쪽 자식 노드의 값은 부모 노드보다 크다!!!
  • 따라서 검색, 삽입, 삭제가 빠르게 이루어질 수 있다. (평균 시간 복잡도: O(log n))
  • 균형이 맞지 않으면 성능이 떨어질 수 있다. 예를 들어 트리가 한쪽으로 치우치면 성능이 O(n)로 최악의 경우가 될 수 있다.

 

차이점

• Binary Tree: 자식 노드 값에 대한 규칙 없음.
• Binary Search Tree: 왼쪽 자식 노드의 값은 부모보다 작고, 오른쪽 자식 노드의 값은 부모보다 큼.

---

1. BFS (Breadth-First Search, 너비 우선 탐색)

• 정의: 트리의 각 레벨을 순차적으로 탐색하는 방식 → 루트에서 시작하여, 같은 레벨에 있는 모든 노드를 탐색한 후, 그 다음 레벨로 넘어간다.
• 작동 방식:
  1. 루트 노드에서 시작하여, 왼쪽에서 오른쪽으로 차례대로 모든 자식 노드를 큐(Queue)에 넣는다.
  2. 큐에서 하나씩 노드를 꺼내면서 그 자식 노드들을 큐에 넣고, 이를 반복한다.
  3. 각 레벨을 차례대로 탐색하며, 한 번에 하나의 레벨씩 탐색한다.
• 특징:
  • 트리의 가장 가까운 노드부터 탐색
  • 큐(Queue)를 이용하여 구현
  • 주로 최단 경로를 찾는 데 유용

2. DFS (Depth-First Search, 깊이 우선 탐색)

• 정의: 가능한 한 깊게 트리를 탐색하는 방식 → 루트에서 시작하여, 각 분기점을 따라가며 끝까지 탐색하고, 더 이상 갈 곳이 없으면 마지막 분기점으로 돌아가서 다른 경로 탐색
• 작동 방식:
  1. 루트 노드에서 시작하여, 왼쪽 자식부터 깊게 탐색한다.
  2. 한 가지 경로를 끝까지 탐색한 후, 되돌아가서 다른 경로를 탐색한다.
• 특징:
  • 트리의 가장 깊은 노드부터 탐색
  • 주로 스택 자료구조나 재귀를 이용하여 구현
  • 순차적으로 깊이 있는 경로를 따라가므로 메모리 사용이 다소 많이 듦.
• DFS의 세 가지 탐색 방법
  1. Pre-order (전위 탐색): 현재 노드 → 왼쪽 서브트리 → 오른쪽 서브트리
  2. In-order (중위 탐색): 왼쪽 서브트리 → 현재 노드 → 오른쪽 서브트리 (BST에서 값이 오름차순으로 정렬되는 특징)
  3. Post-order (후위 탐색): 왼쪽 서브트리 → 오른쪽 서브트리 → 현재 노드

 

차이점

구분	BFS	DFS
탐색 방식	각 레벨을 차례대로 탐색	한 경로를 끝까지 탐색 후, 다른 경로 탐색
사용 자료구조	큐(Queue)	스택(Stack) / 재귀
탐색 순서	1번 레벨 → 2번 레벨 → 3번 레벨…	루트 → 왼쪽 서브트리 → 오른쪽 서브트리
주요 특징	최단 경로 탐색에 유리	깊이 있는 경로를 우선 탐색, 트리의 구조에 따라 달라짐

 

예시

• BFS: 1 → 2 → 3 → 4 → 5 → 6 → 7 (시간 복잡도: O(n))
• DFS: 1 → 2 → 4 → 5 → 3 → 6 → 7 (시간 복잡도: O(n))