[DB] 12.2. 트리 탐색 기법

김주희

Mar 10, 2025

Contents

1. 순회 방식 2. 이진 탐색 ✅ 2. 이진 탐색(Binary Search) 예제 3. 수기로 해보는 이진 탐색 트리 삽입 및 탐색

❗

순회 방식 : 전위,중위,후위

이진탐색 : 왼쪽, 오른쪽 (크기 비교)

1. 순회 방식

❗

Full Scan

전위 순회(Preorder Traversal) - 루트 → 왼쪽 → 오른쪽

루트를 먼저 방문한 후, 왼쪽 서브트리, 오른쪽 서브트리 순으로 방문합니다.

순서: Root → Left → Right

예제:


     A
    / \
   B   C
  / \   \
 D   E   F

전위 순회 결과: A → B → D → E → C → F

중위 순회(Inorder Traversal) - 왼쪽 → 루트 → 오른쪽

왼쪽 서브트리를 먼저 방문한 후, 루트를 방문하고, 오른쪽 서브트리를 방문합니다.

순서: Left → Root → Right

예제:


     A
    / \
   B   C
  / \   \
 D   E   F

중위 순회 결과: D → B → E → A → C → F

후위 순회(Postorder Traversal) - 왼쪽 → 오른쪽 → 루트

왼쪽 서브트리를 먼저 방문한 후, 오른쪽 서브트리를 방문하고, 마지막에 루트를 방문합니다.

순서: Left → Right → Root

예제:


     A
    / \
   B   C
  / \   \
 D   E   F

후위 순회 결과: D → E → B → F → C → A

트리 순회 요약

순회 방식	방문 순서
전위 순회	Root → Left → Right
중위 순회	Left → Root → Right
후위 순회	Left → Right → Root

2. 이진 탐색

❗

삽입 먼저 손으로 그려서 이해 : 2의 배수 (10개) (20개) (30개) → binary로 넣기o 무작위X

50, 30, 70, 20, 40, 60, 80 순서대로 삽입하겠습니다.

1️⃣ 50 삽입 (첫 번째 값 → 루트)

2️⃣ 30 삽입 (50보다 작으므로 왼쪽)


    50
   /
  30

3️⃣ 70 삽입 (50보다 크므로 오른쪽)


    50
   /  \
  30   70

4️⃣ 20 삽입 (30보다 작으므로 30의 왼쪽)

5️⃣ 40 삽입 (30보다 크므로 30의 오른쪽)

6️⃣ 60 삽입 (70보다 작으므로 70의 왼쪽)

7️⃣ 80 삽입 (70보다 크므로 70의 오른쪽)


     50
   /    \
  30     70
 /  \   /   \
20   40 60   80

✅ 완성된 BST 구조:

이제, 이진 탐색(Binary Search) 을 이용해서 특정 값을 찾아보겠습니다.

✅ 2. 이진 탐색(Binary Search) 예제

이진 탐색은 정렬된 데이터에서 반씩 나누며 값을 찾는 알고리즘입니다.

BST에서는 왼쪽(작은 값), 오른쪽(큰 값)으로 이동하며 탐색합니다.

🔍 예제 1: 값 40을 찾는 과정

루트(50)와 비교 → 40은 50보다 작음 → 왼쪽 이동 (30)

30과 비교 → 40은 30보다 큼 → 오른쪽 이동 (40)

40과 비교 → 값이 일치! 탐색 성공 ✅

🔍 예제 2: 값 25를 찾는 과정

루트(50)와 비교 → 25는 50보다 작음 → 왼쪽 이동 (30)

30과 비교 → 25는 30보다 작음 → 왼쪽 이동 (20)

20과 비교 → 25는 20보다 큼 → 오른쪽 이동 (노드 없음)

더 이상 이동할 곳이 없음 → 탐색 실패 ❌

3. 수기로 해보는 이진 탐색 트리 삽입 및 탐색

Database