RB Tree에 대한 고찰

모기·2025년 4월 18일

gochal

기본 규칙과 회전은 Krafton Jungle Sixth를 참고하길 바란다.
https://velog.io/@mogiyoon/Krafton-Jungle-Sixth

이 글에서 다루고 싶은 것은
단순한 삽입과 제거의 규칙보다는
왜 삽입을 할 때 그런 선택을 했고,
왜 제거를 할 때 그런 선택을 했을까이다.

물론 삽입과 제거에 대한 규칙도 추가할 예정이지만,
중점적으로 다뤄지는 것은 RBTree에 대한 보다 깊은 이해이다.

내 생각엔 보다 깊은 이해를 못할 확률이 높을 거 같지만
일단 부딪혀본다.

RB Tree의 길이

레드블랙 트리는 이진트리이며 균형트리에 가까운 트리이다.
균형트리에 가깝다는 얘기는 완벽한 균형트리는 아니라는 얘기다.

우선 RB트리의 규칙 4번과 5번을 살펴보겠다.

빨간색 노드의 자식은 반드시 검은색이다.
어떤 노드에서 리프 노드까지 가는 모든 경로에는 같은 개수의 검은색이 있다.

이 규칙을 이해하면 RB트리의 가장 짧은 경로와 가장 긴 경로의 차이에 대해 이해할 수 있을 것이다.
우선 RB트리의 모든 경로는 같은 개수의 검은색이 있다.

Q. 그렇다면 가장 짧은 경로는 어떤 특징을 가질까?
A. 바로 모든 노드가 검은색인 경우이다.

Q. 그렇다면 가장 긴 경로는 어떤 특징을 가질까?
A. 바로 모든 검은 노드 사이에 빨간 노드가 있는 경우이다.

그림으로 보면 다음과 같다.
중간에 있는 노드들은 생각하지 말고 양 끝의 노드만 생각하자.

최악의 시간 복잡도가 되기 위한 조건은 무엇일까?
이건 이진 트리를 생각해보면 답이 나온다.

(1번이 루트 노드이다.)
최소 노드 개수에 최대 탐색 수가 되면 최악의 시간 복잡도가 될 것이다.
그렇다면 레드블랙 트리에서 최소 노드 개수는 어떻게 정해질까?

우선 최대 탐색 수는 3번부터 8번까지 가는 경로일 것이다.
그리고 최소 노드가 되려면 나머지 2번, 4번, 5번 ... 노드에 검은색 노드만 달려야 한다.

그럼 이제 점화식을 만들어보자.
최악의 상황일 때 레드블랙트리가 가진 노드 규칙이 있을까?

그리기 힘들었다...
위 그림을 보면 4, 5번 규칙이 레드블랙트리의 최대 깊이와 최소 깊이의 차이를 조절하고 있다는 것을 알 수 있다.

위 트리의 노드 개수 규칙을 찾기 전에 짚고 넘어갈 부분이 있다.
바로 꽉찬 완전이진트리의 높이가 h일 때 노드의 개수다.
총 노드의 개수를 t이라고 할 때
다음과 같은 관계가 성립한다.

h = 2, t = 3

   O
  / \
 O   O

h = 3, t = 7

       O
     /   \
    O     O
  /  \   /  \
 O    O O    O

...

h(높이)	t(노드 개수)
1	1
2	3
3	7
4	15
...	...

즉 높이가 h일 때 t는 2h-1이다.
그리고 다시 그림을 보면

위와 같이 겹치는 부분이 있다는 것을 알 수 있다.
해당 트리는 가장 오른쪽 경로의 노드가 8개인 트리이고
높이가 3인 트리 2개, 2인 트리 2개, 1인 트리 2개, 0인 트리 2개인 것을 알 수 있다.

레드블랙트리에서 오른쪽 경로 노드가 2n이라고 할 때 최악의 경우 총 노드의 개수는
$2n + (2^{n-1}-1)*2 + (2^{n-2}-1)*2 + ... + (2^1-1)*2$
임을 알 수 있다.
이 식을 정리해보자

$2n + (2^{n-1}-1)*2 + (2^{n-2}-1)*2 + ... + (2^1-1)*2$
$= 2n + 2^n-2 + 2^{n-1}-2 + ... + 2^2-2$
$= 2n + 2^n-2 + 2^{n-1}-2 + ... + 2^2-2$
$= 2n - 2(n-1) + 2^n + 2^{n-1} + ... + 2^2$
$= 2n - 2n + 2 + 2^n + 2^{n-1} + ... + 2^2$
$= 2^n + 2^{n-1} + ... + 2^2 + 2^1$

$S = 2^n + 2^{n-1} + ... + 2^2 + 2^1$

