• 자가 균형 트리가 구현되지 않은 이진 트리는 시간 복잡도가 좋지 않아 시간 초과가 발생할 수 있다.

트리란?

• 계층 구조를 가지고 있고 루트를 제외하고 상위 노드와의 연결이 딱 하나로 이루어져 있다.

트리 이미지

• 정점과 정점을 연결 시켜주는 것을 간선이라 하며, 간선으로 연결된 상, 하 관계를 부모 / 자식 관계라 한다.
• 어떤 정점에 대해 그 밑의 간선과 노드들로 이루어진 트리를 서브 트리라 한다.
• 이진 트리 → 각 노드의 자식이 2개 이하인 트리

이진 트리의 장점)

• insert, erase, find, update → O(lg N) 에 처리가 가능
• 원소가 크기 순으로 정렬되어 있음

SET

MAP

• key 와 value 대응 관계 일 때 사용하면 좋음

<aside> 🔥 unordered_set과 unordered_map 은 속도는 빠를지언정 충돌이 얼마나 빈번한가에 따라서 속도 저하가 발생하기에 set과 map을 사용하는 것이 좋다.

이분탐색이나 정렬보다는 좀 더 느린 O(lgN)의 시간 복잡도를 가진다.

</aside>

이진 검색 트리 연습 문제

BOJ 7662 : 이중 우선순위 큐

#include <bits/stdc++.h>

using namesapce std;

int main(){
	int t;
	cin >> t;
	while(t--){
		int k;
		cin >> k;
		multiset<int> ms;
		while(k--){
			char com;
			cin >> com;
			if(com == 'D'){
				int q;
				cin >> q;
				if(ms.empty()) continue;
				if(q == l) ms.erase(prev(ms.end()));
				else ms.erase(ms.begin());
			}
			else{
				int q;
				cin >> q;
				ms.insert(q);
			}
		}
		if(ms.empty()) cout << "EMPTY\\n";
		else{
			cout << *prev(ms.end()) << ' ' << * ms.begin() << '\\n';
		}
	}