목차

RB Tree 이론

이진 검색 트리(BST)와 균형 탐색 트리

• 정의 및 조건

  BST를 기반으로 하는 트리 자료구조. 동일한 노드의 개수에서 시간 복잡도를 줄이기 위해 complete binary tree를 만들어 depth를 최소화하는 것이 핵심이다.

  <aside> 💡 1. 모든 노드는 빨간색 아니면 검은색이다. 2. 루트는 검은색이다. 3. 리프 노드(NIL)은 검은색이다. 4. 만약 부모 노드가 빨간색이면, 자식 노드들은 모두 검은색이다. 5. 각 노드로부터 그 노드의 자손인 리프 노드(NIL)로 가는 모든 경로**(흑색 경로)**는 같은 수의 검은색 노드를 포함한다.

  </aside>

  

  루트 노드부터 모든 리프 노드로 가는 길은 흑색 노드가 2개다.

• 특징

  • BST의 일종이므로 그 특성을 모두 갖는다.
  • 각 노드에 한 비트의 color 필드가 추가로 있다.
  • Black height : 노드 x로부터 리프 노드까지의 경로에서 모든 black 노드들의 개수(노드 x를 포함하지 않음).
  • Balanced 상태 : 루트부터 리프 노드까지 모든 경로 중 최소 경로와 최대 경로의 크기 비율은 2보다 크지 않다. 이를 통해 RBT는 self-balancing tree로서 기능한다.
  • NIL : 노드의 child가 없을 경우 child를 가리키는 포인터는 NIL 값을 저장한다. 이러한 NIL들을 리프 노드로 간주한다.

• N개의 내부 노드를 가지는 RBT는 최대 2log(N+1)의 높이를 가진다.

  Search, Minimum, Maximum, Successor, Predecessor 등 동적 집합 연산을 O(logN) 안에 구현할 수 있다.

RB Tree 구현

Sentinel Node와 T.nil

• Sentinel Node 단말 노드

  경계 노드. 트리의 순회를 끝내는 기준이 된다.

• T.nil(Tree 구조체의 nil 멤버)

  모든 NIL(리프 노드)를 하나의 객체로 관리한다. 메모리를 절약하고 경계 조건을 관리하기 편하다는 장점이 있다.

  <aside> 💡 노드 하나를 할당하여 이를 리프로 정하고, 모든 NIL 리프에 대한 포인터가 이 노드를 가리키도록 한다.

  </aside>

  

코어 기능

Rotate

Insert와 Delete 시, RBT의 기본 속성을 위반하는 상황이 생긴다. 이를 수정하기 위해 일부 노드의 색깔과 포인터를 변경한다. 이 때 포인터를 변경하기 위해 Rotate를 사용한다.

Insert → O(logN)

RedBlack Tree에 대해

<aside> 💡 1. 새 노드 z를 삽입한다. → O(logN) : 이진탐색(트리의 높이) 2. 새 노드 z를 RED로 칠한다. → O(1) 3. 삽입한 후에 RBT의 규칙에 어긋난다면 insert_fixup()을 실행한다.

</aside>

• 새 노드를 적색으로 칠하는 이유

  아래의 3가지 RBT 조건만 변경하면 된다. 이 두 조건이 변경하기 쉬운 편이다.

  <aside> 💡 2, 3. 루트와 리프 노드(NIL)은 검은색이다. 4. 만약 부모 노드가 빨간색이면, 자식 노드들은 모두 검은색이다.

  </aside>

Insert_fixup → O(1)

<aside> 💡 위반된 RBT 규칙을 바로잡는다.

• 삽입한 노드가 root면 노드를 BLACK으로 칠한다. → O(1)
• 삽입한 노드의 삼촌이 RED면 Recolor 진행 → O(1)
• 삽입한 노드의 삼촌이 BLACK이면 Restructure 진행 → O(1) : Rotation

</aside>