$2S = 2^{n+1} + 2^n + ... + 2^3 + 2^2$
$S = 2^{n} + 2^{n-1} + ... + 2^2 + 2^1$

$S = 2^{n+1} - 2$
즉, 레드블랙 트리에서 오른쪽 노드 경로가 2n이면 노드의 총 수는 $2^{n+1} - 2$ 가 된다.
오른쪽 경로의 맨 아래쪽 노드로 가는 건 최악의 탐색 경우라고 할 수 있다.

다시 말해 자료의 크기가 $2^{n+1} - 2$ 일 때 최악의 탐색 시간은 2n이다.
최악의 탐색 시간 T(N) = 2n 이고
$N = 2^{n+1} - 2$ 이다.
$log(N+2) = (n+1)$
$n = log(N+2) - 1$
$T(N) = 2log(N+2) - 2$

따라서 O(logN)의 복잡도를 갖는다고 할 수 있다.

삽입 고찰

삽입 규칙은 간단하다.
기본적으로 이진트리 규칙을 통해 리프노드를 찾아간 뒤
해당 리프노드(nil노드)를

얘로 바꿔준다.
이후 두 가지 경우로 나뉘게 되는데

1. 부모가 검은색인 경우

=> 그냥 추가

-트리 규칙을 위배하지 않으므로 그냥 추가하면 된다.
(1) 경로 상의 검은색 노드 개수가 달라지지 않았고
(2) 검은색 노드의 자식이이기 때문이다.

2. 부모가 빨간색인 경우

부모가 빨간색인 경우에는 어떻게 해야할까?

이 경우, 규칙(빨간 노드의 자식은 무조건 검정)을 위배하므로 수정이 필요하다.

딱히 중요한 건 아닌데
규칙이 적용된 트리에서는 삽입하려는 노드의 부모가 빨강이라면 형제는 무조건 nil 노드이긴 하다.
형제가 '값이 있는 빨강'은 절대 아니며, '값이 있는 검정'이면 경로상 검정 수에 위배되기 때문이다.

쉽게 말해 빨강 노드를 삽입하기 전 이런 상황이었다는 건데 말이 안된다.
아무튼

가장 기본적인 상황부터 생각해보자.
1. 루트 노드가 존재하고
2. 우리는 새로운 노드를 삽입하려 한다.

그러나 루트 노드는 항상 검은색이다. 부모가 빨간색이면 루트 노드가 될 수 없다.
따라서 '부모 노드'의 '부모 노드'가 존재한다고 볼 수 있다.
최소 조부모 노드까지 있다는 얘기이며, 조부모 노드의 색은 당연히 검은색이다.

그럼 다음 상황을 가정해보자.
1. 루트 노드가 있고
2. 부모 노드를 삽입한 뒤
2. 새로운 자식 노드를 삽입하는 과정이다.

우리는 이제 결정을 내려야 한다. 조부모 노드가 루트 노드라고 가정할 경우
이 규칙을 해결하기 위해 수를 써야한다.

부모나 자식을 검은색으로 바꾸는 것은 의미가 없다.
앞서 설명했던 O(logN)을 위해 기껏 정해둔 규칙이 쓸모가 없어지기 때문이다.
(예를 들면 블랙의 깊이와 관련된 규칙 같은거 말이다.)

따라서
위 그림에서 될 수 있는 가장 이상적인 상황은

얘다. 루트는 검은색이 돼야하고 검정의 깊이도 같아야 하기 때문이다.
그렇다면 우리는 얘를 만들기 위해 어떻게 해야할까?

일단 크기 관계는 조부모 < 부모 < 자식이다.
이를 고려하면
루트 노드에는 부모 노드가 들어가고
왼쪽 노드에는 조부모가
오른쪽 노드에는 자식이 들어간다.

쉽게 말해 조부모가 부모 노드의 왼쪽 자식이 된 것이다.

근데 여기서 중요한 사실이 있다.
바로 검은색의 위치다.

루트에 가까운 검은색 노드일수록 더 많은 경로의 검정 개수에 관여한다.
무슨 말이냐면

이 사진에서 '파란색 박스의 노드'와 '주황색 박스의 노드'는 그 중요성?이 같다고 할 수 있을까?
위 상황에서 파란색 박스의 검은색 노드가 빨간색 노드로 바뀐다고 하면

위 그래프에서 위배한 것은 오로지 4번 (빨간 노드 자식 검정) 규칙이다.

엥? 검은색 노드가 빨간색 노드로 바꼈는데 왜 5번 (검정 깊이) 규칙이 위배가 아니냐고?
그 이유는, 루트 노드는 모든 경로의 검은색 노드 개수에 관여하기 때문이다.

왜 이 이야기를 하냐하면 아까 트리에서 조부모와 부모를 조정하는 이유는 오로지 자식 노드 때문이다.

