VI. Binary Search Tree & Union Find

• Binary Search Tree
  • STL set, map
• Disjoint Set
  • Naive Approach
  • Using Trees
  • Optimizations
  • Time Complexity
• Additional Topics / Problems
• Programming Practice

Binary Search Tree

Binary Search Tree란, 다음과 같은 성질을 만족하는 트리를 말합니다.

• 이진 트리입니다.

• 항상 왼쪽 서브트리의 값은 자기 자신보다 작고, 오른쪽 서브트리의 값은 자기 자신보다 큽니다.

Binary Search Tree는 우리의 맥락에서 약간 벗어나 있으나 자료구조와 알고리즘 시간에 매우 중요하게 다룹니다. 익혀두는 것을 추천하지만, 우리가 앞으로 쓸 일은 아마도 없을 것입니다. 간단하게만 짚고 넘어가도록 하겠습니다.

(i) 삽입 : 삽입은 기본적으로, 루트에서부터 출발해서, 삽입할 자리를 찾아가는 식으로 합니다. 대소관계에 따라 왼쪽으로 타고 내려갈지, 오른쪽으로 타고 내려갈지를 정한 다음, 내려가야 할 자리가 비었으면 그 자리에 집어넣습니다.

(ii) 삭제 : 삭제는 다음과 같이 수행합니다.

• 삭제할 값 $x$를 트리에서 찾습니다. (삽입에서 찾는 방법과 비슷합니다.)

• 이 노드를, $x$의 오른쪽 서브트리에서 가장 작은 값이 있는 노드와 교환합니다.

• 이제 그 자리에 교환되어 들어간 노드를 삭제합니다.

• 왼쪽 자식 노드가 있다면 그 노드는 가장 작은 겂이 있는 노드가 아니므로 불가능하고, 따라서 노드의 자식이 2개일 수는 없습니다. 자식이 1개라면, 삭제된 노드 자리로 끌어올립니다.

• 자식이 없다면 그냥 넘어가도 됩니다.

결국, 두 연산 모두 검색 연산을 이용하여 이루어집니다.
이제, 시간 복잡도를 생각해 봅시다. 삽입 연산의 경우 검색 연산과 거의 동일하므로, 트리의 높이 $h$에 대해 $O(h)$ 시간이 들게 됩니다. 삭제의 경우, 검색 + 오른쪽 서브트리의 가장 작은 값 찾기의 두 번인데, 둘 모두 사실상 검색과 비슷한 연산이므로 $O(h)$ 시간입니다. 결국 삽입과 삭제 모두 $O(h)$ 시간이 드는 연산입니다. 그런데, 이진 트리의 경우 최악의 상황에서 $h$가 $n$까지 커질 수 있습니다. (한 줄로 쭉 늘어서 있는 경우)
우리는 별로 자세히 다루지는 않겠지만, 이러한 문제를 해결하기 위한 방법을 잠깐만 생각해 봅시다. Quick select때랑 약간 비슷한데, “약간의 시간을 지불해서”, “너무 나쁜 상황이 벌어지지 않게” 만들면 됩니다. 이것을 Balanced Binary Search Tree (BBST) 라고 부르고, 이를 구현하는 다양한 방법이 있습니다. 자세한 내용은 알고리즘 수업에서 다룹니다. 추가 자료를 Additional ii에 일부 제시해 두었습니다.

STL set, map

C++의 라이브러리에는 매우 편한 set 과 map이 있습니다. 이 set과 map은 Balanced Binary Search Tree의 일종인 Red-Black Tree로 구현되어 있기 때문에, BBST를 실제로 구현해서 쓸 일은 보통 없습니다. 이 라이브러리의 사용법을 반드시 익히길 권합니다.
예시 코드 보기 : BOJ 14425 문자열 집합
set, map, multiset, multimap은 활용도가 매우 높습니다. 참고로, priority queue로 할 수 있는 모든 연산은 multiset으로 똑같이 할 수 있고, 시간 복잡도도 $\order{\log n}$으로 같습니다. 그렇다고 해서 두 코드의 수행 시간이 같거나 비슷할 것으로 기대해서는 안 됩니다. 항상, 시간 복잡도는 중요하지만, 그렇다고 해서 전부는 아닙니다.

Disjoint Set

이번 section에서 우리의 목표는, 다음과 같은 두 기능을 갖는 자료구조를 만드는 것입니다.

(i) Union(a, b) : a가 들어 있는 집합과 b가 들어 있는 집합을 합치는 연산.

(ii) Find(x) : x가 들어 있는 집합의 번호를 확인한다. 즉, Find(x) 와 Find(y) 를 통해 두 원소가 같은 집합에 소속되어 있는지 확인하는 작업이 목표.

예를 들어, 1부터 5까지의 숫자가 있다고 할 때, Union(1, 2), Union(3, 4) 를 하고 나면 $\Set{1, 2}, \Set{3, 4}, \Set{5}$ 가 됩니다. 이때 Find(3) 과 Find(4)는 같아야 하고, Find(1)과는 달라야 합니다. 또한, Union(1, 4) 나 Union(2, 3) 등은 모두 $\Set{1, 2, 3, 4}, \Set{5}$ 로 만드는 과정을 수행해야 합니다.

