ft_containers[Red-Black Tree]

RB Tree 조건

1. 각 노드의 색은 Red or Black이다.
2. 루트 노드의 색은 Black이다.
3. 모든 리프 노드의 색은 Black이다.
4. Red노드의 자식 노드는 전부 Black이다.
5. 루트 노드에서 시작해서 리프 노드에 이르는 모든 경로에는 동일한 개수의 Black노드가 존재한다.

---

RB Tree 특징

NIL노드 : 존재하진 않지만 존재한다 생각하는 노드이다.

                트리의 끝에 항상 존재하며 색은 Black이다.

NIL노드 설명

삽입시의 해당 노드는 Red로 들어간다.

삼촌 노드 : 부모 노드의 형제 노드를 뜻한다.

---

RB Tree Rotation

트리를 삽입하고 삭제하는 과정에서 RB의 조건이 맞지 않는 경우가 있는데 이를 우리는 회전을 하거나 색을 바꿔줌으로써 조건을 맞춰간다.

회전 설명

위의 그림을 보면 간단하게 보일지도 모른다.

하지만 step by step으로 거쳐간 상황들이 몇 가지 있다.

---

Rotation

왼쪽 그림에서 오른쪽 그림으로 변형시키는 과정이다.

아래의 그림이 슈도 코드인데 한 줄씩 따라가면서 해보면 간단하다.

left rotation pseudo code

과정은 간단하게 2 과정이다.

1. 자식 교환
2. 부모 교환

Right Rotation은 위 코드에서 right->left & left->right로 교환하면 된다.

 

---

RB Tree Insert

트리의 삽입은 일반적인 삽입 후에 조건을 만족하도록 교정하는 과정이 있다.

 

RB의 조건을 만족하지 못하는 경우의 수는 3가지이다.

1. 삽입한 노드가 루트 노드일 때
2. 부모 노드와 삼촌 노드가 Red일 때
3. 부모 노드가 Red인데 삼촌 노드가 Black일 때

 

---

삽입한 노드가 루트 노드일 때

 

삽입노드 = 루트노드

---

부모 노드와 삼촌 노드가 Red일 때

 

부모,삼촌 = Red

---

부모 노드가 Red인데 삼촌 노드가 Black일 때

 

부모 = Red, 삼촌 = Black

---

RB Tree Delete

삭제는 2가지 case로 삭제가 진행되고 RB의 조건에 맞게 조정한다.

일단 삭제할 노드, 대체할 노드, 대체할 노드를 대체할 노드를 알고 시작해야한다.

 

대체할 노드는 3가지 경우가 있다.

1. 삭제할 노드의 왼쪽 자식 노드(오른쪽 자식 노드가 NIL 노드일 때)
2. 삭제할 노드의 오른쪽 하위 트리의 가장 작은 노드(오른쪽 자식 노드가 NIL 노드일 때)
3. NIL노드(자식 노드가 모두 NIL 노드일 때)

대체할 노드를 대체할 노드는 2가지 경우가 있다.

1. 대체할 노드의 오른쪽 노드
2. NIL 노드

 

그렇게 정하고 대체할 노드위치에 대체할 노드를 대체할 노드를 넣고 삭제할 노드위치에 대체할 노드를 넣으면 된다.

하지만, 우리가 지울노드가 만약 Black노드였다면 우리는 이미 균형이 잡혀진 트리에 불균형을 초래하는 것이다.

Black노드가 지워지면 "루트노드부터 리프노드의 Black의 수가 같아야한다."는 조건을 위반하는 것으로 재조정이 필요하다.

---

RB Tree를 사용하는 의미는 복잡하지만 복잡한 만큼 효율적이고 최악의 경우에도 우수한 실행시간을 보이기 때문이다.

근데 색만 바꿔버리면 최종 높이들이 달라질 것이다.

그렇기 때문에 우리는 단편만 보는 것이 아니라 전체적인 트리를 보아야 하는 것이다.

 

Delete-fixup의 수도 코드를 보자.

Delete fixup pseudo code

형태는 복잡하게 생겼다.

크게 나누면 2가지, 다음으로는 4가지 정도가 나온다.

먼저 크게 나눠서 보자.

1. 삼촌 노드의 색이 Red일 때
2. 삼촌노드의 색이 Black일 때

삼촌 노드의 색이 Red일 때의 코드를 해석해보면, 부모 노드의 색을 Black으로 만들려 한다.

