[RBTREE] Red-Black tree 레드블랙트리

bongf·2022년 5월 3일

정글

목록 보기

8/20

자가균형이진탐색트리란

레드블랙트리는 자가균형이진탐색트리(self-balancing binary tree)의 일종이다.

이진트리란

이진트리는 자식 노드를 최대 2개를 갖는 트리이다. (그림출처 위키)

이진탐색 트리

이진탐색트리는 탐색 작업을 효율적으로 하기 위한 이진트리이다. 한 노드를 기준으로
- 자신의 왼쪽 서브트리 노드의 키 값은 자신의 키 값보다 작아야 하고
- 자신의 오른쪽 서브트리 노드의 키 값은 자신의 키 값보다 큰 값을 갖는다.
- 그림 출처 위키
- 탐색하는 값이 7이라고 한다면 루트 8부터 시작해서 8보다 크므로 왼쪽, 그 다음 찾는 7이 3보다 커서, 3의 오른쪽, 그 다음 7이 6보다 커서 6의 오른쪽으로 가서 7을 찾는 방식이다. 남은 것들 중에서 대소 비교를 기준으로 절반을 날려버리기 때문에 아주 빠르게 찾을 수 있다.
이진탐색트리의 단점 :
- 이진탐색트리가 편향될 경우 실제로는 선형리스트가 되어 빠른 검색을 수행할 수 없다는 단점이 있다.

자가균형검색트리

자가균형검색트리 는 self-balancing search tree로 위와 같이 이진 탐색트리가 선형트리가 되지 않도록 (균형을 갖는 트리가 되도록) 노드의 삽입과 삭제를 할 때 전체 트리의 높이를 제한하는 이진탐색트리이다.
- 위키 를 보면 아래와 같은 균형 잡히지 않는 트리를 높이 제한을 둬서 밸런스를 맞췄을 때 맨 아래와 같이 됨을 알 수 있다.
레드블랙트리는 이 자가 균형 검색트리의 일종으로 노드의 삽입, 삭제시 노드가 균형잡힌 이진 탐색 트리가 될 수 있도록 한다.

레드블랙트리

레드블랙트리에 대한 학습은 유튜브 권오흠 교수님 강의와 위키 [책 Introduction to Algorithms]로 학습했다.
이진검색트리로 노드가 자신의 key값(key값으로 정렬)외에도 색깔에 관한 정보를 갖는다.(Red/Black)
- 레드블랙 트리는 이진 탐색 트리에서 오직 색깔 정보만 추가로 저장하므로 추가 메모리 비용이 거의 들지 않는다.
레드블랙트리는 탐색, 삽입, 삭제에 있어서 O( $\log_2 n$ ) 을 보장한다. (n은 노드의 개수)
- 자가 균형 탐색 트리(근사적인)로 높이가 항상 제한되기 때문에
- 루트에서 리프까지의 색깔이 제한되기 때문에 (빨간색은 연속해서 올 수 없고, 각 노드에서 도달할 수 있는 리프노드들까지의 검은색 노드의 수는 같다)

용어

NIL

레드블랙 트리에는 NIL (닐노드) 라는 용어가 등장한다.
실제 데이터를 갖는 트리는 아니며 구현의 편의성을 위해 모든 리프노드 끝에 NULL 대신 NIL을 가리키게 해 둔 것이다. 리프노드의 색은 black으로 한다.
그림출처 위키

노드 높이

일반 트리에서 높이와 같다.
권오흠 교수님은 자신으로부터 리프노드까지의 가장 긴 경로에 포함된 edge(간선)수라고 정의했다.

블랙 높이

노드 x로 부터의 블랙높이(bh)는 x에서 시작해서 리프노드까지 경로상의 블랙 노드의 수이다. (노드 x 자신은 포함하지 않는다)

레드 블랙 트리 정의

레드 블랙 트리는 다음 조건을 만족하는 이진 탐색 트리이다.
1) 각 노드는 red or black 이다
2) 루트노드는 black 이다
3) 모든 NIL 노드는 black
4) 모든 red 노드는 red 자식이 있으면 안된다(red 연속될 수 없다)
5) 한 노드로부터 자기 자신의 모든 자손 NIL노드까지 black 노드의 수는 같다.

