[0x16] 이진 검색 트리

트리의 정의

 

정점(=노드) : 각각의 원소

루트 : 가장 꼭대기에 있는 정점

리프 : 자식이 없는 정점

간선 : 정점끼리 연결하는 선

서브트리 : 어떤 한 정점에 대해 그 밑에 있는 정점과 간선만을 모은 트리

이진트리 : 각 노드의 자식이 2개 이하인 트리

 

이진 검색 트리

 

왼쪽 서브트리의 모든 값은 부모의 값보다 작고, 오른쪽 서브트리의 모든 값은 부모의 값보다 큰 이진 트리

이진 검색 트리를 이용하면 insert, erase, find, update 모두 O(logN)에 처리할 수 있다.

 

이진 검색 트리를 사용해야 하는 문제가 있다면 map/set을 사용하면 된다.

보통 unordered_map/set이 조금더 빠르지만 해시충돌이 빈번하게 일어난다면 얘기가 달라지므로 언제나 O(logN)을 보장해주는 map/set을 이용하는게 낫다.

하지만 O(logN)중에서도 느린편이다.

 

 

코딩 테스트에서 STL을 사용하지 못하는 경우 이진 검색 트리로 풀 수 있을것 같은 문제라 하더라도 해시나 이분 탐색과 같은 다른 방법을 이용하는 풀이를 고민해야 한다.

 

연습 문제

 

7662: 이중 우선순위 큐

#include <bits/stdc++.h>
using namespace std;

int main(void)
{
	int tc;
	cin >> tc;
	while (tc--)
	{
		multiset<int> h;
		int k;
		cin >> k;
		while (k--)
		{
			char a;
			int b;
			cin >> a >> b;
			if (a == 'I')
				h.insert(b);
			else
			{
				if (h.empty()) continue;
				if (b == 1)	h.erase(prev(h.end()));
				else h.erase(h.begin());
			}
		}
		if (!h.empty()) cout << *h.rbegin() << ' ' << *h.begin();
		else cout << "EMPTY";
		cout << '\n';
	}
}

 

삭제할 때 prev(h.end())가 아니라 h.rbegin()을 넣어봤더니 reverse_iterator는 erase 할 수 없었다.

iterator로 변환해주는 base()를 쓰게되면 해당 iterator 그대로 변환되는게 아니라 이전 iterator가 반환된다.

또한 iterator가 아닌 참조한 값을 지우게 되면 중복값이 싸그리 지워지기 때문에 이 문제에서는 적합하지 않다.

 

1202: 보석 도둑

아직 내가 쉽게 이해할만한 문제가 아니라 패스함

 

기본 문제

 

21939: 문제 추천 시스템 Version 1

#include <bits/stdc++.h>
using namespace std;

int n, m;
map<int, set<int>> h;

int main(void)
{
	cin >> n;
	while (n--)
	{
		int a, b;
		cin >> a >> b;
		h[b].insert(a);
	}

	cin >> m;
	while (m--)
	{
		string s;
		cin >> s;
		if (s == "recommend")
		{
			int a;
			cin >> a;
			if (a == 1)	cout << *(prev(h.end())->second.rbegin()) << '\n';
			else cout << *h.begin()->second.begin() << '\n';
		}
		else if (s == "add")
		{
			int p, l;
			cin >> p >> l;
			h[l].insert(p);
		}
		else
		{
			int a;
			cin >> a;
			for (auto& it : h)
			{
				if (it.second.find(a) != it.second.end())
				{
					it.second.erase(a);
					if (it.second.empty()) h.erase(it.first);
					break;
				}
			}
		}
	}
}

 

map에 set을 쳐박아놔서 find->remove를 수행할 때 이점을 다 날려버리고 선형탐색을 시도해서 시간이 오래걸린다.

정답 코드는 set과 배열 두개를 사용해서 따로 관리하는 방법을 썼음

 

23326: 홍익 투어리스트

#include <bits/stdc++.h>
using namespace std;

int n, q;
set<int> p;

int main(void)
{
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);

	cin >> n >> q;
	for (int i = 1; i <= n; ++i)
	{
		int a;
		cin >> a;
		if (a) p.insert(i);
	}

	int cur = 1;
	while (q--)
	{
		int a;
		cin >> a;
		if (a == 1)
		{
			cin >> a;
			if (p.find(a) != p.end()) p.erase(a);
			else p.insert(a);
		}
		else if (a == 2)
		{
			cin >> a;
			cur = (cur + a - 1) % n + 1;
		}
		else
		{
			if (p.empty()) cout << -1 << '\n';
			else
			{
				auto it = p.lower_bound(cur);
				if (*it >= cur) cout << *it - cur << '\n';
				else cout << n - cur + *p.begin() << '\n';
			}
		}
	}
}

 

입출력 버퍼 부분 쥐도새도 모르게 지워져서 계속 시간초과 뜨길래 뇌정지옴

해답코드랑 비교해보니 쿼리가 2일때 cur값 주는 부분만 조건식을 썼냐 안썼냐 차이였음