Naive Approach

쉬운 방법으로, Linked List를 사용하는 방법을 예로 들 수 있습니다. $n$개의 숫자가 있고, 이들에 적당히 operation을 수행하려고 한다고 합시다. 각각의 원소가 $p$, $q$개인 집합을 합치는 데 드는 시간은 구현에 따라 다르지만, 효율성을 위해 작은 리스트를 큰 리스트에 합치는 식으로 작업하면 $O(\min(p, q))$ 이지만 이는 최대 $n/2$ 까지이고, 결국 한번의 Union에 $O(n)$이 걸릴 수 있습니다. 또한, Find의 경우 모든 element를 뒤지면서 이 리스트에 소속되어 있는지 찾는 방법밖에 없으므로 $O(n)$이 걸리게 됩니다. 물론, 추가적인 메모리를 쓰면, 매번 각 원소가 자신이 소속된 리스트의 헤드를 가리키는 포인터를 관리하는 등 방법을 쓸 수는 있지만, 이것도 Union은 빨리 할 수 없습니다.

Using Trees

생각을 달리하여, 다음과 같이 생각해 봅시다. 각 집합은 하나의 트리로 나타낼 것이고, 각 원소마다 자신의 부모 노드의 번호만 적어 놓습니다. 즉, 각 원소에 대해 par(x)를 항상 관리한다고 생각하겠습니다. 이때, Find(x)는 약간 생각을 바꿔서, 자신이 소속된 트리의 루트 노드를 찾는 연산이라고 생각합니다. (부모가 없는 루트 노드의 부모는 자기 자신)
그렇다면, Union을 할 때 굳이 모든 노드의 par을 바꿔야 할까요? 트리 A와 트리 B를 합치려고 한다면, A의 루트를 B의 루트 밑에 달아 주기만 하면 (즉, par[root of A] = root of B) 한 번에 트리 A 전체를 트리 B에 달아 놓은 형태가 됩니다. 두 트리 (집합)의 Union이 끝났습니다!
이 방법을 생각해 보면, Union(x, y) 연산의 시간 복잡도는 결국 Find(x)와 Find(y)에 의해 결정됩니다. Find(x)하여, 그 찾은 루트를 Find(y)에 달아 주는 연산이 $\order{1}$이기 때문입니다. 그런데, Find 연산은 그 트리의 높이에 의해 결정되고, 최악의 경우 트리가 루트 밑으로 한 줄로 쭉 달릴 수 있으므로 $O(h) = O(n)$ 입니다. 그러면 별로 빨라진 것이 없습니다.

Optimizations

위와 같은 처참한 상황을 막기 위해, 우리는 크게 세 가지를 생각합니다.

• Union by Rank : 각 트리마다, 항상 트리의 높이¹를 따로 관리합니다. 이때, Union 연산에서 트리를 매달 때, 반드시 높이가 낮은 트리를 높이가 높은 트리에 매달도록 강제합니다. 이렇게 하면, 트리의 높이가 절대 $\log n$ 이상으로 커지지 않음을 보일 수 있습니다. (Additional 3)

• Union by Size : 각 트리마다, 트리의 크기 (노드의 개수) 를 관리하고, 작은 트리를 큰 트리에 붙이도록 강제합니다. 역시 Union by Rank와 마찬가지로, 트리의 높이가 절대 $\log n$ 이상으로 커지지 않음을 보일 수 있습니다. (Additional 4)

• Path Compression : 매번 Find 연산을 하다 보면, $x$가 포함된 트리의 루트를 알게 됩니다. 이때, Heuristic적인 생각으로, 내가 3-4-1-5-2-6의 과정으로 3에서부터 parent를 타고 올라가 6에 도달했다면, 이 트리를 모두 뜯어버리고 3, 4, 1, 5, 2를 전부 6에 그대로 매달아도 됩니다. 이 연산은 트리의 높이를 줄여 줄 것 같습니다.

실제 구현에서 사용하는 방법은 [Union by Rank or Size] + [Path Compression] 입니다. 이하, [Union Rule]과 [Path Comp] 라고 줄이겠습니다.

Time Complexity

Additional 3과 4에서 다룬 바와 같이, [Union Rule] 은 한번 연산에 대략 $\order{\log n}$ 정도가 걸림을 보장합니다. Union Rule 없이 Path Comp 만으로는, 첫 몇번의 Path comp는 별로 효율적이지 못하지만 나중의 case들이 효율적이기 때문에, 상당히 좋은 Bound를 찾을 수 있습니다.² 두 가지를 모두 사용하는, 효율적인 구현의 경우, Find 연산이 평균적으로 대단히 빠르게 수행됩니다. 이때, 이 시간 복잡도를 $\alpha(n)$ 이라는 함수로 씁니다. 이 함수는 Inverse Ackermann 함수라는 것인데, 우리가 상상할 수 있는 대부분의 함수보다 작은 값을 갖습니다. 인간이 가지고 있는 메모리를 모두 합쳐도, 그 안에 들어가는 $n$의 값에 대해 $\alpha(n) < 5$이기 때문에 우리는 이 함수를 사실상 상수라고 생각해도 큰 문제는 없습니다.