bh는 자기 자신을 포함하지 않고 NIL의 블랙은 카운트에 포함한다
6데이터를 갖는 red 노드를 보면 6에서 3을 따라가는 경로로 계산해도 bh 는 2이고, 7을 따라가는 경로로 계산해도 bh 는 2이다 5번조건

그림 출처 : https://www.codesdope.com/course/data-structures-red-black-trees/
조건을 편하게 다루기 위해 모든 리프노드가 nil노드를 자식으로 갖고 루트노드도 동일한 nil노드를 부모로 갖도록 하는데 이 하나의 nil노드를 경계노드 (sentinel)이라고 한다.

레드 블랙 트리 속성

1) 높이가 h인 노드의 블랙 높이 bh는 h/2 이상이다.
- bh >= h / 2
- 레드노드는 연속될 수 없으므로
2) 노드 x를 루트로 하는 임의의 부트리는 적어도 2의 bh(x) 승 -1 개의 내부노드를 갖는다
- 이는 수학적 귀납법으로 증명할 수 있다.
- bh가 1일 때, 성립한다.
- bh가 1보다 큰 임의의 x에 대해 x의 서브트리에 대해 이가 성립할 때 x에 대해서도 성립한다면 이는 증명된다
  - x가 블랙노드라면
    - x의 자식노드를 루트로 하는 부트리는 x의 bh - 1 라는 bh를 갖는다
    - x의 자식노드를 루트로 하는 부트리에 대해 성립한다고 가정하면 왼쪽 자식 부트리는 2의 bh(x) - 1 승 -1 개의 내부노드를 갖고 왼쪽, 오른쪽자식 노드가 있을 때 결국 n은 이에 대해 성립함이 보인다.
  - x가 레드노드라면
    - x의 자식노드를 루트로 하는 부트리는 x의 bh개의 (bh(x)) 라는 bh를 가지므로 이는 위의 경우보다 많은 경우다. 그래서 역시 이 경우에도 성립한다.
n개의 내부노드를 가지는 레드블랙트리의 높이는 $2log_2(n+1)$ 이하이다. 위의 두가지 속성을 이용하면 알 수 있다
이것이 의미하는 바는 결국 시간복잡도가 $log_2n$ 이 보장된다는 말!

Left and Right Rotation

rotate 해도 원래 이진 탐색 트리였다면 그대로 이진 탐색 트리로 유지된다. (수의 대소 비교는 변하지 않는다)
그러나 red-black tree였다고 해서 -> left, right rotate 했을 때는 그 결과가 red-black tree라고 보장되지 않는다
시간복잡도 O(1)

LEFT-ROTATE(T,x)
y = x:right // set y
x:right = y:left // turn y’s left subtree into x’s right subtree

if (y:left != T:nil) :
 	y:left:p = x
y:p = x:p // link x’s parent to y

if (x:p == T:nil) :
 	T:root = y
elseif (x == x:p:left): //x가 부모의 왼쪽 자식이면
	x:p:left = y //부모의 왼쪽자식(원래 x를 y로 설정)
else 
	x:p:right = y //x가 부모의 오른쪽 자식을 때 처리
y:left = x // put x on y’s left
x:p = y

출처 : 책, Introduction to Algorithms

Search

이진탐색트리의 search랑 같다.
- 찾다가 null 이 되었을 때 혹은 해당 키를 찾았을 때 반환한다.
- 찾고자 하는 값보다 해당 노드가 컸을 때는 해당 노드의 왼쪽으로 이동하고, 같은 탐색을 수행.
- 찾고자 하는 값보다 해당 노드가 작았을 때는 해당 노드의 오른쪽으로 이동한다.

파이썬, 자바로 구현한 이진 검색트리

Insert

이진탐색트리의 insert 할 때처럼 들어갈 자리를 찾는다.
z는 항상 leaf 노드니까 z의 left, right는 nill.
처음 INSERT는 무조건 RED로 한다
RED로 INSERT했을 때 위반 가능성 있는 조건은

-	1) 각 노드는 red or black 이다
-	2) 루트노드는 black 이다 
-	3) 모든 NIL 노드는 black
-	4) 모든 red 노드는 red 자식이 있으면 안된다(red 연속될 수 없다)
-	5) 한 노드로부터 자기 자신의 모든 자손 NIL노드까지 black 노드의 수는 같다.