위치를 조정하기 전 상황에서, 새로 삽입하는 노드(자식 노드)를 제외하면 모든 경로의 검정 개수가 같다.
근데 이 둘의 위치를 바꿔버리면 경로상 검은색 개수에 큰 변화가 생길 것이다.
특히 조부모는 더 위쪽에 위치한 검은색 노드이다.
따라서 위치를 조정할 때, 검은색 역시 유지를 시켜줘야 한다.

조부모의 왼쪽, 부모의 오른쪽에 n개의 검은색 노드가 있다고 상상해보자.
가운데 노드는 헷갈리니 뺐다. 크게 상관없긴 하다.
여기서 조정이 이뤄지면

부모 노드는 검은색 노드를 하, n개를 유지하면서 n-1개를 n개로 변경할 수 있는 방법은

검은색과 빨간색을 바꾸는 방법 밖에 없다.

따라서

사실 회전으로 설명하는게 더 직관적이긴 하다.
근데 이 방법이 마냥 다 통하는 것은 아니다.
그래서 레드블랙트리가 어렵다.

항상 4번 규칙을 조심해야한다.
누군가를 빨간색으로 바꾼다는 것은 그 누군가의 자식이나 부모가 빨간색은 아닐지 생각해야하기 때문이다.

쉽게 말해 3번 그림에다가 새로운 노드를 또 넣는다고 가정해보자.
이렇게

아까의 방법을 마냥 따라하다간

이렇게 된다.
부모 노드의 형제 노드를 삼촌 노드라고 한다.
삼촌 노드가 빨간색이면 이 규칙을 적용하기가 어렵다.
삼촌을 관측해야 우리의 행동을 확정지을 수 있으므로 슈뢰딩거의 삼촌이라고 볼 수 있다.

그렇다면

이 상황을 타개할 가장 좋은 방법은 뭘까?

바로
검은색을 바꿔서 칠하는 것이다.

이렇게 되면 검은색 노드 깊이는 문제가 없다.
아래 두 가지 사진을 비교해보며 생각해보자.

근데 그럼 루트 노드가 빨간색이 아니냐? 할 수 있다.
그럼 루트 노드를 검은색으로 칠하면 된다.

새로 삽입하는 노드는 무조건 빨간색이니
트리의 높이가 증가하게 되면
자연스레 검은색 노드의 수도 많아지게 된다.

이제 안쪽에 자식 노드가 달릴 때에 대해서 생각해보자.

이런 형태도 있을 것이다.
이때는 그럼 어떻게 할 것인가?

크기 관계가 조부모 < 자식 < 부모 이므로

이렇게 되는 것이 가장 이상적일 것이다. (물론 색에 대한 규칙을 제외하고 말이다.)
따라서 자식이 부모의 부모가 돼야 한다.
자식이 부모의 부모가 되려면 회전을 해야한다.

여기서는 부모가 조부모의 부모가 됐으므로
조부모를 중심으로

이런 회전을 했다.
그럼 마찬가지로 자식이 부모의 부모가 되려면
부모를 중심으로 회전하면 된다.

삽입 케이스 정리

1. 부모가 검은색

그냥 추가

2. 부모가 빨간색

삼촌을 관측한다.

2-1. 삼촌이 검은색

2-1-1. 자식이 바깥쪽 노드

조부모 노드 기준으로 노드 추가한 쪽의 반대쪽으로 회전

색 바꾸기

2-1-2. 자식이 안쪽 노드

부모 노드를 추가한 방향의 반대쪽으로 회전

나머지는 2-1-1과 같음.

2-2. 삼촌이 빨간색

색을 교체한다.

2-2-1. 할아버지의 부모가 빨간색

할아버지의 할아버지와 할아버지의 부모의 색을 교환한다.

재귀적으로 반복한다.

2-2-2. 할아버지가 루트 노드

루트 노드 색을 검은색으로 교체한다.

삭제 고찰

레드블랙트리가 어려운 이유는 사실 얘 때문이다.
본격적으로 파헤쳐보자.

먼저 삭제 방법은 BST와 같다.
전임자/후임자와 교체 후 삭제하면 된다.

잊을만 하면 나오는 친구다.
저 빨간 노드를 삭제한다고 하면

저 화살표에 해당하는 노드 중 하나와 값을 바꾼 뒤 (색은 바꾸지 않는다.)
삭제하면 된다.

삭제하는 경우에는 이미 트리의 구조가 완성된 상태이기 때문에
중점적으로 봐야하는 것은 경로 상 검은색 노드의 개수이다.

1. 삭제하는 노드가 빨간색인 경우

저 노드를 삭제해도 검은색 노드의 개수에 영향을 주지 않으니 바로 삭제하면 된다.

