[알고리즘] 그림과 문제로 알아보는 이진트리 탐색 (이분 탐색, Binary Search)

 
이진트리에서 가장 중요한 것은 바로 탐색을 효율적으로 할 수 있도록 트리를 구축하는 거야. 물건을 잘 정리해 두면 찾을 수 있는 것과 똑같아. 이진트리는 자식 노드가 최대 2개인 트리를 말해. 그리고 목적에 따라 여러 종류가 있어. 하지만 여기서는 이진탐색트리(binary search tree)를 만들어서 이걸 활용해서 원하는 노드를 효율적으로 찾는 방법을 알아 보도록 하자.
 

1. 이진 트리(Binary Tree)란? 

이진 트리는 각 노드가 최대 두 개의 자식 노드(왼쪽, 오른쪽)를 가질 수 있는 트리 구조야.
쉽게 말해서, 부모 노드가 자식 노드를 0개, 1개, 또는 2개까지만 가질 수 있는 트리야.

위 트리에서 각 노드는 최대 두 개의 자식을 가지고 있어.
이진 트리는 여러 가지로 활용되지만, 탐색을 효율적으로 하기 위해 이진 탐색 트리(Binary Search Tree, BST)로 사용되는 경우가 많아.
 

---

 

2. 이진 탐색(Binary Search)이란? 🔍 

이진 탐색(Binary Search)은 정렬된 배열이나 트리에서 원하는 값을 빠르게 찾는 방법이야
탐색할 때 중간값과 비교하면서 검색 범위를 절반으로 줄이는 방식을 사용해
 

✅ 이진 탐색 과정 (오름차순 정렬된 배열 기준)

• 중간값을 선택한다.
• 찾고자 하는 값이 중간값보다 작으면 왼쪽 절반에서 탐색한다.
• 찾고자 하는 값이 중간값보다 크면 오른쪽 절반에서 탐색한다.
• 위 과정을 반복하면서 원하는 값을 찾거나, 값이 없으면 탐색을 종료한다.

✅ 이진 탐색 예시

정렬된 배열 [1, 3, 5, 7, 9, 11, 13]에서 9를 찾기

• 중간값 = 7 → 9 > 7이므로 오른쪽([9, 11, 13])에서 탐색
• 중간값 = 11 → 9 < 11이므로 왼쪽([9])에서 탐색
• 중간값 = 9 → 찾음
• 시간 복잡도: O(log n) (탐색 범위를 절반씩 줄이므로 빠름!)

 

---

 

3. 이진 탐색 트리(Binary Search Tree, BST)란? 

이진 탐색 트리는 이진 트리의 한 종류로, 이진 탐색의 원리를 적용한 트리야

줄여서 BST 이라고 해.

✅ BST의 특징

• 왼쪽 자식 노드 < 부모 노드 < 오른쪽 자식 노드
• 중복된 값 없음
• 탐색, 삽입, 삭제 연산이 빠름 (O(log n))

• 10의 왼쪽에는 5(작은 값), 오른쪽에는 15(큰 값)
• 5의 왼쪽에는 2(더 작은 값), 오른쪽에는 7(더 큰 값)
• 15의 왼쪽에는 12, 오른쪽에는 20

 

💡 노드가 뭐야?

노드(node)는 트리 구조에서 하나의 요소를 의미해. 쉽게 말해서 데이터를 담고 있는 하나의 상자라고 생각하면 돼.
이진트리에서는 각 노드가 최대 두 개의 자식 노드를 가질 수 있어. 그리고 각각의 노드는 부모 노드와 연결될 수도 있고, 연결되지 않을 수도 있어.

 
■ 노드가 담고 있는 정보들

• 값(value): 노드에 저장된 데이터
• 왼쪽 자식(left child): 현재 노드보다 작은 값을 가진 노드
• 오른쪽 자식(right child): 현재 노드보다 큰 값을 가진 노드
• 부모(parent): 현재 노드를 포함하는 상위 노드 (루트 노드는 부모가 없음)

이진 탐색 트리(Binary Search Tree, BST)에서는 왼쪽 자식은 부모보다 작고, 오른쪽 자식은 부모보다 크다는 규칙이 있어. 이 규칙을 이용하면 빠르게 원하는 값을 찾을 수 있어
 

💡  노드를 잇는 선 = 간선(Edge)

이진 트리에서 노드와 노드를 연결하는 선을 "간선(Edge)"이라고 해. 간선은 트리의 구조를 형성하는 중요한 요소야. 부모 노드와 자식 노드를 연결하는 역할을 하며, 간선의 개수를 보면 트리의 크기를 쉽게 알 수 있어.

 
■ 간선(Edge)의 특징