조건별로 따져 보면
- 1번 문제 없다
- 2번. 만약 루트라면 BLACK으로 바꿔주고 끝
  - 이것은 꼭 EMPTY tree가 아니더라도 다른 조건은 다 만족하고 ROOT만 RED라 하면은 RED -> BLACK으로 바꿔주면 된다
  - 루트를 블랙으로 바꾸면 5번 괜찮을까?
    - 네. 어차피 루트니까 (자기 자신은 포함x) 모든 경로에 영향 없다.
- 3번 문제 없다
- 4번 해결해야 한다. 위반될 가능성 있음
- 5번 문제 없다. 맨 끝자리에 노드를 추가하고 그것이 RED 이기 때문에 영향 X

INSERT시에 4번 해결하기

지금 4번 문제는 RED를 삽입했을 때 RED-RED 되는 것
문제 접근 방식.
- heap과 같이 문제가 되는 RED-RED를 위로 쪽 올려서 중간에서 RED-RED가 소멸되게 하거나, 루트까지 올려서 루트가 RED면 BLACK으로 바꿔주면 문제해결

해결방법 6경우

CASE 1, 2, 3 : parent[z]가 parent[parent[z]]의 왼쪽자식일 때
CASE 4, 5, 6 : parent[z]가 parent[parent[z]]의 오른쪽자식일 때

RB-INSERT-FIXUP(T, z)
1 while z:p:color == RED
2 	if z:p = = z:p:p:left //z가 왼쪽 자식일 때
3 		y = z:p:p:right //삼촌
4 		if y:color == RED
5 ´			z:p:color = BLACK // case 1
6 			y:color = BLACK // case 1
7 			z:p:p:color = RED // case 1
8 			z = z:p:p // case 1
9 		else if z == z:p:right
10 			z = z:p // case 2
11 			LEFT-ROTATE.(T,z) // case 2
12 		z:p:color D BLACK // case 3
13 		z:p:p:color D RED // case 3
14 		RIGHT-ROTATE.T; ´:p:p/ // case 3
15 	else (same as then clause with “right” and “left” exchanged)
16 T:root:color = BLACK

출처 : 책, Introduction to Algorithms

CASE 1 : z의 삼촌이 red

나도 레드, 부모도 레드, 부모의 형제도 red
할아버지는 당연히 black. 연속된 red 안되니까
1) 내 아버지와 삼촌의 칼라와 할아버지의 칼라 switch
2) 그리고 할아버지를 z로 바꿔준다.
애초의 red-red는 해결되었고
이 알파 , 베타, 감마 , 델타, 옵실론.. 얘네 입장은 문제가 없다. 부모가 black으로 바뀌어? 위반될 조건 없다.
문제는 할아버지의 할아버지가 레드일 경우 문제가 생길 수 있다. RED-RED violation 이게 아까 말했던 red red violation이 트리 위쪽으로 따라 올라간다는 말
5번은 문제 없다. 위에서 내려올 때 이전이나 지금이나 하나의 black 노드를 만난다는 건 똑같다. 그게 c에서 a, b로 나뉘어졌을 뿐

CASE 2, 3 : z의 삼촌이 black

내가 내 부모의 오른쪽 자식인 것이 case2, 왼쪽 자식인 것이 case 3.
여기 삼촌을 동그라미로 안 그린 이유는 black이므로 nil 일 수도 있는 것
case 2인 경우 내가, 내 부모의 오른쪽 자식인 경우, z를 내 부모로 두고, 부모 노드(z) 중심으로 left-roation을 한다. 이러면 CASE3가 된다
case 3가 되면 내 부모와 할아버지 색을 exchange. 그런 다음 할아버지를 중심으로 right-rotation을 한다.
이렇게 하고 나면 밑부터 생각해보면 알파 , 베타, 감마 입장에서 원래 내부모 레드였는데 그대로 red.
- 델타 입장에서는 부모가 black -> red 이지만 자신이 black이기 때문에 (케이스 조건) 문제 없다.
a-b, a-c 간에도 red-red 문제가 없다.
b위치는 원래 black이었는데 그대로 black 이므로 red-red 문제가 없다.
5번 블랙 하이트 이슈도 꼼꼼히 따져보면 문제 없음을 알게 된다.
나) red노드에 관해서는 red-red 이슈만 보면 되고 black에 관해서는 path 의 끝인 nil까지 블랙 개수만 신경쓰면 되네

정리