2. 삭제하는 노드가 검은색인 경우

여기서 빨간 부분을 확대해서 고찰해보자

여기서 검은색 노드를 하나 삭제할 경우

저 빨간 부분에 대해서 경로상 검은색이 1개가 부족하게 된다.
그럼 우리는 그 검은색을 어떻게 처리할 지 생각해봐야 한다.
아마 두 가지 방법이 있을 것이다.

다른 모든 검은색을 하나씩 없애거나
노드는 비록 삭제됐지만, 검은색이 있다치고 그 검은색을 누군가를 주거나

생각해봤을 때 무엇이 더 간단할 것 같나?
아마도 2번일 것이다.

왜?
1번은 고려할 것이 너무 많아진다.

첫 번째로 삭제한 경로 이외의 모든 경로의 검은색을 삭제하려면 부모 노드를 타고 가면서 경로 이외의 검은색 노드를 하나씩 빨간색으로 교체해야 하고,
두 번째로 만약 빨간색으로 교체한다면 빨간색 부모-자식 규칙을 계속 체크해야 할 것이다.

따라서 2번이 훨씬 수월하다.
적당한 빨간색을 가져와서 검정색으로 칠해버리거나
정 안되면 루트에서 없애버리면 되기 때문이다.

그리고
얘를 처리하기 위한 여행이 레드블랙트리 삭제 여행이다.

검정색을 처리하는 방법은 결론적으로 두 가지이다.

루트 노드로 가서 그냥 사라지거나
빨간색을 검은색으로 덮어쓰거나

그래서 빨간색이 근처에 있는지 눈 시뻘겋게 뜨고 찾는게 레드블랙트리 삭제 케이스이다.
최대한 다른 경로에 영향을 주지 않아야 되고, 루트 노드로 가면서 재귀적으로 해결해야 한다.

우선 삭제하는 노드가 빨간색인 경우에 대해서는 생각해봤으니,
지금 삭제하는 노드는 항상 검은색 노드일 것이다.(nil 노드인 경우에도 마찬가지 일 것이다.)
결국 처리하는 방법은 똑같기 때문에 그냥 검은색 노드를 쓰겠다.

그리고 검은색에 또 검은색이 추가된 노드를 doubly black이라고 표현하는데
재미없으니

검은 위성을 달았다고 생각하자.
얘를 스윙바이로 다른 곳으로 보낼 것이다.

주변에 빨간색이 있는 경우에는 어떤 경우가 있을까?
확실한 이해를 위해 회색 노드는 색을 알 수 없는 노드라고 하겠다.

0. 경우

경우 1. 형제가 빨간색

경우 2. 형제의 안쪽 자녀가 빨간색

경우 3. 형제의 바깥쪽 자녀가 빨간색

경우 4. 다 검은색

그림들을 봤을 때 가장 빠르게 문제를 해결할 수 있는 경우는 어떤 경우일까?

바로 경우 4이다.
혹시
1.

이 사진이 기억이 나는가?

부모 노드에서 자식 노드로 검은색을 전달하면 왼쪽 오른쪽으로 하나씩 나눠졌다.
이 반대도 성립한다.
무슨 말이냐면

왼쪽의 검은색 하나와 오른쪽의 검은색 하나를 위로 올려주면 된다.
그럼 형제 검은색은 어떻게 되냐고?
빨간색으로 바꿔주면 된다!
그 어떤 규칙에도 위배되지 않는다.

회색이 어떤 색인지 모르는데 어떻게 규칙에 위배되지 않냐고?

앞서 얘기했던 검은색을 처리하는 방법이 기억나는가?

루트 노드로 가서 그냥 사라지거나
빨간색을 검은색으로 덮어쓰거나

이 두 가지를 다 만족시킬 수 있는 방법이다.
회색 노드의 경우를 다 따져보자.
자식 경로의 검은 노드 개수를 n개라고 하자.

1. 경우 4 고찰

경우 4-1. 부모 회색 노드가 빨간 노드일 경우

아주 행복한 결말이다.

경우 4-2. 부모 회색 노드가 검은 노드일 경우

루트 노드에 한 층 가까워졌다.

이번엔 각 경우에 대해서 검은 위성을 그냥 줘보겠다.
그냥 어떻게 될 지 궁금하다.

스윙바이 경우 1.

스윙바이 경우 2.

스윙바이 경우 3.

여기서 또 한 경우를 골라보자.
사람 이름 같다.
한경우
스윙바이 경우 3을 잘 살펴보면

저 초록색으로 표시한 것을
'반대쪽 검은색 노드'와 '회색 부모 노드' 사이에 두면
그 어떤 규칙을 위배하지 않을 것 같지 않은가?

이렇게 똑 떼면 오른쪽 노드는 n개로 변하고

