Red Black Tree에 대해 설명하세요
Keyword
탐색, 삽입, 삭제, Black-height, 루트 노드,리프노드(NIL)
Script
Red Black Tree는 자가 균형 Binary Search Tree의 일종으로, 각 노드를 빨간색 혹은 검은색으로 맵핑하여 균형을 유지합니다. 이때, 항상 root node와 모든 leaf node는 검은색이며, 빨간색 노드의 자식은 항상 검은색입니다. 그리고 모든 leaf node에서 black depth, 즉 leaf node에서 root node로 가는 경로에서 만나는 검은색 node의 개수는 모두 같습니다. 이 규칙을 통해, Red Black Tree에서는 탐색과 삽입, 삭제에서 O(log n)의 시간복잡도로 연산을 수행할 수 있습니다.
Additional
NIL Node
NIL Node는 Tree의 끝을 나타내는 Node로, Red Black Tree에서 leaf node에 해당한다.
New, Parent, Grand Parent, Uncle
Red black Tree에서 새로운 노드를 삽입할 때, 새로 삽입할 노드를 N(New), 그 부모 노드를 P(Parent), 조상 노드를 G(Grand Parent), 삼촌 노드를 U(Uncle)라고 한다.
Red Black Tree의 삽입
Red Black Tree에 새로운 Node를 삽입할 때, Binary Search Tree의 규칙을 따르고, 새로운 Node는 항상 빨간색으로 삽입한다. 이때, 빨간색 Node의 자식으로 빨간색 Node가 들어가게 되면 Uncle Node의 색상에 따라서 균형을 맞추는 과정으로 Restructuring 또는 Recoloring이 발생한다. Uncle Node가 검은색이라면, Restructuring이 발생하고, Uncle Node가 빨간색이라면, Recoloring이 발생한다.
Restructuring
1. 새로운 노드(N), 부모 노드(P), 조상 노드(G)를 오름차순으로 정렬한다.
2. 셋 중 중간값을 부모로 만들고 나머지 둘을 자식으로 만든다.
3. 새로 부모가 된 노드를 검은색으로 만들고 나머지 자식들을 빨간색으로 만든다.
Recoloring
1. 새로운 노드(N)의 부모(P)와 삼촌(U)을 검은색으로 바꾸고 조상(G)을 빨간색으로 바꾼다.
1-1. 조상(G)이 루트 노드라면 검은색으로 바꾼다.
1-2. 조상(G)을 빨간색으로 바꿨을 때 또다시 Double Red가 발생한다면 또다시 Restructuring 혹은 Recoloring을 진행해서 Double Red 문제가 발생하지 않을 때까지 반복한다.
Red Black Tree의 삭제[pending...]
특별히 다른 작업이 필요없는 삭제의 경우는 다음과 같다.
1. 삭제하는 노드가 빨간색인 경우
2. 삭제하는 노드가 검은색이지만 그 유일한 자식 노드가 빨간색인 경우
삭제하는 노드가 빨간색인 경우는
이외에는 문제가 발생하고, Red Black Tree의 규칙에 맞게 수정이 필요하다.
Default Case
Default Case는 삭제가 일어났을 때, 기본으로 실행되는 과정이다. 삭제된 노드가 검은색인 경우, 그 자리를 대체하는 노드를 검은색으로 칠한다.
이때, 새로 칠한 노드가 원래 검은색인 경우
