[DB] 12. 인덱스 Ⅱ. 트리 탐색 기법

Mar 05, 2025

Contents

1. 순회 방식 (시간복잡도 n)전위 순회(Preorder Traversal) - 루트 → 왼쪽 → 오른쪽 중위 순회(Inorder Traversal) - 왼쪽 → 루트 → 오른쪽 후위 순회(Postorder Traversal) - 왼쪽 → 오른쪽 → 루트 트리 순회 요약 2. 이진 탐색 1️⃣ 50 삽입 (첫 번째 값 → 루트)2️⃣ 30 삽입 (50보다 작으므로 왼쪽)3️⃣ 70 삽입 (50보다 크므로 오른쪽)4️⃣ 20 삽입 (30보다 작으므로 30의 왼쪽)5️⃣ 40 삽입 (30보다 크므로 30의 오른쪽)6️⃣ 60 삽입 (70보다 작으므로 70의 왼쪽)7️⃣ 80 삽입 (70보다 크므로 70의 오른쪽)✅ 완성된 BST 구조:✅ 2. 이진 탐색(Binary Search) 예제 3. 노가다로 BST를 밸런스 있게 만들어보기

❗

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

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

1. 순회 방식 (시간복잡도 n)

전위 순회(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

트리 탐색이 필요하면 구현 코드(Python)도 알려드릴 수 있습니다! 😊

2. 이진 탐색

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. 노가다로 BST를 밸런스 있게 만들어보기

See more posts