Red-Black tree란? Red-Black tree(R-B tree)는 AVL tree, Splay tree와 같은 Self-balanced Binary Search Tree입니다. Red-Black tree는 말그대로 모든 노드가 빨간색과 검정색으로 표현됩니다. 이러한 R-B tree는 균형을 유지하기 위해 아래 다섯가지 조건을 만족해야 합니다. 1. 모든 노드는 빨간색 혹은 검은색이어야 합니다. 2. 루트 노드는 검은색이다. 3. 모든 NIL은 검은색이다. (NIL : null leaf, 자료를 갖지 않고 트리의 끝을 나타내는 리프 노드) 4. 빨간색 노드의 자식은 반드시 검은색이다. 5. NIL에서 루트 노드까지 가는 경로에서 만나는 검은색 노드의 개수가 같다. Red-Black tree의 원..
