[알고리즘] 레드 블랙 트리 (Red Black Tree)

글의 요약 설명 부분. 150자를 적어주세요. 글의 요약 설명 부분. 150자를 적어주세요. 글의 요약 설명 부분. 150자를 적어주세요. 글의 요약 설명 부분. 150자를 적어주세요. 글의 요약 설명 부분. 150자를 적어주세요. 글의 요약 설명 부분. 150자입니다

 

목차

 

---

 

인프런 Rookiss님의 '자료구조와 알고리즘' 강의를 기반으로 정리한 필기입니다. 
😎 [C++과 언리얼로 만드는 MMORPG 게임 개발 시리즈] Part3: 자료구조와 알고리즘 강의 들으러 가기!

 

레드 블랙 트리 (Red Black Tree)

레드 블랙 트리(Red Black Tree)는 자료구조 측면에서 '이진 탐색 트리'와 같지만 노드 색이 빨간색 또는 검은색으로 표시된다는 차이점이 있다.

 

레드 블랙 트리는 아래와 같은 규칙이 적용된다.

1. 모든 노드는 빨간색 또는 검은색이다.
2. 뿌리 노드는 검은색이다.
3. 잎 노드는 검은색이다.
4. 빨간색 노드의 자식 노드는 모두 검은색이다.
5. 뿌리 노드와 모든 잎 노드 사이의 검은색 노드의 수는 모두 동일하다.

 

NIL 노드는 데이터를 갖고 있지 않는 더미 노드이다. NIL 노드는 모두 검은색이며 센티널(Sentinel) 노드라고도 불린다.

---

회전 연산

본문내용넣기

void RedBlackTree::LeftRotate(Node* x)
{
	Node* y = x->right;

	x->right = y->left; // [2];

	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->parent->left = y;
	else
		x->parent->right = y;

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

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

	y->left = x->right; // [2];

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

	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;
}

 

 

 

 

---

 

삽입 연산

본문내용넣기

 

 

 

---

 

삭제 연산

 

뿌리 노드와 모든 잎 노드 사이의 검은색 노드의 수는 모두 동일하다.

 

 

 

 

 

 

---

 

마무리

마무리