알고리즘 문제 해결 전략 2 06장 트리 (3)

22. 이진 검색 트리

22.1 도입

자료들을 일정한 순서에 따라 정렬한 상태로 저장해 둠. 검색 트리는 이 점을 이용해 원소의 추가와 삭제만이 아니라 특정 원소의 존재 여부 확인 등의 다양한 연산을 빠르게 할 수 있음. 검색 트리 중 가장 흔하게 사용되는 것이 바로 이 장에서 소개할 이진 검색트리와 그 변종들임. 이진 검색 트리들은 아주 널리 사용됨. 

 

22.2 이진 검색 트리의 정의와 조작

정의

이진 트리란 각 노드가 왼쪽과 오른쪽, 최대 두 개의 자식 노드만을 가질 수 있는 트리를 의미함. 이진 검색트리에서 원하는 값을 찾는 과정은 배열에서의 이진 탐색과 비슷함. 

순회

이진 검색 트리를 중위 순회하면 크기 순서로 정렬된 원소의 목록을 얻을 수 있음. 

자료의 검색

한 번 원소를 비교하는 것 만으로도 찾아야 할 전체 대상의 절반을 줄일 수 있으므로, 이진 탐색과 비슷한 속도로 자료를 찾을 수 있게 됨.

조작

이진 검색 트리가 진가를 드러내는 곳은 집합에 원소를 추가하거나 삭제하는 조작 연산을 해야 할 때 입니다. 이진 검색 트리에는 선형적인 구조의 제약이 없기 때문에, 새 원소가 들어갈 위치를 찾고 거기에 노드를 추가하기만 하면 간단히 새 원소를 추가할 수 있음. 이진 검색 트리에서 가장 까다로운 연산은 집합에서 원소를 삭제하는 것임. 

a의 왼쪽 서브트리에 있는 원소들은 모두 a의 원소보다 작고, a의 오른쪽 서브트리와 B에 있는 원소들은 모두 a의 원소보다 큼. 따라서 오른쪽 서브트리와 B를 재귀적으로 합친 뒤 a의 오른쪽 자식으로 두면 합치기 연산은 완료됨.

 

X보다 작으 원소의 수 찾기/k번재 원소 찾기

직접 구현해야 함. 라이브러리 제공하는 언어 몇 없음.

 

22.3 시간 복잡도 분석과 균형 잡힌 이진 검색 트리

자료의 개수 N에 대해 트리의 높이 h는 어떻게 변할까요?

우리가 원하는 이상적인 케이스는 가급적 가로로 넓게 퍼지고 '평평한' 트리임. 

균형 잡힌 이진 트리(balanced binary search tree)가 있음. 트리의 구조에 추가적인 제약을 정하고 이 제약이 만족되도록 노드들을 옮겨서 트리의 높이가 항상 O(lgN)이 되도록 유지함. 대부분의 표준 라이브러리에서 제공하는 이진 검색 트리의 구현도 내부적으로는 대개 레드-블랙 트리를 사용함. 

 

22.4 문제:너드인가, 너드가 아닌가? 2

조직위는 너드일 가능성이 있는 사람만 대회에 받아주기로 함. 각 사람이 참가 신청을 할 때마다 참가 가능자의 수는 1, 2, 2, 3으로 변함. 입력 N줄에 각 2개의 정수로 각 사람의 문제 수와 라면 그릇 수가 참가 신청한 순서대로 주어짐. 두 사람의 문제 수나 라면 그릇 수가 같은 경우는 없다고 가정해도 좋음. 

 

22.5 풀이:너드인가, 너드가 아닌가? 2

이 문제는 새 점이 하나 추가될 때마다 다른 점에 지배당하지 않는 점, 즉 O들의 수를 계산하는 것으로 바뀜. 평면에 새 점이 하나 찍힐 때마다 기존 점들 중에서 이 점을 지배하는 점이 있는지 우선 확인함. 다른 점에 지배되는 점들은 지워 버려도 좋다는 데 유의함. 이때 지배되는 않은 점드르이 정보를 저장하는 한 가지 간단한 방법은 이들을 그냥 배열에 저장하는 것임. 지배당하지 않는 점들만 모아서 x좌표가 증가하는 순서대로 정렬해 보면 y좌표는 항상 감소하게 됨. 
바로 오른쪽에 있는 점을 찾는 연산, 점의 추가와 삭제 등을 모두 빠르게 할 수 있는 자료구조. map<int, int>::lower-bound(x)는 트리에 포함된 x 이상의 키 중 가장 작은 값을 돌려줌.

 

map<int, int> coords;
bool isDominated(int x, int y) {
	map<int, int>::iterator it = coords.lower_bound(x);
	if (it == coords.end()) return false;
	return y < it->second;
}

void removeDominate(int x, int y) {
	map<int, int>::iterator it = coords.lower_bound(x);
	if (it == coords.begin()) return;
	--it;
	while (true) {
		if (it->second > y) break;
		if (it == coords.begin()) {
			coords.erase(it);
		}
		else {
			map<int, int>::iterator jt = it;
			--jt;
			coords.erase(it);
			it = jt;
		}
	}
}

int registered(int x, int y) {
	if (isDominated(x, y)) return coords.size();
	removeDominated(x, y);
	coords[x] = y;
	return coords.size();
}

registred()를 N번 호출한다고 하면 전체 시간 복잡도는 얼마가 될까요? isDominated()의 시간 복잡도는 이진 검색 트리에서의 탐색이 지배하기 때문에 O(lgN)이지만, removeDominated()에서는 몇 개의 점이 없어지느냐에 따라 수행 시간이 달라지기 때문에 전체 수행 시간을 짐작하기 어려움. 그러나 removeDomintaed()에서 한 점은 최대 한 번만 지워질 수 있기 때문에 지워지는 점의 개수는 다 합해봐야 N-1임. 따라서 전체 시간 복잡도는 O(NlgN)이 됨.