• Recolor : 삽입한 노드의 삼촌이 RED일 때 진행

  새 노드의 부모, 삼촌을 BLACK으로, 조부모를 RED로 바꿔준다.

  • 부모 삼촌을 BLACK으로 바꾸고 바로 조부모를 RED로 바꿔줌으로써 black height를 맞춰줄 수 있다.
  • 조부모의 부모가 RED인 경우, 다시 한 번 전체적인 Fixup 절차를 거쳐야 한다**(while문을 다시 한 번 돌아야 한다).**

• Restructure : 삽입한 노드의 삼촌이 BLACK일 때 진행

  Triangle 형태를 지나면 필연적으로 Line 형태가 되고, Line 형태를 거치면 균형 잡힌 이진 트리를 무조건 만들 수 있다.

  • Triangle 형태

    새 노드가 부모의 왼쪽 노드이고 부모는 조부모의 오른쪽 노드일 때 or 새 노드가 부모의 오른쪽 노드이고 부모는 조부모의 왼쪽 노드일 때

    <aside> 💡 새 노드와 그 부모를 회전시킨다.

    </aside>

    • 회전시키고 아직 색깔을 바꾸지 않았으므로, Line 형태의 Restructure를 바로 실행해야 한다.

    

    Triangle 형태

    

    새 노드와 부모를 회전시킨다.

  • Line 형태

    새 노드가 부모의 왼쪽 노드이고 부모도 조부모의 왼쪽 노드일 때 or 새 노드가 부모의 오른쪽 노드이고 부모도 조부모의 오른쪽 노드일 때

    <aside> 💡 새 노드의 조부모를 회전시키고 부모와 조부모의 색깔을 바꾼다.

    </aside>

    • 부모 노드의 색깔이 BLACK으로 RBT의 규칙을 위배하지 않으므로, 여기서 fixup 함수는 끝나게 된다.

    

    Line 형태

    

    조부모를 회전시키고 부모와 조부모의 색깔을 바꾼다.

Transplant(T, u, v) → O(1)

• transplant(T, u, v) 는 u->parent의 자식 노드를 u 대신 v로 바꿔준다.

  따라서 u의 자식들과 v를 따로 이어주어야 한다.

• u는 삭제되지 않는다. 단지 u->parent로부터 접근이 불가능하게 됐을 뿐이다.

Deletion(T, p) → O(logN), fixup 없이도 O(logN)

https://github.com/Roha-Lee/rbtree-lab

<aside> 💡 p : 지워질 노드 y : 지워질 노드(case1,2), 대체할 노드(case3) x : y의 자리를 대체할 노드

</aside>

지워지거나 삭제될 노드 y의 색깔을 미리 저장해 둔다. 만약 지워진 노드 y의 색이 Black일 때 문제가 되므로, fixed 함수를 호출해 문제를 해결한다.

Deletion은 크게 3가지 경우로 나누어 해결할 수 있다.

• Case1, 2

  노드의 한 자식이 nil인 경우(두개 다 nil인 경우도 포함)

  • 나머지 자식을 x로 두고 y와 대체한다.

• Case 3

  노드의 두 자식 모두 nil이 아닌 경우

  • p의 오른쪽 자식의 왼쪽 자식이 없는 경우
  • p의 오른쪽 자식의 왼쪽 자식이 있는 경우(successor가 있는 경우)

    • 삭제하려는 노드의 직후 원소(다음으로 가장 큰 원소) y를 찾아서 오른쪽 자식을 직후 원소 자리로 옮겨준다.(transplant)

    • y를 삭제하려는 노드 자리로 옮겨준다.(transplant)

    • y의 색을 삭제하려는 노드 색으로 바꿔준다.

      → y가 대체하는 공간의 색깔은 이제 RBT 규칙에 어긋날 일이 없다.

• 그 후, 대체되거나 지워진 노드 y의 색깔이 BLACK일 경우, BLACK 노드를 지웠으므로 그 경로의 Black height가 1 낮아진다. 이는 RBT의 규칙 5에 어긋나므로 수정하기 위해 fixup(T, x)을 실행시킨다(이 때 x는 y의 자리를 대체한 노드).

