레드블랙 트리

• 이진 검색 트리인데 노드의 필드 중에 색깔 (red 또는 black) 을 나타내는 필드가 있다.
• 루트 ~ 리프 경로에 나타나는 노드의 색을 제한해서 트리가 근사적으로 균형을 이루도록 한다.

레드블랙 트리 조건

1. 모든 노드는 적색이거나 흑색
2. 루트는 흑색
3. 모든 리프는 흑색
4. 노드가 적색이면 그 노드의 자식 노드는 흑색이다
5. 각 노드로부터 그 노드의 자손인 리프로 가는 경로들은 모두 같은 수의 흑색 노드를 포함한다.

• n개의 내부 노드를 가지는 레드블랙 트리는 최대 2log(n+1)의 높이를 가진다.

---

nil 노드

레드블랙 트리에서 루트의 부모와 모든 리프 노드는 nil 노드로 표현함
nil 노드는 흑색이고 이 의외의 의미는 없다.

이것은 경계노드를 다루기 편하도록 하고, 저장공간을 낭비하지 않기 위함

흑색높이 bh(x)

노드 x에서 리프까지의 경로에 있는 모든 흑색 노드(x제외)의 수 = bh(x)

---

관심 대상은 키 값을 가지는 내부노드들이므로 위와 같이 표현한다.

---

회전

트리에 노드를 삽입, 삭제할 때 레드블랙 트리의 특성을 위반할 수 있다.
트리내의 일부 노드들의 색, 포인터를 변경하는 것을 회전이라 한다.

//왼쪽 회전 
void leftRotate(RedBlackTree * t, Node* x) {
	//y를 x의 right로 초기화 
	Node* y = x->right;
	//x의 right를 y의 left로 
	x->right = y->left;
	//y의 left가 nil이 아니라면, y의 left의 parent를 x로 
	if (y->left != t->nil) {
		y->left->parent = x;
	}
	//y의 parent를 x의 parent로 
	y->parent = x->parent;
	//x가 root였다면 
	if (x->parent == t->nil) {
		//y를 root로 
		t->root = y;
	}
	else if (x == x->parent->left) { //x가 x의 parent의 left 라면 
		x->parent->left = y;
	}
	else { //x가 x의 parent의 right 라면 
		x->parent->right = y;
	}
	y->left = x;
	x->parent = y;
}

교안이랑 매개변수 형을 같게 하려고 일부러 클래스 멤버함수로 안 만들고 밖에 만듬

삽입

• 노드 z를 트리 T에 삽입한 후 z를 적색으로 칠한다.
• 레드블랙 트리의 특성을 만족함을 보장하기 위해 RB_INSERT_FIXUP 을 호출해서 노드의 색깔을 바꾸고 회전을 수행함

//삽입 
void rb_insert(RedBlackTree* t, Node* z) {
	Node* y = t->nil;//y는 x의 부모노드, z를 삽입하고 parent 포인터를 연결하기 위함 
	Node* x = t->root; //x가 root부터 시작해서 z랑 key를 비교하며 z를 삽입할 위치를 찾음 
	
	//z를 삽입할 위치 찾기 
	while (x != t->nil) { // x == t->nil이면 x가 리프까지 내려가서 z의 위치를 찾은 것 
		y = x; //y=x로 놓고 x는 z와 값을 비교하며 내려간다 
		if (z->key < x->key) {
			x = x->left;
		}
		else {
			x = x->right;
		}
	}

	//y는 while에서 x의 부모 위치를 계속 유지함 x자리에 z를 넣으므로 z->parent를 x로 해줌 
	z->parent = y;

	//y가 nil이면 z는 root 
	if (y == t->nil) { z = t->root; }
	//아닐 경우 y와 z의 키값을 비교해서 알맞은 위치에 넣어줌 
	else if (z->key < y->key) { y->left = z; }
	else { y->right = z; }

	//z는 맨 끝에 있는 노드이므로 left, right는 nil로 지정 
	z->left = t->nil;
	z->right = t->nil;
	z->color = RED; //z의 색은 RED로 놓는다. 

	//z를 트리에 넣은 후에 rb_insert_fixup 메소드로 레드블랙 트리의 조건을 만족하게 한다  
	rb_insert_fixup(t, z);
}

먼저 노드의 값을 비교하며 노드를 삽입할 위치를 정하고 삽입한다. 색은 RED로 한다. 그리고 나서 rb_insert_fixup 메소드로 레드블랙 트리의 조건을 만족하게 해준다.

1. 모든 노드는 적색이거나 흑색
2. 루트는 흑색
3. 모든 리프는 흑색
4. 노드가 적색이면 그 노드의 자식 노드는 흑색이다
5. 각 노드로부터 그 노드의 자손인 리프로 가는 경로들은 모두 같은 수의 흑색 노드를 포함한다.

레드블랙 트리 조건 중 2,4번이 새로 삽입된 노드로 인해 깨질 수 있다.
z가 루트로 들어가면 루트가 흑색이라는 조건을 충족하지 못한다.
z의 부모 노드가 적색이면 z도 적색이므로 4번을 만족하지 못한다.

• z가 루트에 들어갔는데 적색일 경우 : z를 흑색으로 바꾸면 된다.

• z의 부모가 적색인 경우
  이 경우는 3가지로 나눠서 처리해야 한다
  1) z의 삼촌(z.p.p.r)이 적색일 경우
  2) z의 삼촌이 흑색이고 z가 오른쪽 자식일 경우
  3) z의 삼촌이 흑색이고 z가 왼쪽 자식일 경우

1)

2)의 경우