[데이터베이스] 13. 트리 탐색 기법

1. 순회 방식

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

트리 순회 요약

2. 이진 탐색

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

  50

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

    50
   /
  30

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

    50
   /  \
  30   70

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

    50
   /  \
  30   70
 /
20

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

    50
   /  \
  30   70
 /  \
20   40

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

    50
   /  \
  30   70
 /  \   /
20   40 60

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

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

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

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

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

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

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

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

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

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

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

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

3. 직접 이진 탐색

4. 자바로 구현

1. 배열 사용

package algo;


import java.util.Arrays;

// 이진 탐색 : 배열
public class BSearch02 {
    public static void main(String[] args) {
        // 1. 삽입 (무작위)
        // int[] arr = {10, 4, 1, 2, 3, 0, 11};
        int[] arr = {8, 1, 2, 3, 4, 5, 6, 7, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20};

        // 2. 정렬
        Arrays.sort(arr); // 0, 1, 2, 3, 4, 10, 11

        // 3. Start
        int target = 0;
        int mid = arr.length / 2; // mid_index = arr.length / 2
        int s = 0;
        // int e = arr.length - 1;
        int count = 0;

        while (true) {
            // Error 검출 : IndexOutOfBounds >> 에러 메시지 출력 후 break
            if (mid < 0 || mid >= arr.length) {
                System.out.println("Could not find the Target : Target not in bound");
                break;
            }
            // Found : 메시지 출력 후 break
            else if (target == arr[mid]) {
                System.out.println("Found the Target : " + arr[mid]);
                count++;
                System.out.println("탐색 횟수 : " + count);
                break;
            }
            // Target이 기준값보다 작을 때 : index를 낮춤
            else if (target < arr[mid]) {
                System.out.println("Target is smaller than " + arr[mid]);
                s = mid;
                // 무한 루프 방지 : index를 계속 나누어도 0에서 머물므로, index가 0이면 -1로 변경
                if (s == 0) mid = -1;
                else mid = s / 2;
                count++;
                System.out.println("탐색 횟수 : " + count);
            }
            // Target이 기준값보다 클 때 : index를 높힘
            else if (target > arr[mid]) {
                System.out.println("Target is bigger than " + arr[mid]);
                s = mid;
                // 무한 루프 방지 : index를 계속 더해도 arr.length - 1까지만 증가하므로 index가 arr.length - 1이면 s + 1 (= arr.length)
                if (s == arr.length - 1) mid = s + 1;
                else mid = s + ((arr.length - s) / 2);
                count++;
                System.out.println("탐색 횟수 : " + count);
            }
        }
    }
}

2. 클래스 (=LinkedList) 사용

package algo;


import java.util.Arrays;

// 이진 탐색 : Linked List

// Node 생성
class Node {
    private int value;
    private Node left;
    private Node right;

    public Node(int value) {
        this.value = value;
    }

    public int getValue() {
        return value;
    }

    public Node getLeft() {
        return left;
    }

    public Node getRight() {
        return right;
    }

    public void setLeft(Node left) {
        this.left = left;
        System.out.println("Node set left");
    }

    public void setRight(Node right) {
        this.right = right;
        System.out.println("Node set right");
    }

    public void insert(Node node) {
        if (node.value < value) {
            if (left == null) {
                this.left = node;
                System.out.println("Left node inserted");
            } else left.insert(node);
        } else if (node.value > value) {
            if (right == null) {
                this.right = node;
                System.out.println("Right node inserted");
            } else right.insert(node);
        } else System.out.println("Not enough space");
    }
}

public class BSearch03 {
    public static void main(String[] args) {

        // 1. 삽입
        int[] arr = {50, 30, 70, 20, 40, 60, 80, 10, 25, 35, 45, 55, 65, 75, 85};

        // 2. 등록
        Node root = new Node(arr[0]);

        for (int i = 1; i < arr.length; i++) {
            root.insert(new Node(arr[i]));
        }

        // pop : 출력
        pop(root);
    }

    static void pop(Node node) {
        if (node != null) {
            System.out.print(node.getValue() + ", ");
            pop(node.getLeft());
            pop(node.getRight());
        }
    }
}