✏️ Red-Black Tree 개념

이때 BST의 worst case는 한 쪽으로 편향된 트리의 탐색입니다. 즉, O(N)이 걸리는 상황을 말합니다.
따라서 Red-Black Tree는 O(logN)이 나올 수 있도록 수정한 BST라고 볼 수 있습니다.

RB tree는 스스로 균형을 맞춤으로써 트리가 편향된 구조가 되지 않도록 하여 최악의 경우에도 시간복잡도가 O(N)이 아니라 O(logN)이 나올 수 있도록 하는 것이 RB tree의 장점입니다.

Red-Black Tree의 다섯가지 속성

3번 속성을 알아보기에 앞서 nil 노드라는 것을 알아봅시다.

일반적인 노드와 같다고 생각해야 합니다.

현재 상황에서 30, 90 nil노드 아니므로 nil 노드 자식을 가져야 합니다. 또한 nil은 블랙으로 처리하기로 했으므로 아래와 같은 그림이 성립합니다.

• 80을 예시로 보면 nil 노드까지 black의 수는 모두 1개임을 알 수 있습니다. (본인은 제외이므로 1개!)

• 20에서 확인해보면 nil노드까지 5개의 path가 존재하며 모두 2개 인것을 알 수 있습니다.

만약 5번 속성이 성립하지 않는다면 임의의 노드 x로부터 nil 노드까지 내려가는 경로의 수의 black수가 모두 다를 것이기 때문에 black height를 정의할 수 없습니다. (즉, 모두 같기 때문에 black height를 정의할 수 있다는 말입니다.)

• 20의 black height는 2임을 알 수 있습니다.
• 50의 black height는 2임을 알 수 있습니다.

• A와 그 자식들의 색깔만 바꾸어줬기 때문에 A의 부모의 입장에서의 black height는 변화가 없음을 알 수 있습니다.
  -> 자식과 손자를 지날텐데 바꿔주더라도 어쨋든 1개의 black만 존재하기 때문입니다.
• A입장에서 보면 왼쪽, 오른쪽 모두 black이 하나 늘어났을 뿐이지 두 쪽 모두 black의 개수가 같습니다.
• B, C 입장에서 보면 본인은 포함하지 않기 때문에 각 각의 black height는 같은것을 알 수 있습니다.
• 각 i,j,x,y 서브트리의 변화는 없으므로 5번 속성도 만족하고 있음을 증명할 수 있습니다.

삽입은 모두 Red이고 leaf노드는 nil이어야 하므로 다음과 같은 Tree가 그려집니다. 이때 nil은 black 이므로 3번 속성을 만족하는 것을 알 수 있습니다.

그런데 2번 속성에 의해 root 노드는 black 이어야 합니다. 따라서 루트 노드를 black으로 바꾸어주면 해결됩니다.

정리하면 red 삽입 후 2번 속성을 위반했을 때 루트 노드를 black으로 바꾸어주면 해결할 수 있습니다.

50과 비교하여 더 작으므로 왼쪽으로 이동하고 red를 삽입하면 다음과 같은 Tree가 만들어집니다. 이때 RB Tree의 모든 속성을 만족하게 됩니다.

그렇다면 왜 삽입 노드는 모두 Red여야 할까요?

새로 삽입될 위치가 nil노드라고 합시다. 그리고 위에 조상 노드 아무거나 하나 선택해봅시다. 조상노드에서 삽입하기 전까지의 black수랑 삽입한 이후의 black 수랑 같은것을 확인 할 수 있습니다.

따라서 위과 같이 새로 추가하더라도 기존에 있던 RBT의 부모노드에서의 5번 속성을 만족하게 됩니다.

지금부터 nil을 표기하지 않더라도 있는것으로 생각하며 이때 nil 노드는 black임을 잊지 않도록 합시다.

BST 삽입 논리에 따라 10은 다음과 같은 위치에 저장될 것입니다.
삽입해보니 4번 속성을 위반한것을 알 수 있습니다.

해결할 수 있지 않을까 생각해볼 수 있습니다.

왼쪽 자식들은 자신보다 작은 값, 오른쪽 자식들은 자신보다 큰 값이 유지되어야 할 것입니다

아래와 같이 case3의 방법으로 바꾸어 주면 해결 가능합니다.

그림과 같이 CASE 1은 여러 개의 경우가 가능합니다.
이 때 할아버지가 루트 노드이며 red라면 black으로 바꿔주면 됩니다.
만약 할아버지의 부모 또한 red라면 4번 속성을 위반하므로 해당하는 CASE로 적용하여 해결해야 합니다.

RBT 삽입 예제

35를 기준으로 할아버지까지 가는게 꺽여있으므로 case2의 상태입니다.
35와 50을 오른쪽으로 회전해주고 이때 40이 붕 뜨게 되는데 50의 왼쪽 자식은 비어있게 되므로 40을 삽입해주면 됩니다.

35의 왼쪽 서브트리는 35가 올라가면서 붕 뜨게 되는데 20의 오른쪽이 비어있기 때문에 빈곳에 삽입해주면 됩니다.

RBT 삭제 예제