왼쪽에 넣으면 모든 규칙을 만족한다.
(물론 이진 트리의 규칙을 잘 지키면서 넣어야 한다.)
그러면 어떻게 진행해야할지 한 번 보자.

2. 스윙바이 경우 3 고찰

여기서 먼저 회색 부모 노드를 기준으로 회전한다.

그럼 반대쪽(왼쪽) 검은색 노드의 자식은 n개의 경로상 검정을 가지고
바깥쪽(오른쪽) 검은빨간은 n+1-?로 변한다.
왜냐하면 회색이 검은색인지 아닌지 모르기 때문이다.

검은색이면 n+1-1이고
빨간색이면 n+1-0이다.
근데 그건 진짜 중요하지 않다.
바로 다음 장면 때문이다.

회색이랑 검은색이 바뀌면
바깥쪽(오른쪽/검은빨간) n+1-?에 -1(검은색 내려감)+?(회색 올라옴)
즉, n+1-?-1+? = n이 된다.
지금 보이는건 검은색 밖에 없기 때문에 문제가 없다.

또 확인할 수 있는 건, 다른 회색 노드들의 트리를 정상화하는데 영향을 주지 않았다는 사실이다.
경우 3에서 바깥쪽 자식이 빨간색이면 무조건 사용할 수 있다는 것을 의미한다.

이제 알았을 것이다.
우리의 여정은 경우 3과 경우 4를 위한 여정이다.

그렇다면 경우 3으로 만들기 위한 친구들이 있을까?
바로 경우 2이다.

여기서 '빨간색 노드'가 '형제'의 '바깥쪽(오른쪽) 자식 노드'가 되면 정말 좋을 것 같다.
그리고 앞서 설명했듯

이 경우는 무조건
정상화 시킬 수 있기 때문이다.

그러면 경우 2를

자연스레 이렇게 생각해도 될 것이다.

복면가왕의 복면이 벗겨지는 순간이라고 할 수 있다.

3. 경우 2 고찰

우선 형제를 기준으로 바깥쪽(오른쪽) 회전한다.

하나가 모자라게 되는데 별거없다.

올리면 해결이다.

이제 하나 남았다.

4. 경우 1 고찰

얘도 뭔가 스윙바이 경우 3과 비슷한 느낌이다.

똑 떼서

요렇게 붙인다.
그럼 아무튼 형제 노드가 검정색이 되고
자식이 어떻게 되느냐에 따라 경우 2나 스윙바이 경우 3이 될 것이다.

해보자.

회색 부모 노드를 중심으로 좌회전하면

맨 오른쪽 노드빼고 n개를 유지한다.
n-?을 정상화 해줘야하므로

빨간색과 회색을 교체한다.
n-?+? = n 으로 다시 만들어준다.

삭제 케이스 정리

1. 형제가 빨간색

경우 1

회색 부모 노드를 중심으로 검은 위성 있는 쪽으로 회전

형제와 부모 색깔 교체

경우에 따라 경우 2, 3, 4로

2. 형제가 검은색

2-1. 형제의 안쪽 자식이 빨간색, 바깥쪽 자식이 검정색

경우 2

형제 노드 바깥쪽 회전

형제와 안쪽 자식 색 교체

경우 3으로

2-2. 형제의 바깥쪽 자식이 빨간색

경우 3

회색 부모 노드 검은 위성쪽 회전

회색 부모와 형제 노드 색깔 교체

완성

2-3. 형제의 자식이 검은색

경우 4

경우 4-1. 부모 회색 노드가 빨간 노드일 경우

양쪽 자식의 검은색을 부모로 전송. 형제는 빨간색

부모 색깔 교체

완성

경우 4-2. 부모 회색 노드가 검은 노드일 경우

양쪽 자식의 검은색을 부모로 전송. 형제는 빨간색

부모는 검은 위성이 달림

경우에 따라 경우 1, 경우 2, 경우 3, 경우 4로
만약 검은 위성이 루트 노드에 달릴 경우 검은 노드는 그냥 사라짐.

뭔가 만들었던 사진을 다시 캡쳐해서 도형을 다시 넣으니
화질구지가 돼 버렸다.

출처: 나무위키

...

끗!

아래는 알고리즘 로드맵이다.

코드

#include "rbtree.h"

#include <stdlib.h>
#include <stdio.h>

rbtree *new_rbtree(void) {
  // TODO: initialize struct if needed
  rbtree *p = (rbtree *)calloc(1, sizeof(rbtree));
  node_t* nil = (node_t*)malloc(sizeof(node_t));
  //nil black initiate 
  nil->color = RBTREE_BLACK;
  nil->parent = nil->left = nil->right = NULL;
  //root Null initiate
  p->root = nil;
  p->nil = nil;
  return p;
}