• p의 메모리 공간을 free한다.

• 예제

Delete_fixup(T, x) → O(logN)

<aside> 💡 Delete하며 바뀌거나 삭제된 노드의 색이 BLACK이라면, RBT 규칙 5번에 위반된다. 이를 해결하기 위해, 빈 공간을 대체한 노드 x에 가상의 BLACK을 하나 더 추가한다. 즉, 함수가 시작될 때 x는 여분의 B를 하나 더 들고 있다.

</aside>

<aside> 💡

1. 대체된 노드 x의 색깔이 RED일 때
2. 대체된 노드 x가 root일 때
3. 대체된 노드 x의 색깔이 BLACK일 때 논외. 삭제된 노드 y의 색깔이 RED일 때

</aside>

<aside> 💡 대체된 노드 x의 색깔이 BLACK일 때, 4가지의 케이스가 있다.

Case 1 : x의 형제 노드 w가 RED → O(1) Case 2 : x의 형제 노드 w가 BLACK, w의 왼쪽, 오른쪽 자식이 모두 BLACK → O(logN), while문이 실행되는 경우가 이 부분. Case 3 : x의 형제 노드 w가 BLACK, w의 왼쪽 자식 RED, 오른쪽 자식 BLACK → O(1) Case 4 : x의 형제 노드 w가 BLACK, w의 오른쪽 자식 RED → O(1)

</aside>

• 논외. 삭제된 노드의 색깔이 RED일 때

  Black height에 변화가 없다. 그냥 Delete만 진행하고 그 자리를 대체하는 노드에게 색깔을 덮어주면 끝이다.

  

  p의 자식이 둘 다 NIL이 아니고, y가 RED, x가 NIL이다.

• y가 BLACK이고 x의 색깔이 RED일 때

  규칙대로 자리를 메꾼 후 x의 색깔만 BLACK으로 덮어주면 된다.

  

  p = 18, y = 22, x = 26. y == BLACK이지만 x = RED라서 그냥 while문 돌지 않는다.

• x가 root일 때

  그냥 root이므로 BLACK으로 칠해준다.

• x의 색깔이 BLACK일 때.

  x는 두 개의 B를 들고 있다. 이 때 case는 x가 왼쪽 자식일 때, 오른쪽 자식일 때 각각 4 case가 있다.

  Google Slides - create and edit presentations online, for free.

  Black height 중심으로 설명한 fixup

  • Case 1 : x의 형제 노드 w가 RED → O(1)

    • x의 부모와 w의 색을 교환한다.
    • x의 부모를 기준으로 Left Rotate한다.

    결과 : Case 2, 3, 4 중 하나(w가 BLACK)로 바꾼다.

    

  • Case 2 : x의 형제 노드 w가 BLACK, w의 왼쪽, 오른쪽 자식이 모두 BLACK → O(logN)

    • x와 w에서 각각 BLACK을 하나씩 뺀다.
    • x의 부모를 새 x로 만들어준다.

    결과 : while문을 탈출하거나 새 x로 다시 while문을 돈다.

    

  • Case 3 : x의 형제 노드 w가 BLACK, w의 왼쪽 자식 RED, 오른쪽 자식 BLACK → O(1)

    • w와 w의 왼쪽 자식의 색을 교환한다.
    • w를 중심으로 Left Rotate한다.

    결과 : Case 4(w.right == RED)로 바꾼다.

    

  • Case 4 : x의 형제 노드 w가 BLACK, w의 오른쪽 자식 RED → O(1)

    • w의 부모의 색을 w로 옮긴다.
    • x의 부모를 BLACK으로 만든다.
    • w의 오른쪽 자식을 BLACK으로 만든다.

    결과 : 조정이 완료되면 RBT의 규칙을 지키게 된다. 끝.

    

• 전체 코드

기타