C++로 작성한 레드블랙트리

Red Black Tree란, Binary Search Tree의 일종으로 입력 순서에 따라 BST가 한쪽으로 기울어지는(skewed) 걸 막기 위해 스스로 균형을 맞추는(self-balanced) 트리이다.

트리가 skewed하면 연결리스트랑 다를 바 없어서 \(O(N)\)의 시간복잡도를 갖기 때문이다.
균형을 맞춘다는 것은 어떤 노드의 (자신 아래의) 모든 리프까지의 거리가 최대한 같도록 조정한다는 말인데, 균형을 잘 맞추면 트리의 깊이가 \( \log_{2}{N} \)이기 때문에 빠르게 검색할 수 있다.

레드블랙트리는 아래의 규칙을 만족하도록 조정된다.
1. 노드는 레드 혹은 블랙 중의 하나이다.
2. 루트 노드는 블랙이다.
3. 모든 리프 노드는 블랙이다.
4. 레드 노드의 자식노드 양쪽은 언제나 모두 블랙이다. (즉, 레드 노드는 연달아 나타날 수 없으며, 블랙 노드만이 레드 노드의 부모 노드가 될 수 있다)
5. 어떤 노드로부터 시작되어 리프 노드에 도달하는 모든 경로에는 리프 노드를 제외하면 모두 같은 개수의 블랙 노드가 있다.

이게 뭔소린가 싶지만 (구현하려고) 계속 보다보면 이해가 되고, 뭔가 당연하게 생각된다.

위 규칙을 만족하도록 트리를 회전시키는 작업이 꽤 빈번하게 일어나는게 이게 케이스가 여러개라 골때린다. 책이랑 수업 PPT만 보고 만들어서 적기가 힘든데, 아래 그림​이 도움이 될 거 같다. 

만들 때 참고한 사이트이다. 삽입/삭제 시에 과정을 단계별로 하나씩 볼 수 있어서 디버깅하기 좋다.
https://www.cs.usfca.edu/~galles/visualization/RedBlack.html​​​​​​​​​​​​

같은 숫자도 들어가는 것 같으니 주의.

과제용으로 만든거라 기본 기능만 있다. 입력 테스트하려고 랜덤 입력 생성기를 만들었는데 파이썬2로 작성되어있다 (generator.py)

Github: https://github.com/joonas-yoon/Class-Algorithm/tree/master/Red-Black-Tree​

++

BST를 사용하는 문제로 테스트를 해봤다.

std::set, set::map이 각각 148ms, 132ms가 나왔고 내가 작성한 레드블랙트리가 128~144ms 정도 나왔다. 이 정도면 매우 만족스러운 결과이다.

set으로 제출한 코드: https://www.acmicpc.net/source/15138748
레드블랙트리 코드: https://www.acmicpc.net/source/15139125