case2의 경우 한번의 left-rotation으로 case3로 넘어가고, case3인 경우 한번의 right-rotaion으로 해결. (그리고 색깔 바꾸고)
case1의 경우에는 red-red가 두 칸 위로 올라가는 거였(다시 case1 2, 3, 4, 5, 6 넘어갈 수도 (case 4-> 1,2,3) 로 갈 수도 있고)
최악의 경우는 case1이 루트까지 올라가는 것 -> 루트가 레드가 되면 문제 해결 되므로
while문을 빠져나오는 조건은 만약 case3, case6으로 빠져나오면 모든 문제 해결 된거고, case1반복하다가 나오면 루트가 레드인 상태로 나온 것일 수 있다. 그래서 맨 마지막에 루트의 색을 블랙으로 바꾼다 (3,6에서 끝난 것이라면 해당 안되겠지만 그래도 그냥 해준다)
예제 4 인서트 하기

DELETE

보통의 BST처럼 DELETE 한다.
1) 해당 노드를 search로 찾는다 (같은 key 값을 가진 노드)
- 2) 삭제하려는 노드를 y에 저장한다
- 1) 삭제하려는 노드가 자식이 0, 1 이라면 그대로 해당 노드를 삭제할 것
- 2) 삭제하려는 노드가 자식이 2라면 successor(해당 노드의 오른 쪽 서브트리에서 가장 작은 값) 혹은 predecessor?(해당 노드의 왼쪽 서브트리에서 가장 큰 값)을 삭제하려는 노드 y로 삼는다
- 3) y(삭제할 노드, 자식은 0, 1)읜 왼쪽 자식이 있으면 x에 왼쪽 자식을 없으면 x에 오른쪽 자식을 넣는다 (x는 null일 수 있다)
- y의 부모를 x의 부모로 두고
- y가 루투였다면 x를 루트로 두고
- y가 루트가 아니었다면 y가 부모의 왼쪽 자식이었다면 y 부모의 왼쪽자식을 x로 두고, y가 부모의 오른쪽 자식이었다면 y 부모의 오른쪽 자식을 x로 둔다.
만약에 우리가 삭제한 노드(y)가 red였다면 그것으로 끝내면 된다.
- 조건별 문제 없는지 보자.
y의 color가 블랙이었다고 한다면,
- 루트일 경우 문제가 되고
- r-b-r 이었는데 중간에 b가 삭제되서 r-r 문제
- 가장 심각한 문제는 black height. 중간에 black이 빠지니까
이런 문제를 r-b-delete-fixup(T, x) 할 것 여기보면 매개 변수로 node x를 넘겨준다. 왜냐하면 y는 이미 삭제된 노드니까 그걸 넘겨주는 것은 의미 없다. node x는 우리가 삭제한 노드의 자식 노드
삭제한 노드의 자식이 (x) red라면 쉽게 문제 해결 가능
어차피 y는 자식이 한 명이었어서 black으로 만들어주면 아무 문제 없어.
실제로 문제가 되는 경우는 x도 블랙인 경우 (y도 블랙), 또하나 x가 null 노드 일 수도 있다 (y가 자식이 없을 경우)

x, y가 둘 다 불랙

일단 x에게 까만공 2개를 줘서 어거지로 일단 해결 (black height 문제는 어거지로 해결)
위로 올려보내고, 거기서도 소화가 안되면 또 위로 올려보내고 내가 공을 올려 보낸 쪽이 red라면 이제 black, black이 아니라 red, black이 되면서 그러면 기존의 red를 버리고 보통의 블랙으로 만들어 주면 된다.
만약 루트까지 올라간다면 (최악의 case) 루트는 b니까 루트가 bb 더블블랙이면 그냥 하나를 제거하면 된다.
loop 조건
- x가 루트가 아니면서 double-black 이다
- w는 x의 형제노드
- w는 nill 노드가 될 수 없다
- x는 지금 까만 공 두개 인데 w가 nill 이면 갯수가 안맞지

해결에 관한 8가지 경우의 수

case 1,2,3,4 : x가 부모의 왼쪽 자식인 경우
case 5,6,7,8 : x가 부모의 오른쪽 자식인 경우
대칭적이므로 여기선 1,2,3,4에 대해서만 설명
- x가 더블 블랙이고 x의 형제 노드가 w, x가 부모의 왼쪽 자식노드일 때

case1 : w가 red일 때

