자료구조, rbtree insert
📌 RB-Insert
삽입노드는 항상 RED
왜? 삽입 후 모든 경로에 Black Height 영향을 주지 않기 때문.
root부터 시작해 트리를 순회하면서 z노드(삽입노드)의 부모 위치를 찾아줍니다.
부모 위치(y)를 찾은 뒤 z노드의 부모를 y노드를 가리키도록 포인터로 설정해주고
z노드의 자식들은 모두 nil노드로, 컬러는 빨간색으로 설정해줍니다.
그런 다음, RB트리의 균형을 맞춰주는 함수로 이동!
📄 rbtree.c
node_t *rbtree_insert(rbtree *t, const key_t key) {
// TODO: implement insert
node_t *y = t->nil; // y will be parent of z
node_t *x = t->root;
// 노드 크기 만큼의 동적 메모리 할당
node_t *z = (node_t *)calloc(1, sizeof(node_t));
// 입력받은 key 값 할당
z->key= key;
while (x != t->nil) {
y = x; // root부터 시작해 z의 부모 노드가 될 노드 찾음
if (z->key < x->key) {
x = x->left;
}
// 작으면 오른쪽으로 한칸 내려감
else {
x = x->right;
}
};
// nil까지 내려가서 z의 부모값으로 y 할당
z->parent = y;
if (y == t->nil){ // x가 값이 없어서 while문 패스시 ,
t->root = z; // root 주소에 할당
}
else if (z->key < y->key){ //입력값 z가 부모값 y보다 크면
y->left = z; // 왼쪽
}
else {
y->right = z; //오른쪽
};
// 삽입된 z child nil , color red
z->left = t->nil;
z->right = t->nil;
z->color = RBTREE_RED;
// rbtree 특성 위반 체크
rbtree_insert_fixup(t, z);
return t->root;
}
📌 RB-Insert-Fixup
삽입노드가 Red인데, 삽입노드의 부모 노드도 Red이면 double Red가 되므로 RBtree의 균형이 깨진다.
그러므로 조정해준뒤, z노드의 할아버지노드(z.p.p)로 타고타고 올라가
double Red가 없어질 때까지 fix-up 작업을 진행해 준다.
현재 추가한 노드를 가리키는 z, 이 z노드의 삼촌(u)의 컬러가 중요하다.
(Case1) u노드가 빨간색이면 recoloring 작업만 진행하고 z의 할아버지노드로 탐색 위치를 조정해준다.
u노드가 검정색일 경우, 두 가지로 나뉜다.
(Case2) z가 z부모의 왼쪽 자식일 때는 left-rotate 후, z의 할아버지 노드로 탐색 위치를 조정해준다.
(Case3) z가 z부모의 오른쪽 자식일 때는 recoloring & right-rotate 후, z의 할아버지 노드로 탐색 위치를 조정해준다.
📄 rbtree.c
void rbtree_insert_fixup(rbtree *t, node_t *z) {
node_t *y;
while (z->parent->color == RBTREE_RED) {
// z의 부모가 조부모의 왼쪽 서브 트리일 경우
if (z->parent == z->parent->parent->left) {
y = z->parent->parent->right;
// CASE 1 : 노드 z의 삼촌 y가 적색인 경우
if (y->color == RBTREE_RED) {
z->parent->color = RBTREE_BLACK;
y->color = RBTREE_BLACK;
z->parent->parent->color = RBTREE_RED;
z = z->parent->parent;
}
// CASE 2 : z의 삼촌 y가 흑색이며의 z가 오른쪽 자식인 경우
else {
if (z == z->parent->right) {
z = z->parent;
rotate_left(t, z);
}
// CASE 3 : z의 삼촌 y가 흑색이며의 z가 오른쪽 자식인 경우
z->parent->color = RBTREE_BLACK;
z->parent->parent->color = RBTREE_RED;
rotate_right(t, z->parent->parent);
}
}
// z의 부모가 조부모의 왼쪽 서브 트리일 경우
else {
y = z->parent->parent->left;
// CASE 4 : 노드 z의 삼촌 y가 적색인 경우
if (y->color == RBTREE_RED) {
z->parent->color = RBTREE_BLACK;
y->color = RBTREE_BLACK;
z->parent->parent->color = RBTREE_RED;
z = z->parent->parent;
}
// CASE 5 : z의 삼촌 y가 흑색이며의 z가 오른쪽 자식인 경우
else {
if (z == z->parent->left) {
z = z->parent;
rotate_right(t, z);
}
// CASE 6 : z의 삼촌 y가 흑색이며의 z가 오른쪽 자식인 경우
z->parent->color = RBTREE_BLACK;
z->parent->parent->color = RBTREE_RED;
rotate_left(t, z->parent->parent);
}
}
}
t->root->color = RBTREE_BLACK;
}
전반적인 insert과정은 다음 그림과 같다.
공부자료 1 : CLRS book (Introduction to Algorithms) 13장 레드 블랙 트리
공부자료 2 : 자료구조 레드-블랙 트리 쉽게 이해하기 https://code-lab1.tistory.com/62
'알고리즘' 카테고리의 다른 글
자료구조, RBtree 구현 (0) | 2023.04.06 |
---|---|
자료구조, rbtree delete (0) | 2023.04.06 |
자료구조, AVL Left-Rotate & Right-Rotate 구현 (0) | 2023.04.04 |
자료구조, Binary Search Tree (0) | 2023.04.02 |
자료 구조, Linked List (0) | 2023.04.02 |