• 부모 노드와 자식 노드를 연결하는 선
• 노드 개수가 N개라면, 간선 개수는 N-1개
• 루트 노드를 제외한 모든 노드는 반드시 부모 노드를 가지므로, N-1개의 간선이 필요해

 

---

 

4. 순회란?

이진 트리에서 노드를 방문하는 순서를 정의하는 트리 순회(traversal) 방법에 대해 잠깐 알아 보고 가자.
각 순회 방식은 노드의 루트(root)와 자식 노드(left, right)를 방문하는 순서에 따라 구분돼
트리를 순회하는 방법으로 아래 세 가지가 있는데 모두 깊이 우선 탐색(Depth-First Search, DFS)의 일종이야.
DFS는 트리나 그래프에서 한 경로를 끝까지 탐색한 후, 다른 경로로 이동하는 방식의 탐색 방법인데, 트리의 순회 방식은 DFS의 한 형태로 보는 이유는 트리를 한쪽 방향으로 깊이 들어가며 순회하기 때문이야. 
 

• 전위 순회(Preorder Traversal)
• 중위 순회(Inorder Traversal)
• 후위 순회(Postorder Traversal)

다음과 같은 그래프가 있다고 가정해 보자. 

전위 순회

전위 순회에서는 루트 노드를 먼저 방문하고, 그 다음에 왼쪽 자식 노드를 방문한 후 오른쪽 자식 노드를 방문해

[방문순서]
루트 → 왼쪽 → 오른쪽
전위 순회 결과: A → B → D → E → C → F

 

중위 순회

중위 순회에서는 왼쪽 자식 노드를 먼저 방문하고, 그 다음에 루트 노드를 방문한 후 오른쪽 자식 노드를 방문해. 중위 순회는 이진 탐색 트리에서 노드를 오름차순으로 방문하는 순서로도 자주 사용되는 방식이야.

[방문순서]
왼쪽 → 루트 → 오른쪽
중위 순회 결과: D → B → E → A → C → F.

 

후위 순회

후위 순회에서는 왼쪽 자식 노드를 먼저 방문하고, 그 다음에 오른쪽 자식 노드를 방문한 후 루트 노드를 방문해. 후위 순회는 트리의 노드를 삭제할 때, 혹은 자식 노드를 모두 처리한 후 부모 노드를 처리해야 하는 경우에 사용되는 방식이야.

[방문순서]
왼쪽 → 오른쪽 → 루트
후위 순회 결과: D → E → B → F → C → A

 
 

---

 

5. 이진 탐색 트리 구축하기

이진 탐색 트리의 대상 데이터가 3 → 4 → 2 → 8 → 9 → 7 → 1 순서로 들어온다고 가정하고 이진 탐색 트리를 구축하는 원리에 대해서 설명 해 볼게.

 
이진 탐색 트리는 위에서 말한 것처럼 데이터 크기를 따져서 크기가 작으면 왼쪽 자식 위치에, 크기가 크거나 같으면 오른쪽 자식 위치에 배치하는 특성을 가지고 있어. 
 
아래의 그림을 보면 데이터를 전부 삽입 후 정렬하는 것이 아니라 데이터를 하나씩 삽입하면서 이진 탐색 트리를 구축하는 걸 볼 수 있어. 즉, 삽입과 동시에 정렬을 해.

 
1단계
최초의 데이터는 루트 노드가 돼. 3을 이진 탐색 트리에 루트 노드로 추가해. 
 
2단계
현재 삽입하려는 데이터는 4야. 4는 3보다 크니까 오른쪽 자식 위치에 배치해.
 
3단계
현재 삽입하려는 데이터는 2야. 2는 3보다 작으니까 왼쪽 자식 위치에 배치해.
 
4단계 
현재 삽입하려는 데이터는 8이야. 8은 3보다 크니까 오른쪽 자식 위치를 봐야 해. 이미 자식이 있는 경우 값을 비교해. 8은 4보다 크니까 오른쪽 자식 위치를 봐. 4의 오른쪽 자식 위치가 비어 있으니까 이 자리에 8을 배치해. 이런 식으로 이진 탐색 트리를 구축할 때는 넣으려는 대상 데이터의 값이 크거나 같으면 오른쪽 자식으로, 작으면 왼쪽 자식으로 배치해.
 
5단계
9는 3보다 크니까 오른쪽을 봐. 4보다 크고 8보다 크니까 8의 오른쪽 자식 위치에 배치해.
 
6단계
7은 3보다 크고, 4보다 크고, 8보다는 작으니까 8의 왼쪽 자식 위치에 배치해.
 
