추가 설명 — 균형 이진 탐색 트리는 어떻게 y로 정렬하고 구간을 찾는가

가장 가까운 점 쌍 ③에서 활성 집합을 “y좌표로 정렬 상태를 유지하는 균형 이진 탐색 트리”(C++의 std::set)로 관리했다. 그 트리가 어떻게 y정렬을 저절로 유지하고, $[y-D,\ y+D]$ 구간을 어떻게 빠르게 찾아내는지 안을 들여다본다.

---

세 연산을 모두 빠르게

활성 집합에 필요한 연산은 세 가지였다. 점의 삽입, 점의 삭제, 그리고 y가 특정 구간에 든 점만 뽑는 구간 조회. 이 셋을 한 자료구조에서 모두 빠르게 해야 한다.

익숙한 자료구조로는 왜 안 되는지 보자.

• 정렬 배열. 이진 탐색으로 조회는 $O(\log n)$에 되지만, 삽입·삭제할 때 뒤 원소를 전부 밀어야 해 $O(n)$이다.
• 연결 리스트. 포인터만 바꾸면 되니 삽입·삭제 자체는 $O(1)$이지만, 그 자리를 찾는 탐색이 앞에서부터 훑어 $O(n)$이다.

어느 쪽이든 한 연산이 $O(n)$으로 새고, 점마다 반복하면 다시 $O(n^2)$이다. 이 딜레마를 푸는 것이 이진 탐색 트리(BST) 다. BST에서 삽입·삭제·탐색은 모두 뿌리에서 아래로 한 번 내려가는 일이라, 트리 높이에 비례한다.

문제는 높이다. 삽입 순서가 나쁘면 트리가 한쪽으로 기울어 사실상 연결 리스트가 되고, 높이가 $O(n)$까지 늘어난다. 그래서 높이를 강제로 $O(\log n)$에 묶어 두는 균형 BST가 필요하다. 예컨대 AVL 트리는 모든 노드에서 좌우 서브트리의 높이 차를 1 이내로 유지하는데, 이 규칙만으로 트리 높이가 $O(\log n)$임이 보장된다. 그러면 세 연산이 모두 $O(\log n)$이 된다.

---

y를 키로 두면 트리가 곧 y정렬

BST의 순서 규칙은 단 하나다.

모든 노드에서, 왼쪽 서브트리의 키는 그 노드의 키보다 작고, 오른쪽 서브트리의 키는 크다. 이것이 모든 서브트리에서 재귀적으로 성립한다.

활성 집합에서는 이 키를 점의 y좌표(정확히는 (y, x) 쌍, y를 1순위로)로 둔다. 그러면 순서 규칙에 따라 트리 전체가 y로 정렬된 뼈대가 된다. 트리를 중위 순회(in-order), 즉 왼쪽 서브트리·자기 자신·오른쪽 서브트리 순으로 방문하면 정확히 y 오름차순으로 점들이 나온다.

그래서 ③에서 “트리가 y정렬을 유지한다”고 한 말의 뜻은 이것이다. 매번 정렬을 다시 돌리는 게 아니라, 새 점을 삽입하면 순서 규칙에 따라 제자리에 꽂히고, 점을 삭제해도 규칙이 보존되므로, 트리는 언제나 y정렬 상태를 공짜로 유지한다.

---

구간 [y-D, y+D]는 어떻게 찾나

이제 핵심이다. y정렬된 트리에서, y가 $[\,y_P - D,\ y_P + D\,]$인 점만 어떻게 골라낼까? 두 단계로 나뉜다.

1단계 — 하한 찾기. 구간의 왼쪽 끝, 즉 y가 $y_P - D$ 이상인 첫 노드를 뿌리에서 내려가며 찾는다. 각 노드에서 규칙은 간단하다.

• 현재 노드의 키가 $y_P - D$보다 작으면, 답은 더 오른쪽에 있으니 오른쪽 자식으로 내려간다.
• 크거나 같으면, 이 노드가 하한 후보이니 기억해 두고 왼쪽 자식으로 내려가 더 작은 후보가 있는지 본다.

잎에 닿으면 마지막으로 기억한 후보가 하한이다. 내려간 경로 길이는 트리 높이와 같으므로 $O(\log n)$이다. (C++ std::set의 lower_bound가 정확히 이 일을 한다.)

2단계 — 중위 순서로 훑기. 하한 노드에서 출발해 다음 노드(중위 후속자)를 하나씩 보며, 키가 $y_P + D$를 넘는 순간 멈춘다. 그 사이에 나온 노드가 구간 안의 점 전부다. (upper_bound가 이 멈추는 지점을 가리킨다.)

비용을 더하면, 하한 찾기 $O(\log n)$에 훑은 노드 수 $k$를 더해 $O(\log n + k)$ 다. Plane Sweeping에서는 칸 세기 논거로 이 $k$가 $n$과 무관한 상수이므로, 구간 조회 한 번이 $O(\log n)$에 끝난다.

---

AVL이든 레드-블랙이든

위의 y정렬과 구간 탐색은 오직 BST 순서 규칙 하나에만 기댄다. 균형을 맞추는 방식(AVL은 좌우 높이 차를 1 이내로 잡고, 레드-블랙 트리는 노드에 색을 칠하는 규칙으로 잡는다)은 트리 높이를 $O(\log n)$으로 보장할 뿐, 정렬 순서나 탐색 방식을 바꾸지 않는다.

그래서 균형 BST를 AVL로 이해하든 레드-블랙 트리로 이해하든 이 글의 설명은 그대로 성립한다. C++ std::set도 마찬가지다. 표준이 요구하는 것은 정렬 순회와 로그 시간 연산이지 특정 자료구조가 아니며(구현은 대개 레드-블랙 트리를 쓴다), 아래 논증은 그 두 가지 보장에만 기댄다. ③의 활성 집합이 어느 구현을 쓰든 y정렬·구간 조회는 똑같이 동작한다.

---