1. rbtree

다음의 5개의 속성을 모두 만족하는 이진 트리

2. 삽입

1. 삽입하는 노드 색은 항상 RED - 5번 속성을 만족하기 위해

따라서, 아래의 케이스들로 문제가 나눠지게 된다. 즉, 트리를 리밸런싱하여 위의 5가지 조건을 모두 만족하도록 만들어야 한다!

2. CASES

1. 삽입된 red 노드가 부모의 왼쪽 자녀 && 부모는 red고 할아버지의 왼쪽 자녀 && 부모의 형제는 black : case 3

   
   -> 부모와 할아버지의 색을 바꾼후 할아버지 기준 오른쪽으로 회전

2. 삽입된 red 노드가 부모의 오른쪽 자녀 && 부모는 red고 할아버지의 왼쪽 자녀 && 부모의 형제는 black : case 2

   
   -> 부모를 기준으로 왼쪽으로 회전한 뒤 위와 같은 방식으로 회전. 즉 case 3로 바꾼 뒤 해결.

3. 삽입된 red 노드의 부모가 red && 부모의 형제도 red : case 1

   
   -> 부모와 부모의 형제를 black으로 바꾸고 할아버지를 red로 바꾼 뒤 할아버지에서 다시 확인 시작(끝이 아님)

3. 삭제

1. 이진트리의 노드 삭제 방식과 동일

단, rbtree에서는 어떤 색이 삭제되는지가 속성 위반 여부를 확인할 때 중요하다.

2. 삭제되는 색 결정

1. 삭제하려는 노드의 자녀가 없거나 하나일 때(nil node 제외)

   -> 삭제되는 색 = 삭제되는 노드의 색

2. 삭제하려는 노드의 자녀가 둘일 때(nil node 제외)

   -> 삭제되는 색 = 삭제되는 노드의 successor의 색

3. 삭제되는 색 결정 이후

1. 삭제되는 색이 red

   -> 어떠한 속성도 위반하지 않음

2. 삭제되는 색이 black

   -> 2, 4, 5번 속성을 위반할 수 있음. 따라서 리밸런싱이 필요할 수 있음!

4. 리밸런싱 과정

부모로 타고 올라가면서 블랙이면 계속 while문을 돈다.
결국 doubly black이란건 부모가 블랙일 때를 말하는 것!

while (타겟이 루트아님 && 타겟 == BLACK) {

    // CASE 1.
    if **형제 == RED**
        형제/부모 서로 색바꾸기, 부모기준 회전 (타겟이 내려가도록)

    // CASE 2.
    if **형제 == BLACK, 형제의 자식 둘다 블랙**
        형제/자신의 블랙을 부모로 올리기 -> 형제를 RED로 변경, 부모에서 다시 fixup

    else {
        // CASE 3.
        if 형제 == BLACK, (**형제의 꺾인 자식**) == RED
            자식 RED와 형제 서로 색바꾸기, 펴지게 회전 (RED가 바깥쪽에 오게)
            CASE 4가 됨

        // CASE 4. 형제 == BLACK, (**형제의 펴진 자식**) == RED
        부모/형제 서로 색바꾸기
        형제의(펴진 자식) = BLACK
        부모기준 회전 (타겟이 내려가도록)
        타겟을 루트로 설정 -> while 종료
    }
}

// 종료전
타겟을 BLACK으로 변경