산술비교가 가능한 대용량 데이터에 대해 삽입/삭제/검색을 해야하는 경우 적용할 알고리즘. C++의 std::map을 사용하면 굳이 몰라도 되긴하지만, C에서는 없으니까, 오픈소스를 가져다 이용한다.
Red / Black 지정에 대한 규칙은 다음과 같다.
- 하나의 노드는 Black 아니면 Red 로 한다.
- Root 노드는 반드시 Black 이다.
- 모든 Leaf 노드는 Black 이다.
- Red 노드의 Child 노드 양쪽(left/right)은 항상 모두 Black 이다. 그러므로, Black 노드만 Red 노드의 Parent 노드가 될 수 있다.
- 어떤 노드로부터 시작되어 Leaf 노드에 도달하는 모든 경로에는 Leaf 를 제외하고 모두 같은 개수의 Black 노드가 있다.
위와 같은 다섯가지 조건을 만족하게끔 알고리즘이 구성되어 있다. 그러다보니, Root 노드로부터 가장 먼 경로까지의 거리가, 가장 가까운 경로까지의 거리의 두배보다 항상 작게 된다. 그래서 대략 균형잡힌 트리라고 볼 수 있겠다. 삽입/삭제/검색에 대해 최악의 경우에도 시간복잡도가 보통의 이진트리와 비교해보면 훨씬 효율적이라고 볼 수 있다. 삽입/삭제/검색에 대한 시간복잡도면에서 AVL 알고리즘이 이와 유사하긴 하지만, Red/Black 알고리즘이 효율성에서 훨씬 앞서고 있으며 보다 많이 사용되고 있다.(거의 대부분)
Download document (RedBlack Tree.pdf)
'$ SaVvY > » computer' 카테고리의 다른 글
Building ACE framework on Mac OS X Mountain Lion. (0) | 2013.07.10 |
---|---|
Public DNS server (0) | 2013.07.10 |
GDBM User Reference (0) | 2013.07.05 |
SyncMaster TA531 with Mac OS X (1) | 2013.07.01 |
UDP Maximum message size (0) | 2013.06.21 |