7단계
1은 3보다 작고, 2보다 작으니 2의 왼쪽 자식 자리에 배치해
 
 

---

 

6. 이진 탐색 트리 탐색하기

이제 이진 탐색트리가 배열보다 좋은 점을 보여줄게. 이진 트리 탐색하는 법은 아래와 같아

1. 찾으려는 값이 현재 노드의 값과 같으면 탐색을 종료하고 크면 오른쪽 노드를 탐색해
2. 찾으려는 값이 현재 노드의 값보다 작으면 왼쪽 노드를 탐색해
3. 값을 찾으면 종료해. 노드가 없을 때까지 계속 탐색했는데 값이 없으면 현재 트리에 값이 없다고 간주해

위와 같은 검색 대상 트리에서 5를 찾아보자.
 
3보다 크기 때문에 우선 오른쪽을 본다. 6보다는 작으니 왼쪽을 본다. 왼쪽에는 아무것도 없다. 이진 탐색 트리의 특징에 따르면 이제 5가 없다는 걸 알기 때문에 이 트리에는 5가 없다는 걸 2번만의 탐색으로 판단가능해.
  
만약 같은 방식으로 배열 탐색을 진행한다면 순차적으로 5를 찾기 때문에 0번 인덱스부터 7번의 비교 연산을 수행해야 해. 그에 반해 이진트리는 2번만 비교 연산을 진행하게 돼. 따라서 배열 탐색보다 이진 탐색 트리의 탐색이 훨씬 빠르다.
 

---

 

7. 이진 탐색 트리 VS 배열 비교

 
지금까지의 설명을 들으면 '이진 탐색 트리에서 탐색하는 것이 배열에서 탐색하는 것보다 효율이 좋은 것 같네!'라고 생각하는 사람이 있을 수 있다. 하지만 두 자료구죠의 삽입과 탐색 시간 복잡도는 이진 탐색 트리의 균형이 맞지 않는다면 최악 의 형우 O(N)이 되어 비슷한 효율을 낸다.
 
이진 탐색 트리의 시간 복잡도는 트리 균형에 의존한다. 트리의 균형이 잡혔다는 건 각 노드의 차수가 비슷하게 유지되면서 각 노드의 자식 노드 수가 비슷하게 유지되는 걸 말한다. 균형이 유지되었다고 가정했을 때 삽입과 탐색 연산 시 이진 탐색 트리에 저장된 노드가 N개라고 하면 시간 복잡도는 O(logN)이다. 하지만 균형이 맞지 않을 때는 시간 복잡도가 배열과 비슷하다. 
 
* 균형이 잡혀 있다는 건 왼쪽과 오른쪽 서브 트리의 높이 차가 1 이하인 경우이다. 그렇지 않을 때는 균형이 잡혀 있지 않다라고 한다. 균형 이진 탐색 트리를 활용하면 이진 트리의 탐색 연산 횟수가 트리 높이에 비례하고 트리의 높이는 logN이므로 탐색 시간 복잡도를 O(logN)으로 유지할 수 있다. 하지만 균형 이진 탐색 트리를 구현하는 건 난이도가 너무 높기 때문에 코테에는 거의 나오지 않는다. 
 

---

 

8. 예시 문제 (트리 순회)

 

📑 8-1. 문제설명

이진 트리를 표현한 리스트 nodes를 인자로 받습니다. 예를 들어서 nodes가 [1, 2, 3, 4, 5, 6, 7]이면 다음과 같은 트리를 표현한 것입니다. 해당 이진 트리에 대하여 전위 순회, 중위 순회, 후위 순회 결과를 반환하는 solution() 함수를 구현하세요
 
제약조건

• 입력 노드값의 개수는 1개 이상 1,000개 이하이다.
• 노드값은 정수형이며, 중복되지 않는다.

입출력 예

nodes	return
[1, 2, 3, 4, 5, 6, 7]	["1 2 3 4 5 6 7", "4 2 5 1 6 3 7", "4 5 2 6 7 3 1"]

 
 

💡 8-2. 풀이 과정 & 정답 코드

문제 그대로 전위, 중위, 후위 순회를 반환하는 문제이다.
 
📌 트리 순회 방식은?

• 전위 순회(Preorder): Root → Left → Right
• 중위 순회(Inorder): Left → Root → Right
• 후위 순회(Postorder): Left → Right → Root

[정답 코드1]

import java.util.*;

class Solution {
    public static List<List<Integer>> solution(int[] nodes) {
        List<Integer> preorderList = new ArrayList<>();
        List<Integer> inorderList = new ArrayList<>();
        List<Integer> postorderList = new ArrayList<>();

        traverse(nodes, 0, preorderList, inorderList, postorderList);

        return Arrays.asList(preorderList, inorderList, postorderList);
    }

