BOJ 2957 - 이진 탐색 트리 (BST)

BOJ 2957 - 이진 탐색 트리 (BST)

[ 분류 - BST ]

  역시 이진 탐색 트리을 포함하여 자료구조 자체를 물어보는 문제는 증명 문제로 이어지는 것이 운명인가보다..

  당연하게도 삽입이 O(N)인 구조이기 때문에 O(N^2)으로 데이터를 확인하는 것은 시간초과로 이어질 수 밖에 없다.

명제) 삽입할 노드를 x라고할 때, 이 x는 직전원소(predecessor) 또는 직후원소(successor) 중 하나의 자식으로 가도록 되어 있다.

증명) 직전원소를 P, 직후원소를 S라고 지칭하자. 아래 상황을 고려해보자.

1. P와 S가 루트의 같은 서브트리에 있는 경우 x가 다른 서브트리에 삽입되려는 경우

   P.key < x < S.key 이기 때문에 반드시 x도 같은 서브트리에 있어야만 성립

2. P와 S가 루트의 다른 서브트리에 있는 경우

   P.key < root.key < S.key 이기 때문에 P 또는 S가 x의 직전 또는 직후원소가 아니게되므로 이런 경우도 없다.

3. P와 S가 같은 서브트리 안에 포함되어 있으며 P와 S 사이에 다른 원소가 있는 경우

   2.와 마찬가지로 사이에 어떤 노드 Y가 있는 경우는 존재할 수 없다.

  따라서 P와 S는 같은 서브트리에 있으면서 사이에 노드가 없어야 하므로, P가 S의 부모(P.right = S) 또는 S가 P의 부모(S.left = P)으로 나타날 수 밖에 없다. 따라서 depth에 대해서 추적해야하는 코드에서는 두 경우 모두 고려하여 depth가 더 큰 노드 자식으로 노드를 추가해주면 된다.

  P와 S는 정렬된 데이터에서 이진탐색을 통해 얻을 수 있으며 이는 곧 C++에서는 map을 쓸 수 있는 환경이 된다.

  또 신경써야할 점은 이 이진 검색 트리는 마지막 노드가 O(N)의 depth를 가질 수 있으므로 답이 N(N+1)/2로 나올 수 있으므로 overflow가 발생할 수 있다.

#include<cstdio>
#include<map>
using namespace std;
int max_v(int a, int b) { return a > b ? a : b; }
int main() {
	int N, D;
	long long acc = 0;
	map<int, int> pool;
	scanf("%d", &N);
	pool.insert({ 0 , -1 });
	pool.insert({ N + 1, -1 });
	while (N--) {
		scanf("%d", &D);
		pool.insert({ D,-1 });
		auto lit = pool.find(D);
		auto rit = lit, it = lit;
		lit--; rit++;
		it->second = max_v(lit->second, rit->second) + 1;
		acc += it->second;
		printf("%lld\n", acc);
	}
	return 0;
}