w가 red니까 w는 반드시 자식 노드를 가져야 하고 (5번 조건에 따라. 지금 x는 이미 까만공 2개)
w가 red니까 w의 자식들은 둘 다 black.
거기다가 w의 자식들은 nil node 일 수가 없다.
나 ) 왜 d가 한쪽으로 치우친 블랙 2개를 가질 수 없을까(한쪽은 nil 자식, 한쪽은 검은공 2개를 가진) 궁금했는데 이렇게 되면 nill 까지 블랙 노드의 수가 각각 달라져서 안된다.
딱 이그래프만 된다.
이제 처리는 x의 부모인 b에 대해서 한번의 left rotate. b와 d가 자리와 칼라를 바꾼다

x랑 블랙이 위로 올라간 것이 아니라 밑으로 내려왔지 (2보 전진을 위한 1보 후퇴)

이제 c가 a의 형제노드가 되고 c는 블랙. case1 탈출

정리

x 의 부모 기준 왼쪽 로테이트 하니까 x의 형제는 red였을 때 x 형제의 자식은 black 이었을 테니 새롭게 x의 형제가 된 (원래 x의 형제의 자식들) 애가 black이 되면서 case1을 탈출 한다
그리고 x는 red 부모를 갖게 되며 한 칸 후퇴한다.

case2 : w가 black, w자식들도 black일 때

x로부터 black 하나와 w로부터 black 하나를 뺏어서 그것을 둘의 부모인 b에게 준다.
노드 b는 블랙인지 레드인지 알 수 없다.
- case1로부터 왔다면 맨 처음에 w가 red였으니까 a의 부모인 b는 지금은 red/black 가능 (case2에 들어올 때 노드 b가 레드였을 것)
x는 더블블랙이었는데 하나 뺏겨서 보통의 블랙노드가 되고 d는 원래 블랙이었는데 하나 뺏기니까 red가 된다. (이 공은 b에게 간다)
이렇게 되면 위에서 내려오는 까만 공의 개수에는 아무런 변화가 없다.
문제는 부모노드 b
- b가 원래 red였다면 red-black(빨간공1, 까만공1)
  - 나) A에서 하나 뺏고, D에서 하나 뺏으면 B가 더블블랙 아니야? 라고 이해했는데 위에서 부터 내려오는 경로의 수로 따지면 원래 B가 RED인 경우 상위에 하나를 두면 그 경로의 오른 쪽 애들도 변경되므로 양 쪽에서 하나씩 뽑아서 상위에 하나를 두는 것이 맞다.
- 다시. b가 원래 red였다면 red-black. 그 때는 black으로 변경해주고 끝! (빨간공 뺏고)
- 문제는 B가 원래 Black 이어서 이제 B가 새로운 더블블랙 노드가 되는 것. 이제 parent[x]를 새로운 x로 해서 루프를 계속 돌면 된다. 여기서 EXTRA BLACK을 위로 올려보낸다는 말이 바로 이 말

case3 : w가 black, w의 왼쪽 자식이 RED, 오른쪽 자식은 black

case4: w 블랙, w의 오른쪽 자식이 red

w색을 p[x]의 색으로, p[x]를 black으로 w의 오른 자식을 black으로 바꾸고 p[x]에 대해 left-rotate 그리고 나서 x의 extra-black을 제거하고 종료
알파, 베타 생각해보면 어차피 2개
e의 자식들의 입장에서도 어차피 까만 공 하나 (e는 원래 red 였어서)

정리

전체적으로 케이스 8개 1,2,3,4 / 5,6,7,8 대칭적
처음부터 4로(형제의 오른쪽 자식이 red)가면 extra rotation, 하나 뺏기
case3으로 가면(형제의 왼쪽 자식이 red) right rotate해서 case4로 바뀐다
나) case가 3이면서 동시에 4면 어디로 가지? 뒤에 수도 코드 보면 우선 3에서 거른다
case1으로 가면 2,3,4중 하나로 가게 되고,
특이 case2 처음부터 case2로 가면 case2가 반복되다가 case 1, 3, 4로 갈 수 있고, case2 반복되는 동안에는 계속 올라갈 수 있다. 루트까지 올라가서 종료되거나
이것은 root[t] <- x가 아니다 종료하기 위해서 x에 root를 가리키게 한 것 뿐

bongf

spring, java학습