악어떼가 나온다 악어떼

악어때를 만나기 전, 우리는 나름의 준비를 해야한다.
우리의 무기는 C.

가장 흔하게 잘 쓰이는 RB-tree를 C에서 구현하면서,
포인터 / 구조체 개념을 익히고, 디버깅 방법, make파일 작성 및 실행 등을 익혔다.

why RB-tree

RB-tree 는 이미 포스팅 했지만, 주로 RB-tree의 기본 개념과 구현 문제에 관한 이슈들을 정리해놓았을 뿐이다. 이번 주차 티타임에서 (참석하진 않았지만) 들려오는 말들에 의하면 RB-tree의 구현 자체는 중요한 사항이 아닌듯 싶다. 설명서를 보고 물건을 조립하듯 구현 자체는 재밌긴 했으나, 여태까지 경험한 바에 의하면 크게 기억에 남지 않고 '이런거 해봤다' 하는 자신감 이상의 의미가 없을 것같다.

그래서 RED-BLACK tree 왜 쓰느냐. 어디서 쓰느냐.

뒤 늦게 정리해보자면 이렇다.

왜

'왜 쓰느냐'는 RB-tree의 등장 배경과, 다른 균형 이진 트리와의 차이점에서 찾을 수 있을 것이다.

1. 균형을 이루는 검색 트리의 시작은 AVL(Adel'son-Vel'ski, Landis)트리였다. 트리 내의 어떤 노드의 왼쪽 서브트리와 오른쪽 서브트리의 높이차가 1이하가 되게 유지함으로써 균형을 잡는다.

2. 그 다음은 2-3 트리 와 B-트리가 등장했다.
   2-3 트리는 각 노드가 (자식이 있는 경우) 2개의 자식과 1개의 데이터를 가지거나, 3개의 자식과 2개의 데이터를 가지는 트리인데 이것을 일반화 한 것이 B-트리. M차 B-트리는 하나의 노드가 최대 M개의 자식을 가질 수 있는 트리를 의미한다.

3. 이후에 '4차 B-트리'의 조금 특별한 버전인 "대칭 이진 B-트리"(2-3-4 트리)가 개발되고,
   이러한 '대칭 이진 B-tree'의 개념을 가지고, RB-tree가 탄생하게 되었다.
   여담으로 노드의 색깔이 RED와 BLACK인 이유는 빨간색이 당시 개발이 이루어졌던 팔로알토 연구소의 프린터기가 인쇄할 수 있는 가장 선명한 색이었기 때문이라고 한다.

그렇담 AVL-tree와 RB-tree의 차이점은 뭘까

AVL 이 RB보다 균형 기준이 엄격
( 균형인수의 차이가 2만 나도 즉 좌우 높이차가 2만 나도 재조정)
- 거의 모든 경우에 조회를 logn에 할 수 있음
- 단 균형 조정이 엄격해서, 조정할 일이 많을 것이고 그에 따라 삽입과 삭제가 비용이 많이 듦

RB는 AVL보다 균형이 덜 엄격
(루트에서 리프까지 가는 모든 경로의 흑색노드의 수만 같으면 됨)
- 균형이 많이 깨진 경우엔 조회가 logn보다 많이 걸릴 수 있음 (그림처럼 경로 길이 최대 2배 가까이 차이 날 수 있음)
- 단, 균형 조정이 널널하기 때문에, 삽입 삭제 비용이 덜하다

그러하다.
실제론 RB-tree가 좀더 일반적으로 사용된다고 한다. 일반적인 경우 RB-tree가 삽입, 삭제, 조회에서 비교적 좋은 성능을 보이지만, 빠른 조회를 위해선 AVL트리를 활용할 수 있겠다.

다음은 RB-tree가 실제로 활용되는 예시다.

어디에

Java: java.util.TreeMap, java.util.TreeSet
C++ STL (in most implementations): map, multimap, multiset
Linux kernel: completely fair scheduler, linux/rbtree.h

소감

역시 재밌었다. 특히 이번주는 블로그 포스팅 하는 재미를 조금 알게 된 것 같다.
블로그는 피드백이 생명인거 같다. 뿌듯했다.

한번 더 후회없는 한 주가 되길