void delete_rbtree(rbtree *t) {
  // TODO: reclaim the tree nodes's memory
  free(t);
}

node_t *rbtree_insert(rbtree *t, const key_t key) {
  //새 노드 생성
  node_t* newNode = make_new_node(t, key);
  //루트 노드를 가리키는 이중 포인터
  node_t** nodePtrAddress = &(t->root);
  //노드 삽입
  insert_node(t, nodePtrAddress, newNode);
  //노드 수정
  node_t* targetNode = newNode;
  insert_fixUp(t, targetNode);
  return newNode;
}

//새 노드를 만드는 함수
node_t* make_new_node(rbtree* t, const key_t key) {
  node_t* newNode = (node_t*)malloc(sizeof(node_t));
  newNode->key = key;
  newNode->color = RBTREE_RED;
  newNode->right = t->nil;
  newNode->left = t->nil;

  return newNode;
}

//노드 삽입 함수
void insert_node(rbtree* t, node_t** nodePtrAddress, node_t* newNode) {
  //부모 노드를 닐노드로 설정
  node_t* parentNode = t->nil;
  //가리키고 있는 노드의 값이 닐노드 주소가 아닌 동안(닐노드 가리키는 노드 포인터가 나올 때까지)
  while (*nodePtrAddress != t->nil) {
    //부모 노드는 현재 노드로 설정
    parentNode = *nodePtrAddress;
    //값이 같을 떄는 오른쪽으로
    if ((*nodePtrAddress)->key <= newNode->key) {
      //이중 포인터에 오른쪽 가리키는 포인터 주소 할당
      nodePtrAddress = (&(*nodePtrAddress)->right);
    } else {
      //이중 포인터에 왼쪽 가리키는 포인터 주소 할당
      nodePtrAddress = (&(*nodePtrAddress)->left);
    }
  }
  //가리키는 주소가 닐노드면
  if (*nodePtrAddress == t->nil) {
    //가리키는 주소를 새 노드로 할당
    *nodePtrAddress = newNode;
    //새 노드의 부모에 부모 노드 할당
    newNode->parent = parentNode;
  }
}

//픽스업
void insert_fixUp(rbtree* t, node_t* nowNode) {
  if (nowNode->parent == t->nil) {
    //부모노드가 닐이면 루트이므로 블랙으로 변경 후 리턴
    nowNode->color = RBTREE_BLACK;
    return;
  } 
  else {
    //자신과 부모가 빨강일 때만 작동
    if (nowNode->color == RBTREE_RED && nowNode->parent->color == RBTREE_RED) {
      //조부가 루트인지 확인
      node_t** gGNode;
      node_t* gPNode = nowNode->parent->parent;
      node_t* pNode = nowNode->parent;
      //증조부 할당
      if (gPNode == t->root) {
        //증조부가 루트면 루트 주소 할당
        gGNode = &(t->root);
      } else {
        //조부의 위치에 따라 증조부의 왼쪽/오른쪽 주소 할당
        if (gPNode == gPNode->parent->left) {
          gGNode = &(gPNode->parent->left);
        } else {
          gGNode = &(gPNode->parent->right);
        }
      }
      //조부 노드의 오른쪽, 왼쪽 자식이 같은 경우(삼촌이 빨간색)
      if(gPNode->left->color == gPNode->right->color) {
        //조부와 자식의 색 변경
        gPNode->color = RBTREE_RED;
        gPNode->left->color = RBTREE_BLACK;
        gPNode->right->color = RBTREE_BLACK;
        //재귀
        insert_fixUp(t, gPNode);
      }
      //삼촌이 검정색인 경우
      else {
        //부모 노드가 조부모 노드의 왼쪽
        if (pNode == gPNode->left) {
          //자식 노드가 부모 노드의 오른쪽
          if (nowNode == pNode->right) {
            //자식 노드가 올라오면서 자동으로 로테이트 타겟 변경
            rotate_left(t, nowNode);
          } else {
            //로테이트 타겟 변경
            nowNode = nowNode->parent;
          }
          rotate_right(t, nowNode);
          //부모였던 노드와 색 변경
          nowNode->color = RBTREE_BLACK;
          nowNode->right->color = RBTREE_RED;
        }
        //부모 노드가 조부모 노드의 오른쪽
        else {
          //자식 노드가 부모 노드의 왼쪽
          if (nowNode == pNode->left) {
            //자식 노드가 올라오면서 자동으로 로테이트 타겟 변경
            rotate_right(t, nowNode);
          } else {
            //로테이트 타겟 변경
            nowNode = nowNode->parent;
          }
          rotate_left(t, nowNode);
          //부모였던 노드와 색 변경
          nowNode->color = RBTREE_BLACK;
          nowNode->left->color = RBTREE_RED;
        }
        //증조부 노드에 회전 결과 최상위 노드 연결
        *gGNode = nowNode;
        //만약 현재 노드가 루트 노드면 블랙
        if (nowNode->parent == t->nil) {
          nowNode->color = RBTREE_BLACK;
        }
      }
    }
  }
}