    private static void traverse(int[] nodes, int index, 
                                 List<Integer> preorder, 
                                 List<Integer> inorder, 
                                 List<Integer> postorder) {
        if (index >= nodes.length) return;

        preorder.add(nodes[index]);  // 전위 순회 (Preorder): Root → Left → Right
        traverse(nodes, 2 * index + 1, preorder, inorder, postorder); // Left
        inorder.add(nodes[index]);   // 중위 순회 (Inorder): Left → Root → Right
        traverse(nodes, 2 * index + 2, preorder, inorder, postorder); // Right
        postorder.add(nodes[index]); // 후위 순회 (Postorder): Left → Right → Root
    }

    public static void main(String[] args) {
        int[] nodes = {1, 2, 3, 4, 5, 6, 7};
        List<List<Integer>> result = solution(nodes);

        System.out.println("전위 순회: " + result.get(0));
        System.out.println("중위 순회: " + result.get(1));
        System.out.println("후위 순회: " + result.get(2));
    }
}

 
solution 함수 

• preorderList, inorderList, postorderList를 생성하기
• traverse() 함수를 호출하여 트리 탐색
• 결과를 리스트 배열 형태로 반환

traverse() 함수 (재귀함수)

• 현재 노드의 index가 nodes.length를 초과하면 종료
• 전위 순회: 현재 노드를 먼저 리스트에 추가
  왼쪽 자식 방문: 2 * index + 1
• 중위 순회: 왼쪽 탐색 후 현재 노드 추가
  오른쪽 자식 방문: 2 * index + 2
• 후위 순회: 왼쪽과 오른쪽 탐색 후 현재 노드 추가

---

[정답 코드2]

import java.util.*;

class Solution {
    public static List<String> solution(int[] nodes) {
        String pre = preorder(nodes, 0).trim();
        String in = inorder(nodes, 0).trim();
        String post = postorder(nodes, 0).trim();
        return Arrays.asList(pre, in, post);
    }

    private static String preorder(int[] nodes, int idx) {
        if (idx >= nodes.length) return "";
        return nodes[idx] + " " + preorder(nodes, 2 * idx + 1) + preorder(nodes, 2 * idx + 2);
    }

    private static String inorder(int[] nodes, int idx) {
        if (idx >= nodes.length) return "";
        return inorder(nodes, 2 * idx + 1) + nodes[idx] + " " + inorder(nodes, 2 * idx + 2);
    }

    private static String postorder(int[] nodes, int idx) {
        if (idx >= nodes.length) return "";
        return postorder(nodes, 2 * idx + 1) + postorder(nodes, 2 * idx + 2) + nodes[idx] + " ";
    }

    public static void main(String[] args) {
        int[] nodes = {1, 2, 3, 4, 5, 6, 7};
        List<String> result = solution(nodes);

        System.out.println("전위 순회: " + result.get(0));
        System.out.println("중위 순회: " + result.get(1));
        System.out.println("후위 순회: " + result.get(2));
    }
}

 
문제에서 nodes는 노드 리스트를 의미하고 solution() 메서드에서는 리스트와 루트 노드의 인덱스를 preorder(), inorder(), postorder() 메서드에 인수로 전달해서 전위 순회, 중위 순회, 후위 순회 결과를 각각 계산하고 이걸 리스트로 반환한다.
 
각 메서드에서는

• idx가 노드 배열의 길이보다 작을 때만 재귀 호출한다.
• idx가 노드 배열의 길이와 같거나 크면 빈 문자열을 반환한다.
• 반환된 결과 문자열에서는 마지막 공백을 제거한 뒤에 반환한다.

 

---

9. 참고 자료 & 포스팅 작성에 도움을 주신 블로그

1. 궁금한 점은 chatGPT에 물어보면서 작성함 https://chatgpt.com/
2. 김희성. 프로그래머스 제공 97문제로 완벽 대비 코딩 테스트 합격자 되기: 자바 편. 한빛미디어, 2023.
3. [프로그래머스] 길찾기 게임 => 이진 트리와 DFS를 통한 순회 방식 정리 중 트리 순회 부분 발췌
https://velog.io/@sperr/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-%EA%B8%B8%EC%B0%BE%EA%B8%B0-%EA%B2%8C%EC%9E%84-%EC%9D%B4%EC%A7%84-%ED%8A%B8%EB%A6%AC%EC%99%80-DFS%EB%A5%BC-%ED%86%B5%ED%95%9C-%EC%88%9C%ED%9A%8C-%EB%B0%A9%EC%8B%9D-%EC%A0%95%EB%A6%AC