Back to Blog
알고리즘BST이진탐색트리setmapmultiset

0x16. 이진 탐색 트리(BST) 구현과 활용

이진 탐색 트리의 개념과 STL set, multiset, map 사용법을 정리한다.

0x16 BST

이진 탐색 트리(Binary Search Tree, BST)는 데이터를 정렬된 상태로 유지하면서 빠르게 삽입, 삭제, 검색할 수 있는 자료구조다. 배열에서 정렬을 유지하려면 삽입/삭제 때마다 O(N)이 드는 반면, BST는 이를 O(log N)으로 처리한다. PS에서는 직접 구현할 일은 거의 없고, C++ STL의 set, multiset, map을 활용하는 것이 핵심이다.

0x00 정의와 성질

BST는 각 노드가 최대 두 개의 자식을 가지는 이진 트리인데, 핵심 규칙이 하나 있다. 왼쪽 서브트리의 모든 값은 현재 노드보다 작고, 오른쪽 서브트리의 모든 값은 현재 노드보다 크다. 이 규칙 덕분에 원소가 항상 크기 순으로 정렬된 상태를 유지한다.

주요 연산의 시간 복잡도는 다음과 같다.

  • insert (삽입): O(log N)
  • erase (삭제): O(log N)
  • find (검색): O(log N)
  • update (수정): O(log N)

트리의 높이에 비례하기 때문에 균형 잡힌 트리라면 모든 연산이 O(log N)에 수행된다.

0x01 기능

BST의 기본 연산은 세 가지로 나뉜다.

검색은 루트에서 시작하여 찾으려는 값이 현재 노드보다 작으면 왼쪽, 크면 오른쪽으로 내려가는 방식이다. 정렬된 배열에서 이분 탐색을 하는 것과 원리가 같다.

삽입도 검색과 비슷하다. 트리를 따라 내려가다가 빈 자리를 찾으면 그곳에 새 노드를 넣는다. BST의 규칙이 자연스럽게 유지된다.

삭제는 조금 복잡하다. 자식이 없는 노드는 그냥 제거하면 되지만, 자식이 하나인 경우 자식을 끌어올려야 하고, 자식이 둘인 경우에는 왼쪽 서브트리의 최댓값 또는 오른쪽 서브트리의 최솟값으로 대체한 뒤 해당 노드를 제거해야 한다.

0x02 자가 균형 트리

일반 BST에는 치명적인 약점이 있다. 이미 정렬된 데이터를 순서대로 삽입하면 트리가 한쪽으로 쏠려서 사실상 연결 리스트가 되어버린다. 이 경우 모든 연산이 O(N)으로 퇴화한다.

이를 해결하기 위해 **자가 균형 트리(Self-Balancing Tree)**가 등장한다. 삽입이나 삭제가 일어날 때마다 트리의 균형을 자동으로 맞춰서, 항상 O(log N)을 보장하는 구조다. 대표적으로 AVL 트리와 **레드-블랙 트리(Red-Black Tree)**가 있다.

C++ STL의 set, map은 내부적으로 레드-블랙 트리로 구현되어 있다. 그래서 직접 균형 트리를 구현할 필요 없이, STL만 잘 활용하면 된다.

0x03 STL

실전에서 BST를 직접 구현할 일은 거의 없다. C++ STL이 제공하는 set, multiset, map이 내부적으로 균형 잡힌 BST를 사용하므로, 이들의 사용법만 잘 익혀두면 충분하다.

set

set은 중복 없이 원소를 정렬된 상태로 저장하는 컨테이너다. 아래 코드에서 주요 연산들의 동작 방식을 확인할 수 있다.

void set_example() {
    set<int> s;
    s.insert(-10); s.insert(100); s.insert(15); // {-10, 15, 100}
    s.insert(-10); // {-10, 15, 100}

    cout << s.erase(100) << '\n'; // {-10, 15}, 1
    cout << s.erase(20) << '\n'; // {-10, 15}, 0

    if (s.find(15) = s.end()) cout << "15 in s\n";
    else cout << "15 not in s\n";

    cout << s.size() << '\n'; // 2
    cout << s.count(50) << '\n'; // 0

    for (auto e : s) cout << e << ' ';
    cout << '\n';

    s.insert(-40); // {-40, -10, 15}

    set<int>::iterator it1 = s.begin(); // {-40(<-it1), -10, 15}
    it1++; // {-40, -10(<-it1), 15}

    auto it2 = prev(it1); // {-40(<-it2), -10, 15}
    it2 = next(it1); // {-40, -10, 15(<-it2)}
    advance(it2, -2); // {-40(<-it2), -10, 15}

    auto it3 = s.lower_bound(-20); // {-40, -10(<-it3), 15}
    auto it4 = s.find(15); // {-40, -10, 15(<-it4)}

    cout << *it1 << '\n'; // -10
    cout << *it2 << '\n'; // -40
    cout << *it3 << '\n'; // -10
    cout << *it4 << '\n'; // 15
}

몇 가지 포인트를 짚어보면, 이미 존재하는 값(-10)을 다시 insert해도 set은 중복을 허용하지 않으므로 무시된다. erase는 삭제한 원소의 개수를 반환하는데, 존재하는 값을 지우면 1, 없는 값을 지우면 0을 반환한다. find는 원소를 찾으면 해당 이터레이터를, 못 찾으면 s.end()를 반환한다.