void rotate_left(rbtree* t, node_t* node) {
  //조부 주소 왼쪽/오른쪽 설정
  node_t** gPNodePtr = &(t->root);
  node_t* pNode = node->parent;
  if (pNode->parent != t->nil) {
    if (pNode == pNode->parent->right) {
      gPNodePtr = &(pNode->parent->right);
    } else {
      gPNodePtr = &(pNode->parent->left);
    }
  }

  //회전
  node_t* leftChild = node->left;
  node->left = pNode;
  node->parent = pNode->parent;
  pNode->parent = node;
  pNode->right = leftChild;
  if (leftChild != t->nil) {
    leftChild->parent = pNode;
  }

  //조부와 회전 결과 최상위 노드 연결

  *gPNodePtr = node;
}

void rotate_right(rbtree* t, node_t* node) {
  //조부 주소 왼쪽/오른쪽 설정
  node_t** gPNodePtr = &(t->root);
  node_t* pNode = node->parent;
  if (pNode->parent != t->nil) {
    if (pNode == pNode->parent->left) {
      gPNodePtr = &(pNode->parent->left);
    } else {
      gPNodePtr = &(pNode->parent->right);
    }
  }

  //회전
  node_t* rightChild = node->right;
  node->right = pNode;
  node->parent = pNode->parent;
  pNode->parent = node;
  pNode->left = rightChild;
  if (rightChild != t->nil) {
    rightChild->parent = pNode;
  }

  //조부와 회전 결과 최상위 노드 연결
  *gPNodePtr = node;
}


node_t *rbtree_find(const rbtree *t, const key_t key) {
  node_t* nowNode = t->root;
  while (nowNode != t->nil) {
    if (nowNode->key == key) {
      break;
    }
    else if (nowNode->key < key) {
      nowNode = nowNode->right;
    } 
    else if (key < nowNode->key) {
      nowNode = nowNode -> left;
    }
  }

  if (nowNode == t->nil) {
    return NULL;
  } else {
    return nowNode;
  }
}

node_t *rbtree_min(const rbtree *t) {
  node_t* nowNode = t->root;
  if (nowNode != t->nil) {
    while (nowNode->left != t->nil) {
      nowNode = nowNode->left;
    }
  }
  return nowNode;
}

node_t *rbtree_max(const rbtree *t) {
  node_t* nowNode = t->root;
  if (nowNode != t->nil) {
    while (nowNode->right != t->nil) {
      nowNode = nowNode->right;
    }
  }
  return nowNode;
}

int rbtree_erase(rbtree *t, node_t *p) {
  node_t* target = find_successor(t, p);
  //트리에 루트노드 밖에 없을 경우
  if ((target == p) && (t->root == target)) {
    t->root = t->nil;
    free(target);
    return 0;
  }

  //키 스왑
  int originalKey= p->key;
  p->key = target->key;
  target->key = originalKey;

  //삼촌 노드 설정 - 원노드가 nil이면 부모가 없음
  node_t* broNode = return_bro(t, target);
  color_t targetColor = target->color;
  erase_node(t, target);
  if (targetColor == RBTREE_BLACK) {
    erase_fixUp(t, broNode);
  }
  return 0;
}

node_t* find_successor(rbtree* t, node_t* node) {
  node_t* nowNode = node;
  if (nowNode->left != t->nil) {
    nowNode = nowNode->left;
    while (nowNode->right != t->nil)
    {
      nowNode = nowNode->right;
    }
  } 
  else if (nowNode->right != t->nil) {
    nowNode = nowNode->right;
    while (nowNode->left != t->nil)
    {
      nowNode = nowNode->left;
    }
  }
  return nowNode;
}

node_t* return_bro(rbtree* t, node_t* target) {
  if (target == t->root) {
    return target;
  }

  node_t* broNode;
  if (target == target->parent->left) {
    broNode = target->parent->right;
  } else {
    broNode = target->parent->left;
  }
  return broNode;
} 

void erase_node(rbtree* t, node_t* node) {
  node_t** pNode = NULL;
  //타겟의 부모 노드가 가리키는 곳 저장
  if (t->root == node) {
    pNode = &(t->root);
  } else if (node == node->parent->left) {
    pNode = &(node->parent->left);
  } else {
    pNode = &(node->parent->right);
  }

  //타겟의 자식 노드 찾기
  node_t* childNode = t->nil;
  if (node->left != t->nil) {
    childNode = node->left;
  } else if (node->right != t->nil) {
    childNode = node->right;
  }

  if (childNode != t->nil) {
    childNode->parent = node->parent;
  }

  //타겟의 부모가 가리키는 곳을 타겟의 자식 노드로 변경
  *pNode = childNode;
  free(node);
}

