RB 트리의 노드 삽입에 대해 알아보자

RB 트리의 삽입 개념

• 삽입 전 RB 트리의 속성을 만족한 상태여야 한다.

• 삽입 방식은 일반적인 BST(이진탐색트리)와 동일하다.

• 삽입할 노드의 색은 항상 RED다. (삽입 후에도 5번 속성을 만족하기 위해서!)

• 알맞은 자리에 노드 삽입 이후, RB 트리 속성 위반 여부를 확인한다.

• RB 트리 속성을 위반했다면 트리를 재조정(insert-fixup)한다. 이 과정에서 트리는 균형을 잡아낸다.

• RB 트리의 속성을 만족한다면 삽입 종료.

RB 트리의 속성 위반 케이스들

Case 1

• 삽입된 노드의 부모, 삼촌이 RED라면 -> 4번 위반
• 부모와 삼촌을 BLACK으로 바꾸고, 할아버지를 RED로 바꾼다.
• 이후 할아버지에서 다시 속성을 만족하는지 확인한다.

Case 2

• 삽입 노드가 부모의 오른쪽자식, 부모는 RED, 삼촌은 BLACK - 4번 위반
• 부모를 기준으로 왼쪽으로 회전한다.
• 이후 Case 3와 동일하게 해결

Case 3

• 삽입 노드가 부모의 왼쪽자식, 부모는 RED, 삼촌은 BLACK - 4번 위반
• 부모와 할아버지의 색을 바꾼 후, 할아버지 기준으로 오른쪽으로 회전
• 좌우 대칭으로 동작

의사 코드 예시

while (부모가 RED) {

    // CASE 1. 
    if 부모/삼촌 == RED이면, 
        부모/삼촌 모두 BLACK으로 바꾸고, 할아버지를 RED로 변경
        할아버지에서 다시 시작
        
    // CASE 2/3. 삼촌 == BLACK
    else {
        // CASE 2. 
        if 할아버지/부모/자신 꺾인상테
            회전해서 부모/자신을 펴준다. CASE 3 상태가 됨
        
        // CASE 3. 할아버지/부모/자신 펴진상테
        부모/할아버지 서로 색바꾸기
        할아버지 기준 회전
    } 
}

// 종료전
루트를 BLACK으로 변경