원래 존재했던 Red를 왼쪽으로 옮기는 과정이다.

이 부분은 이후 나오는 과정에서 왜 그렇게 되는지 알 수 있다.

 

그다음의 4가지 나눠짐을 보자.

1. 삼촌의 자식들의 모두 Black일 때
2. 삼촌의 자식 중 왼쪽이 Red일 때
3. 삼촌의 자식들이 모두 Black이 아닐 때

1번 -> 삼촌 노드를 Red로 바꾸는데, 이는 RB Tree 4번 조건에 'Red의 자식은 모두 Black이다.'를 만족시키면서 균형 잡힌 트리를 만들기 위함이다.

 

2번 -> 삼촌의 왼쪽 자식이 Red, 오른쪽 자식이 Black인 경우 고르게 분포되어있다고 판단한 것처럼 느껴진다.

            그래도 삼촌의 왼쪽 자식을 Black으로, 삼촌을 Red로 바꾸고 우회전을 하는데 이는 왼쪽 트리의 높이를 한 칸 더 길게 만든 것이다.

            그리고 삼촌을 다시 지정한 뒤, 삼촌의 색을 부모의 색으로 바꾸고, 부모의 색을 Black으로 바꾼다.

            또한, 삼촌의 오른쪽 자식의 색을 Blakc으로 바꾼 뒤, 좌회전을 하여 오른쪽 트리의 높이를 한 칸 더 길게 만든다.

            그리고 끝날 수 있도록 x를 루트 노드로 지정한다.

 

3번 -> 삼촌의 색을 부모의 색으로 바꾸고, 부모의 색을 Black으로 바꾼다.

            또한, 삼촌의 오른쪽 자식의 색을 Blakc으로 바꾼 뒤, 좌회전을 하여 오른쪽 트리의 높이를 한 칸 더 길게 만든다.

            그리고 끝날 수 있도록 x를 루트 노드로 지정한다.

 

처음 보았을 땐, 뭐 이리 거지같이 만들어 놨는지 모르겠다는 생각이었는데 구조와 색을 신경 쓰는 방식은 두 개의 손을 한 손씩 다른 일을 하는 것만큼 어려운듯하다.

 

결론적으로는 지운 노드가 Black인지 Red를 확인하는 작업에서 루트 노드의 왼쪽, 오른쪽 하위 트리에서 리프 노드로 도달하는 과정에서의 Black노드의 개수를 조절하는데, 이것을 대체 노드의 위치부터 양쪽의 균형을 유지하는 방식인 것이다.

---

최종 느낀점

아래 내용은 단순히 내 생각을 적는 공간입니다. 참고만 해주세요.

 

일단 RB Tree는 어려운 게 맞았다.

사람들이 괜히 AVL Tree로 꺾는 게 아니었다. (다만, AVL Tree도 어렵다.)

 

RB Tree는 Red와 Black의 조합인데, 여러 가지 조건들을 만족시켜야 한다.

조건들은 위에 있다.

 

하지만 나와있는 조건만 고려하면 살짝 문제가 생기는데,

이는 문제를 풀면서 각 조건들 만족하지만 루트 노드의 양쪽 하위 노드의 높이가 맞지 않다면,

그에 따라 높이도 맞춰주어야 한다는 것이다.

즉, 각각의 루트 노드까지 Black의 개수가 같다는 것은 높이 차이가 커도 1 정도일 것이다.

 

근데 생각해보면 우리는 Double Red는 허용하지 않지만 Double Black은 허용한다.

나는 이 부분을 생각해서 Double Black은 생각하지 않았다.

하지만, 생각해보면 우리는 자가 균형 이진 탐색 트리를 만들어야 한다는 것을 기억하고 있어야 한다.

스스로 균형을 맞추는데 이 균형을 맞출 때 고려해야 하는 부분은 리프 노드까지의 높이와 리프 노드까지의 Black이다.

 

예를 들자면, 어떤 조건도 위배하지 않은 트리의 루트 노드의 하위 노드 중 왼쪽은 Black으로만 이뤄져 있고, 오른쪽은 Red, Black이 균형 있게 이뤄져 있다.

그렇다면 이를 균형이 잡혀있다고 말할 수 있을지에 대한 고민을 해봐야 한다.

 

결과적으로, 최종적으로 존재해야 하는 조건은 Double Black은 사용할 수 있지만 자제해야 한다고 생각한다.

 

끄읕!!!!!