유효한 값을 가지는 자녀는 nil을 포함하지 않습니다.

• 20을 삭제한 경우 : BST 삭제 방식에 따라 20과 25의 값을 바꾸고 바꾼 리프 노드의 값을 삭제합니다. 이때 색깔은 바꾸지 않습니다.
• 35를 삭제한 경우 : 35와 37을 바꿉니다. 결론적으로 삭제할 노드는 red 35가 되며 (37이 red) 이 값이 삭제 됩니다.
  -> 35의 자리는 black 37이 됩니다.

• #1 : 당연히 상관없습니다.
• #2 : 삭제되는 색이 Red이므로 black과는 상관없는 상황입니다.
• #3 : 2번과 마찬가지입니다.
• #4 : 4번은 결국 Red가 두개 이상 붙어있으면 안된다는 조건인데 이미 RB Tree였기 때문에 Red를 삭제하더라도 연속하는 Red가 있을 수 없습니다.
• #5 : 결국 black수를 세는거니까 Red가 삭제되는것은 영향을 미치지 않습니다.

예를 통해서 알아봅시다.

40을 삭제하면 4, 5번 조건을 만족하지 않는다는 것을 알 수 있습니다.

50에서 nil노드까지의 black을 세어보면 다르다는 것을 확인할 수 있습니다. 따라서 5번 조건도 만족하지 않습니다.

지금까지 삭제 후 RBT 속성 위반 여부에 대해 확인해봤습니다. 속성 위반을 체크했다면 이를 어떻게 해결할지 알아봅시다.

결론적으로 삭제되는 색이 black일 때 해결해봅시다.

삭제하는 색이 black이므로 5번을 위반하느 것은 너무나 자연스럽습니다.

따라서 5번 속성을 만족하게 됩니다.

예시와 함께 이해해보겠습니다.

이제 doubly black 혹은 red-and-black을 해결해주면 됩니다.

이때 C는 red, black중 어떤 색깔인지 알 수 없습니다. 그러나 우리는 extra black의 개념을 사용하고 있습니다. 따라서 D의 색깔을 red, E의 색깔을 black 그리고 C에 extra black을 넣어주면 됩니다.

D가 위 그림과 같은 위치로 가고 싶은 상태입니다. 추가적으로 BST의 성질을 만족하기 위해서는 회전을 사용해야 합니다. 따라서 B와 D의 색깔을 바꾸고 회전시켜줍시다.

<결론> 은 아래와 같습니다.

다른 케이스를 살펴봅시다.

C를 E의 위치로 옮기기 위해서는 C와 D의 색깔을 바꾼 후 오른쪽 회전을 해주면 됩니다.

<결론>

이제 다른 케이스를 살펴봅시다.

<결론>

마지막 케이스를 알아봅시다.

B의 위치가 black이어야 하기 때문입니다.

최종적으로 이러한 모양이 되고 case 2,3,4 중에 해결책을 찾으면 됩니다.

<결론>

지금까지의 내용을 정리해봅시다.

Red-Black Tree 삭제 예제

25의 왼쪽 자녀는 black(nil)이므로 case3에 해당합니다.

따라서 27을 25의 왼쪽으로 옮겨야 합니다.

그러기 위해서 먼저 25와 27의 색깔을 바꾸어 줍시다.

이후 회전하면 아래와 같은 모양이 만들어집니다.

35의 자식이 2개이므로 successor와 위치를 바꾸어주어야 합니다.
따라서 40이랑 값을 바꾸어 주어야 합니다.

이후 40값을 삭제해야하며 black이므로 extra black을 추가해주어야 합니다. 그럼 어디에 추가해주어 하냐면,, 40을 대체할 노드에 추가해주어야 합니다. 이 경우에는 45가 40의 대체 노드가 될 것입니다.

최종적으로 이러한 형태가 됩니다.

최종적으로 이러한 형태가 됩니다.

45에 extra black을 전달해줍니다. 30을 red가 되고 nil 노드의 extra black은 없어집니다. 그럼 아래와 같은 형태가 만들어집니다.

extra black이 red 노드와 함께 있으므로 그냥 black으로 바꾸어 주면 됩니다.

Red-Black Tree의 시간복잡도

AVL Tree와 비교

삽입/삭제

• Red-Black Tree가 AVL Tree보다 삽입/삭제 성능에서 더 빠른이유는 AVL Tree의 경우 수정 시 root 노드까지 올라가며 balance factor를 확인하고 balance factor가 맞지 않을 경우 구조를 바꿔줍니다. 따라서 AVL Tree의 경우 균형을 엄격하게 맞추기 때문에 삽입/삭제마다 시간적 비용이 Red-Black Tree보다 더 많이 발생합니다.

• 반면에, Red-Black Tree는 삭입/삭제 시 올라가는 경우도 있지만 그 자리에서 끝나는 경우도 존재합니다. 따라서 삽입/삭제 시 Red-Black Tree가 좀 더 빠릅니다.

검색
AVL Tree의 균형이 Red-Black Tree보다 더욱 정교하므로 검색 성능에서 AVL Tree가 더 나은 성능을 보입니다.

참고
쉬운코드 유튜브