Additional Topics / Problems

1. Balanced Binary Search Tree의 예시로, AVL-Tree, Red-Black-Tree, B-Tree와 그 특수한 형태인 2-3-4 Tree가 있습니다. 이 자료구조들은 크게 검색과 검색 기반 연산 (삽입, 삭제, 검색)을 $\order{\log n}$ 에 수행합니다. 그 밖에도, 일반적인 이런 트리로는 절대 수행할 수 없어 보이는 기괴한 연산을 제공하는 자료구조들이 존재합니다.³ 우리는 다루지 않을 예정이고 사실 저도 코딩할 줄 모르지만 ‘루트를 바꾸는 연산’을 Amortized $\order{\log n}$에 해 준다거나 하는... 뭐 그런 것도 있다고 합니다 (?)

2. Union by rank만 사용하였을 때, 트리의 높이가 $O(\log n)$ 이상으로 증가하지 않는다는 사실을 납득하세요. 트리의 높이가 합치려는 트리의 높이 $h_1, h_2$보다 1만큼 증가하기 위해서는, 양쪽의 높이가 같아야 하며, 그러기 위해서는 그 트리의 노드 수는 적어도 $2h_1$개가 되어야 합니다. 귀납법을 통해, 높이가 $h$인 트리가 되려면 $2^h$개 정도의 노드가 필요함을 보이세요.

3. Union by size에 대해서, 위 문제와 같은 내용을 보이세요.

4. 2, 3에서 제시된 아이디어의 핵심을 요약하면, ‘매번 큰 쪽에 작은 쪽을 붙이도록 강제하면, 한번 합치는 연산을 할 때 결과물의 크기는 적어도 작은 쪽의 2배가 된다’ 라는 것입니다. 이 원칙은 당연해 보이지만, Tree DP 등에서 복잡도를 줄이는 핵심적인 트릭 중 하나입니다. 간단한 제약을 통해 $O(n^2)$ 시간 알고리즘을 $O(n \log n)$ 또는 $O(n \log^2 n)$ 으로 줄일 수 있기 때문입니다.

5. Wikipedia에는 Union Rule + Path Comp를 수행할 때, 시간 복잡도가 $O(\log^* n)$ 임을 보이는 증명이 있습니다. $\log^* n$ 이라는 함수는, 대략 $\log \log \log \dots \log n$의 값이 1보다 작아지기 위해 필요한 $\log$의 개수입니다. 이 함수도 당연히 매우 느리게 증가하기 때문에, 실용적으로는 5 이하의 값을 가진다고 가정해도 됩니다. CLRS 책의 chapter 21에는 Inverse ackermann 함수에 관한 증명이 수록되어 있습니다. 관심이 있다면 참고하세요. 우리가 다루기에는 필요 이상으로 복잡하고, 별로 중요하지 않습니다. 다만 두 증명 모두 상당히 Elegant합니다.

6. ($\star$) Union Find을 그래프의 용어로 쓰면, 노드들을 잇는 연산과 두 노드가 서로 연결되어 있는지 묻는 연산이라고 생각할 수 있습니다. 이를 Incremental connectivity라고 부릅니다. 반대로, 간선이 처음에는 연결되어 있고, 삭제되는 경우의 문제를 해결할 수 있을까요? 즉, union-find의 union 대신 disconnect(u, v) 연산을 빠르게 구현할 수 있을까요? 이 문제는 incremental보다 훨씬 어렵습니다. 처음에 연결된 상태가 Tree인 경우, 1981년에 Evan과 Shiloach가 $O(n \log n)$ 알고리즘을, 1997년에 Alstrup 등이 $O(n + m)$ 에 가능함을 보였습니다. Planar graph에 대해서 선형 시간 알고리즘이 제시된 것은 2015년의 일입니다.

7. ($\star\star$) 이제, 두 문제를 합쳐 봅시다. connect와 disconnect연산을 모두 지원할 수 있을까요? 이 문제는 그래프가 모든 상황에서 Forest (서로 연결되지 않은 트리들) 임이 보장되는 경우 $O(n \log n)$ 에, 일반 그래프에서도 쿼리당 poly-logarithmic 시간에 풀 수 있음이 알려져 있습니다.

Programming Practice

1. C++의 STL multiset 등을 사용하여, BOJ 7662번을 해결해 보세요.

2. 처음으로 STL에서 아예 지원하지 않는 자료구조를 구현해 보게 되었습니다. Disjoint set 자료구조를 구현해 보고, 구현체를 BOJ 1717번에 제출해서 확인해 보세요. C++로 구현한 올바른 구현체는 100ms 미만으로 동작합니다. 만약 생각보다 시간이 오래 걸린다면, 다른 사람의 빠른 구현을 참고해서 어떤 부분을 개선할 수 있을지 알아보세요.