이터레이터 관련 함수도 중요하다. prev, next는 이전/다음 위치의 이터레이터를 반환하고, lower_bound는 주어진 값 이상인 첫 번째 원소를 가리킨다.

주의할 점은 advance 함수의 시간 복잡도다. set의 이터레이터는 양방향 이터레이터이므로, **한 칸 이동하는 데 O(log N)**이 소요된다. 따라서 advance(it, 100)은 O(log N) * 100만큼의 시간이 든다.

multiset

multiset은 set과 거의 동일하지만, 중복 원소를 허용한다는 점이 다르다. 아래 코드로 차이점을 확인해보자.

void multiset_example() {
    multiset<int> ms;

    ms.insert(-10); ms.insert(100); ms.insert(15);
    // {-10, 15, 100}

    ms.insert(-10); ms.insert(15);
    // {-10, -10, 15, 15, 100}

    cout << ms.size() << '\n'; // 5

    for (auto e : ms) cout << e << ' ';
    cout << '\n';

    cout << ms.erase(15) << '\n'; // {-10, -10, 100}, 2

    ms.erase(ms.find(-10)); // {-10, 100}

    ms.insert(100); // {-10, 100, 100}

    cout << ms.count(100) << '\n'; // 2

    auto it1= ms.begin(); // {-10(<-it1), 100, 100}
    auto it2= ms.upper_bound(100); // {-10, 100, 100} (<-it2)
    auto it3= ms.find(100); // {-10, 100(<-it3), 100}

    cout << *it1 << '\n'; // -10
    cout << (it2= ms.end()) << '\n'; // 1
    cout << *it3 << '\n'; // 100
}

multiset에서 가장 주의할 부분은 삭제 동작이다. ms.erase(15)처럼 값을 직접 전달하면 해당 값의 모든 원소가 삭제된다. 위 코드에서 15가 두 개 있었으므로 2개가 모두 지워지고 반환값은 2다. 만약 하나만 지우고 싶다면 ms.erase(ms.find(-10))처럼 이터레이터를 전달해야 한다. 이 차이를 모르면 실전에서 버그가 발생하기 쉽다.

또한 find 함수로 검색할 때 중복 값이 여러 개 있으면 그 중 아무거나 반환한다는 점도 알아두어야 한다.

map

map은 key-value 쌍을 key 기준으로 정렬하여 저장하는 컨테이너다. key는 중복을 허용하지 않으며, [] 연산자를 통해 직관적으로 접근할 수 있다.

void map_example() {
    map<string, int> m;
    m["hi"] = 123;
    m["bkd"] = 1000;
    m["gogo"] = 165; // ("bkd", 1000), ("gogo", 165), ("hi", 123)

    cout << m.size() << '\n'; // 3

    m["hi"]= -7; // ("bkd", 1000), ("gogo", 165), ("hi", -7)

    if (m.find("hi") = m.end()) cout << "hi in m\n";
    else cout << "hi not in m\n";

    m.erase("bkd"); // ("gogo", 165), ("hi", -7)

    for(auto e : m)
        cout << e.first << ' ' << e.second << '\n';

    auto it1= m.find("gogo");
    cout << it1->first << ' ' << it1->second << '\n'; // gogo 165
}

[] 연산자로 값을 대입하면 해당 key가 없을 때는 새로 추가되고, 이미 있으면 값이 덮어쓰기된다. 위 코드에서 m["hi"]에 처음 123을 넣었다가 나중에 -7로 변경한 것을 볼 수 있다. key 기준으로 자동 정렬되므로, 순회하면 "bkd", "gogo", "hi" 순서로 출력된다. 이터레이터가 가리키는 원소는 pair이므로 first로 key에, second로 value에 접근한다.

1. STL set/map vs unordered_set/unordered_map

  • set/map: 항상 O(log N) 보장 -> 안정적인 성능
  • unordered_set/unordered_map: 평균적으로 더 빠르지만, 해시 충돌로 인해 최악의 경우 O(N) 발생 가능
  • 추천: 특별히 lower_bound, prev, next 같은 연산이 필요하면 set/map, 단순 검색/삽입/삭제면 unordered_set/unordered_map 고려

2. 이진 검색 트리 (STL set/map) 속도 이슈

  • O(log N)이지만 노드 동적할당, 재조정 등의 비용 때문에 느린 로그 복잡도
  • N = 100만일 때 O(N log N) 연산을 수행하면 시간 초과 가능성 있음
  • 만약 TLE 발생 시:
    1. unordered_set/unordered_map으로 변경 -> 그래도 안 되면
    2. 이분 탐색, 정렬, 배열 인덱스 활용 등의 다른 방법 고려

정리하면, 안정성을 원하면 set/map, 속도를 원하면 unordered_set/unordered_map을 선택하되, lower_bound나 이터레이터 순회가 필요한 경우에는 set/map이 필수다. PS에서 TLE가 나면 unordered 버전으로 교체하거나, 아예 다른 접근(이분 탐색, 정렬 등)을 고려하는 것이 좋다.

연습문제

문제 풀이

리뷰

BST 자체를 직접 구현할 일은 PS에서 거의 없지만, 그 위에 얹어진 STL set, multiset, map은 정말 자주 쓰인다. 특히 multiset에서 erase 할 때 값으로 지우면 전부 삭제된다는 점, set의 advance가 한 칸에 O(log N)이라는 점은 실수하기 쉬우므로 기억해둘 필요가 있다.

출처: 바킹독님의 실전알고리즘 강의

PS 시리즈26편