이진 검색 트리(Binary Search Tree, priorty queue, set, map)

Balanced BST(균형이 맞춰져 있는 이진 검색 트리)는 c++에서 heap(priorty queue)와 set으로 구현되어 있고, java에서는 tree set, python에서는 set, dict, tree set 등이 있다. 

---

이진 검색 트리(Binary Search Tree, BST)

바이너리 서치가 중앙값보다 작으면 왼쪽 크면 오른쪽으로 이동했으니깐 똑같은 원리로 이루어진 트리

하지만 이진검색트리 만으로는 균형이 잡혀 있지 않기 때문에 최악의 경우 검색, 삽입, 삭제가 O(N)이 걸린다. 

그래서 실제로 BST를 사용하지 않는다.

추가, 삭제, 검색이 O(N)이 걸리기 배열을 사용하겠다,,

//이진 검색 트리는 매우 중요한 알고리즘이지만 BST를 구현하는 문제는 거의 없다.

 

고로 균형이 맞춰져 있는 트리를 사용해야 한다.

 

Balanced BST(균형이 맞춰져 있는 이진 검색 트리)

알고리즘 문제풀이에서 사용하기 위해 균형이 맞춰져 있는 BST를 구현하는 것은 
하나의 알고리즘을 해결하는 것보다 시간이 오래 걸린다.. 

틀릴 수 도 있고 스택이나 큐처럼 간단한 자료구조가 아니다.
//상황에 따라서는 균형과 관련 없이 bst를 구현하는 것도 어려워하는 사람이 많다.

 

 

힙(Heap, Priorty Queue)

힙은 최댓값 또는 최솟값을 찾아내는 연산을 빠르게 하기 위해 고안된 Balanced-BST를 기본으로 한 자료구조이다. C++에서는 우선순위 큐로 STL 구현이 되어 있다. 

 

최대 힙(Max Heap) / 최소 힙(Min Heap)

최대 힙 : 루트가 항상 최댓값

최소 힙 : 루트가 항상 최솟값

 

힙의 연산

#include <queue>	queue에 포함되어 있음
priority_queue<int> pq1;	max heap
priority_queue<int, vector<int>, greater<int>> pq2;	min heap
push(<int>)	요소 삽입(마지막 자리에 추가하고 부모와 자신의 크기를 비교, 시간복잡도 O(logN))
pop()	탑 제거(최댓값 또는 최솟값만 제거 가능)
top()	탑에 접근(최댓값 또는 최솟값)
empty()	비어 있는지 확인
size()	사이즈 반환
emplace(<int>)	Construct and insert element
swap(priority_queue<int>)	큐 자체를 교환

 

최대 힙 제거 : 루트를 제거하고 가장 마지막에 있는 값으로 바꿈.
내려갈 때는 부모가 자식보다 커야 되므로
왼쪽 자식, 오른쪽 자식과 비교해서 가능한 자식으로 이동, 자식과 비교하면서 아래로 내려감

시간복잡도  O(logN)

: 삽입, 제거

최소 힙

최대 힙의 원소에 -1을 곱하여 구현 가능

하지만 힙에 들어갈 수 있는 자료형의 전체 범위 일 때는 사용 불가능 (∵2의 배수 표현)

 

 

세트(Set), 맵(Map)

정리가 잘 되어 있는 블로그가 많아서 첨부.

https://hydroponicglass.tistory.com/171

[C++, STL] 알고리즘 문제풀이를 위한 셋(set)

https://sarah950716.tistory.com/6

[C++/STL]map, set

 

 

 

 

관련 문제풀이

11279 최대 힙 https://www.acmicpc.net/problem/11279
풀이 :

힙 sql 사용, 함수 구현

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

int main(void) {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);

	int n;
	cin >> n;

	priority_queue<int> max_heap;
	for (int i = 0; i < n; ++i) {
		int num;
		cin >> num;
		if (num == 0) {
			if (max_heap.empty())
				cout << "0\n";
			else {
				cout << max_heap.top()<<"\n";
				max_heap.pop();
			}
		}else
			max_heap.push(num);
	}
}

1655 가운데를 말해요 https://www.acmicpc.net/problem/1655
풀이:

가장 쉬운 방법?

-> 정렬하여 풀 경우
O(N^2logN)이 걸림.
->정렬을 링크드 리스트를 사용하여 구현
O(N^2)이 걸림. //시간 초과

첫 풀이 :
왼쪽 그룹, 가운데 수, 오른쪽 그룹으로 나눠서
왼쪽 그룹은 max_heap, 오른쪽 그룹은 min_heap으로 표현 // 정렬되어있는 상태
다음 수가 들어올 경우 가운데 수와 크기 비교 후 왼쪽 또는 오른쪽 그룹으로 이동
이후 크기 비교하여, 왼쪽 == 오른쪽 || 왼쪽 == 오른쪽 +1으로 이동.

풀고 나니 가운데 수가 필요 없는 걸 알게 되었다..
왼쪽 그룹, 오른쪽 그룹,
수가 들어올 경우 왼쪽 또는 오른쪽으로 보내기.
(N/2, N/2) or (N/2 +1, N/2)으로 맞추기.

#include <iostream>
#include <vector>
#include <queue>
#include <functional>
using namespace std;

int main(void) {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);

	int n;
	cin >> n;
	priority_queue<int> left;
	priority_queue<int, vector<int>, greater<int> > right;

	for (int i = 0; i < n; ++i) {
		int num;
		cin >> num;

		int mid;
		if (!left.empty()) mid = left.top();
		else if (!right.empty()) mid = right.top();
		else {
			left.push(num);
			cout << left.top()<<"\n";
			continue;
		}
		if (num <= mid) left.push(num);
		else right.push(num);

		while (!(left.size() == right.size() || left.size() == right.size()+1)) {
			if (left.size() > right.size()+1) {
				right.push(left.top());
				left.pop();
			}
			else {
				left.push(right.top());
				right.pop();
			}
		}
		cout << left.top() << "\n";
	}
	
}