[STL] Set, Map Custom Sort 구현 방법 (Red-black tree)

Red-Black Tree를 통해 구조화된 자료구조: std::set, std::map

이전 글에서 std::set과 std::map은 Associative Container 중 하나들로, Key 기반으로 데이터(value)에 빠르게 접근할 수 있도록 <key, value> 쌍이 저장된다고 정리하였다. 이때 std::set은 key 자체를 데이터(value)로 보아 key 접근만을 빠르게 하도록 구현된다. std::set과 std::map은 컨테이너 내 데이터 관련 연산(데이터 추가, 읽기, 삭제, 존재 여부 등)을 O(log(N))의 time complexity로 수행가능하도록 구현되었다.

 

이러한 Key 기반 빠른 탐색이 가능하도록 하기 위해 std::set과 std::map은 self-balancing binary search tree (i.e. red-black tree)로 구현되었다[1]. Red-black tree[2](RB tree)는 Key 기반으로 정렬된 Binary search tree의 특수한 형태 중 하나로, 다음과 같은 특성을 만족한다. (Fig 1. 참고)

Tree 내 모든 노드에 대해서, 자신이 가진 자료는 자신보다 오른쪽에 있는 모든 노드의 자료보다 작거나 같고, 왼쪽에 있는 모든 노드의 자료보다 크거나 같다. 

Fig 1. 자료(Key)에 따라 정렬된 Red-black tree 예시 [2]

 

이러한 특성은 데이터 접근을 O(log(N)) 시간만에 가능하도록 한다. 예를 들어 11을 찾고자 하자. 탐색은 항상 root(13)부터 시작한다. root의 값이 13이기에 11은 항상 root(13)의 왼쪽에 있음을 알 수 있다. 다음으로 13의 왼쪽인 8을 탐색한다. 11은 8보다 크기에 11은 항상 8의 오른쪽에 있음을 알 수 있다. 그렇기에 8의 오른쪽인 11을 탐색한다. 단 3번만에 11을 찾을 수 있었다. 

 

std::set과 std::map은 이러한 RB tree의 특성을 이용하여 데이터 <key, value>을 저장한다. 이때 key 값을 기준으로 데이터터가 구조화되어 있기에, key값을 통해서 빠르게 데이터 접근이 가능하다.

 

 

 

자동 정렬되는 데이터 구조: std::set, std::map

std::set과 std::map은 데이터가 추가되든 삭제되든 상관없이 항상 RB tree의 특성을 유지한다. 이를 이용해 자동 정렬되는 데이터 구조로 사용할 수 있다.

 

std::set의 예로 들면 다음과 같다. std::set의 첫 번째 iterator (i.e. std::set::iterator::begin()) 는 항상 가장 왼쪽의 노드를 가리킨다. 이 노드는 모든 노드들의 왼쪽에 있기에, 모든 노드보다 작거나 같다. std::set의 두 번째 iterator가 가리키는 노드는 begin() 다음으로 오는 두 번째로 가장 왼쪽에 있는 노드를 가리키다. 이를 반복하여, std::set의 마지막 iterator는 가장 오른쪽에 오는 노드를 가리킨다.

 

따라서 다음과 같이 std::set의 begin()부터 end()까지 순회하면 크기가 작은 순서대로 데이터에 접근할 수 있다.

std::set<int> int_set;
int_set.insert(20);
int_set.insert(10);
int_set.insert(30);
int_set.insert(40);

for (auto i=int_set.begin(); i!=int_set.end(); i++) {
	printf("%d ", *i);
}
// 결과: 10 20 30 40

 

std::set과 std::map은 default로 std::less 함수 객체를 기준으로 데이터를 구조화한다. 밑은 std::set의 선언부로 Compare 클래스의 default가 std::less<key>로 정의된 것을 확인할 수 있다. std::less 함수 객체는 std::less(x, y)에 대해서 x < y 기능을 수행하는 함수 객체이다. 따라서 x가 y보다 작다면 true, 크거나 같다면 false를 반환하는 함수 객체이다.

// std::set의 정의. Compare 클래스를 기준으로 데이터를 구조화한다.
template<
    class Key,
    class Compare = std::less<Key>,
    class Allocator = std::allocator<Key>
> class set;

// std::map의 정의. Compare 클래스를 기준으로 데이터를 구조화한다.
template<
    class Key,
    class T,
    class Compare = std::less<Key>,
    class Allocator = std::allocator<std::pair<const Key, T>>
> class map;

 

 

 

Custom Sort 구현

std::set과 std::map 변수를 정의할 때 Compare 클래스를 바꿔주기만 하면 원하는 방식으로 정렬시킬 수 있다. 다음은 가장 기본적인 Custom Sort의 예시이다. compare 객체의 operator()를 어떻게 정의하는 지에 따라 std::set에 저장되는 데이터ㅇ의 순서가 바뀐다. 이때 operator(key A, key B)가 true를 반환한다면 A가 B의 앞에 위치한다.

 

// 수학, 과학 점수를 담기 위한 struct
struct score {
    int math;
    int science;
    score(int m, int s) : math(m), science(s) {}
};

// 수학, 과학 점수 평균이 큰 순서대로 정렬하기 위한 함수 객체
struct compare {
	bool operator() (score a, score b) const {
    	// 동작은 하나 에러 발생 가능. 자세한 내용은 밑에 기술함
    	return ((float)(a.math+a.science))/2 > ((float)(b.math+b.science))/2
    }
}

// 수학, 과학 점수 평균이 큰 순서대로 정렬되는 set
std::set<score, compare> scores;

 

std::map 또한 위와 같은 방법으로 custom compare 함수 객체를 정의해주고, 이를 map 변수 선언 시 파라미터로 넘겨주면 된다. 다만 주의할 것은 map의 경우 <key, value>쌍을 저장하는데, 비교 대상이 되는 것은 오로지 key뿐이다.

 

(+) custom sort 개발 시, 자주 실수할 수 있는 부분이 있다. std::set과 std::map은 중복(duplicate) key를 가지는 데이터들을 여러 개 저장할 수 없다. 따라서 위 예시에 나오는 compare는 잘못 정의되었다. 예를 들어

 - score(100, 0) : 수학 100점, 과학 0점인 학생

 - score(0, 100) : 수학 0점, 과학 100점인 학생

이 있다고 하자. 각각을 모두 저장하여야 하는데, 위와 같이 compare 함수 객체를 저장하면 set 입장에서는 score(100, 0)의 평균도 50이고, score(0, 100)의 평균도 50이기에 중복 key로 여긴다. 따라서 set에는 score(100, 0)과 score(0, 100) 중 하나만 저장된다. 따라서 이 경우를 해결하기 위해 score 마다 ID를 부여하는 등의 추가적인 방법이 필요하다.

 

 

 

Reference

[1] https://en.wikipedia.org/wiki/Associative_containers

[2] Red–black tree - Wikipedia