void erase_fixUp(rbtree* t, node_t* broNode) {
  //bro is root
  if (broNode == t->root) {
    t->root->color = RBTREE_BLACK;
    return;
  }

  if (broNode->color == RBTREE_RED) {
    erase_case_one(t, broNode);
  }
  else if (broNode->left->color == RBTREE_BLACK && broNode->right->color == RBTREE_BLACK) {
    erase_case_four(t, broNode);
  }
  else if (broNode == broNode->parent->left) {
    //outside
    if (broNode->left->color == RBTREE_RED) {
      erase_case_three(t, broNode, LEFT);
    }
    //inside
    else {
      erase_case_two(t, broNode, LEFT);
    }
  }
  else {
    //outside
    if (broNode->right->color == RBTREE_RED) {
      erase_case_three(t, broNode, RIGHT);
    }
    //inside
    else {
      erase_case_two(t, broNode, RIGHT);
    }
  }
}

void erase_case_one(rbtree* t, node_t* broNode) {
  color_t tmpParentColor = broNode->parent->color;
  color_t tmpBroColor = broNode->color;
  node_t* newBro;

  if (broNode == broNode->parent->right) {
    rotate_left(t, broNode);
    broNode->left->color = tmpBroColor;
    broNode->color = tmpParentColor;
    newBro = broNode->left->right;
  } else {
    rotate_right(t, broNode);
    broNode->right->color = tmpBroColor;
    broNode->color = tmpParentColor;
    newBro = broNode->right->left;
  }
  erase_fixUp(t, newBro);
}

void erase_case_two(rbtree* t, node_t* broNode, side_t side) {
  node_t* child;
  if (side == RIGHT) {
    child = broNode->left;
    rotate_right(t, child);
    broNode->color = RBTREE_RED;
    child->color = RBTREE_BLACK;
  }
  else {
    child = broNode->right;
    rotate_left(t, child);
    broNode->color = RBTREE_RED;
    child->color = RBTREE_BLACK;
  }
  erase_fixUp(t, child);
}

void erase_case_three(rbtree* t, node_t* broNode, side_t side) {
  color_t parentColor = broNode->parent->color;
  if (side == RIGHT) {
    broNode->right->color = RBTREE_BLACK;
    rotate_left(t, broNode);
    broNode->left->color = RBTREE_BLACK;
  }
  else {
    broNode->left->color = RBTREE_BLACK;
    rotate_right(t, broNode);
    broNode->right->color = RBTREE_BLACK;
  }
  broNode->color = parentColor;
}

void erase_case_four(rbtree* t, node_t* broNode) {
  //parent red
  if (broNode->parent->color == RBTREE_RED) {
    broNode->parent->color = RBTREE_BLACK;
    broNode->color = RBTREE_RED;
  } 
  //parent black
  else {
    broNode->color = RBTREE_RED;
    node_t* newBro = return_bro(t, broNode->parent);
    erase_fixUp(t, newBro);
  }
}

int rbtree_to_array(const rbtree *t, key_t *arr, const size_t n) {
  int index = 0;
  int* indexPtr = &index;
  preOrder(indexPtr, t, t->root, arr);
  return 0;
}

void preOrder(int* indexPtr, const rbtree* t, node_t* nowNode, key_t* arr) {
  if (nowNode == t->nil) {
    return;
  }
  preOrder(indexPtr, t, nowNode->left, arr);
  arr[*indexPtr] = nowNode->key;
  (*indexPtr)++;
  preOrder(indexPtr, t, nowNode->right, arr);
}

// printf("\n--------\n");
// print_rb_tree(t, t->root);

void print_rb_tree(rbtree* t, node_t* nowNode) {
  if (nowNode == t->nil) {
    return;
  } else {
    const char* color_names[] = {"RED", "BLACK"};
    printf("my: %d ", nowNode->key);
    printf("color: %s ", color_names[nowNode->color]);
    if (nowNode->left != NULL) {
      printf("left: %d ", nowNode->left->key);
    }
    if (nowNode->right != NULL) {
      printf("right: %d ", nowNode->right->key);
    }
    printf("//");
    print_rb_tree(t, nowNode->left);
    print_rb_tree(t, nowNode->right);
  }
}

모기

안녕

이전 포스트

C언어 lec

다음 포스트

Krafton Jungle Sixth

1개의 댓글

이시우

2025년 4월 22일

rb트리는 너무 징그럽습니다...

답글 달기