레드 블랙 트리

CJB_ny·2022년 12월 5일

DataStructure & Algorithm

목록 보기

16/35

1. 레드 블랙 트리 구현 방법

균형 맞추는 알고리즘 많음.

AVL, Trick, 레드 블랙 트리 => 싹다 균형맞추는 알고리즘임.

2. 레드블랙 트리 특성

NIL은 그냥 Dummy 노드임.

4번 특성이 중요함.

레드 -> 레드 안됨. 블랙 -> 블랙 -> 블랙 이런거는 되지만.

아무튼 1~5번 특성 위반되면은 재구성이 발생함.

레드 블랙 트리는 새로 추가하는 노드는 항상 RED이다.

3. Fix

균형 맞출때 경우가

이 세가지가 있음.

이거 시발 말이 좀 어려운데 node->parent가 node->parent->parent의 왼쪽 자식으로 있을 경우 말하는거임.

else는 pp의 오른쪽 자식일 경우 말한다.

4. Rotate

지금 저 상황을 곧이 곧대로 만들어 볼 것이다.

5. Fixup 함수 분석

1) p = red, uncle = red

p = black, uncle = black, pp = red로 바꾼다.

2) p = red, uncle = black (triangle)

회전을 통해 case 3으로 바꿈

3) p = red, uncle = black (list)

색상 변경 + 회전

while문 시작

30, 10, 20, 25, 40, 50 순으로 넣을 것임.

node->parent->color가 RED가 아닐 경우 못들어옴.

바로 빠져나와서 Black으로 바뀜.

즉, root node집어 넣을 경우 BLACK으로 바로 바뀌고 나옴.

그다음 10넣을 경우

Insert부분에서 이러이러한 코드에 의해 root의 왼쪽 자식이 됨.

현재 InsertFixup들어가기전에는 RED임.

들어가면 while문의 조건에 맞지 않아서 while문 안들어감.

그리고나서 10은 빨강색임.

20을 넣으면은 현재 30이 root이고 b

10은 root의 left이고 r인 상태임.

현재는 이런상태임.

20은 10이 부모이고 right에 r인 상태로 InsertFixup들어옴.

while문 조건을 보면은 node->parent->color == RED이기 때문에 들어옴.

먼저 첫번째 if문 조건 확인하는데 20의 p가 pp의 왼쪽자식이라 들어온다.

uncle만드는데 node->pp는 _nil인데

Node의 기본 Color가 BLACK이라

else로 빠짐.

그리고 node가 p의 right가 맞기 때문에 왼쪽으로 회전시킴.

이게 레드블랙트리임.

현재 이 그림대로 하면 됨.

현재 LeftRotate에 20의 p인 10이 들어옴.

현재여기서 x가 10이라는건데...

y가 20임

이게 지금

이렇게 만들어라는 말같음.

그러면

void RedBlackTree::LeftRotate(Node* x)
{
	Node* y = x->right; 
    // x->right인 20이 y가됨

	x->right = y->left;
    // y->left인 _nil이 x->right로 들어감

	// 왼쪽 자식의 부모를 로
	if (y->left != _nil)
		y->left->parent = x;

	y->parent = x->parent;

	if (x->parent == _nil)
		_root = y;
	else if (x == x->parent->left)	// x가 부모의 왼쪽 자식일 경우
		x->parent->left = y;
	else
		x->parent->right = y;		// x가 부모의 오른쪽 자식일 경우 

	y->left = x;
	x->parent = y;
}

쭉 실행이 끝나면은

이런 상태이다.

그리고

이까지 실행하면

이럼.

그리고 RightRotate에 30넣음.

왜? Triangle나왔으니까

회전을 통해서 list로 바꾸고

색상변경 및 회전을 해주는거임.

void RedBlackTree::RightRotate(Node* y)
{
	Node* x = y->left;

	y->left = x->right;

	if (x->right != _nil)
		x->right->parent = y;

	x->parent = y->parent;

	if (y->parent == _nil)
		_root = x;
	else if (y == y->parent->left)
		y->parent->left = x;
	else
		y->parent->right = x;

	x->right = y;
	y->parent = x;
}