[RED-BLACK TREE] Deletion
6794 단어 red black tree자료구조c언어레드블랙트리c언어
rbtree.c
#include "rbtree.h"
#include <stdlib.h>
#include <stdio.h>
//NIL 생성
node_t nil_node = {RBTREE_BLACK, 988, NULL, NULL, NULL};
node_t *NIL = &nil_node;
int rbtree_erase(rbtree *t, node_t *p) {
// TODO: implement erase
// node_t *temp = t -> root; // 루트 노드
node_t *target_node = p; //삭제 대상 노드
node_t *y = NULL; // splice 대상 y , 초기값 NULL 설정
// target의 자식 노드가 0, 1개인 경우: splice 대상 y는 target 자신
if (target_node -> left == NULL || target_node -> right == NULL) y = target_node;
else y = successor(target_node);
// 2. y의 자식 노드 x 결정
// y가 잘려나가면 그 밑의 노드를 이어주어야 하므로
node_t *x = NULL; //
if (y -> left != NULL) x = y -> left;
else x = y -> right;
// exception case2: y가 root node인 경우
if (y -> parent == NULL) {
t -> root = x;
}
else {
if (x == NULL) x = NIL;
if (y == y -> parent -> left) y -> parent -> left = x;
else y -> parent -> right = x; // y 연결 해제
x -> parent = y -> parent;
}
// y가 삭제 대상이 아닐 경우, 값 복사
if (y != target_node) {
target_node -> key = y -> key;
}
//y가 black인 경우
if (y -> color == RBTREE_BLACK) delete_fixup(t, x);
free(y); //삭제 처리
// NIL 제거
if(NIL -> parent !=NULL) {
if(NIL == NIL -> parent -> left) NIL -> parent -> left = NULL;
else NIL -> parent -> right = NULL;
NIL -> parent = NULL;
}
return y;
}
node_t *rbtree_min(const rbtree *t) {
// TODO: implement find
node_t *curr = t-> root;
while (curr ->left != NULL) curr = curr ->left;
return curr;
}
node_t *successor(node_t *curr) {
// case1: right subtree is non-empty
if (curr->right != NULL) return rbtree_min(curr->right);
// case2: right-subtree is empty
node_t *temp;
temp = curr->parent;
// 조건을 만족할 때까지 트리를 타고 올라간다
// 조건: curr의 조상 중 처음으로 left child가 되는 노드의 부모 노드를 찾는다
while( temp != NULL && temp->right == curr){
curr = temp;
temp = temp->parent;
}
// check impossible cases(루트노드까지 올라간 경우)
if (temp == NULL){
printf("there is no successor of given node!\n");
}
return temp;
}
void delete_fixup(rbtree *t, node_t *x) {
//black 노드가 빠짐으로서 생긴 불균형을 다시 맞춰주기 위한 함수
node_t *sibling_node = NULL;
// if (x -> parent -> left == x) sibling_node = x -> parent -> right;
// else sibling_node = x -> parent -> left;
// x는 항상 double black을 가리키게 됨
while(x != NULL && x-> parent != NULL && x -> color == RBTREE_BLACK) { // x는 루트노드가 아니면서, BLACK일 때
if (x == x -> parent -> left) {
sibling_node = x -> parent -> right;
// case1) 형제노드가 red이므로, x-> parent는 무조건 black
if (sibling_node -> color == RBTREE_RED) {
x -> parent -> color = RBTREE_RED;
sibling_node -> color = RBTREE_BLACK;
left_rotate(t, x -> parent);
sibling_node = x -> parent -> right; // 새로운 형제 노드 설정 (case 2, 3, 4 대입 가능 상태로 만들어줌)
}
// case2) x는 double black, 형제 노드 black, 형제 자식노드(오, 왼) 모두 black
if (sibling_node -> left-> color == RBTREE_BLACK && sibling_node -> right -> color == RBTREE_BLACK) {
// 형제의 왼쪽 자식, 오른쪽 자식이 black인 경우 (빈 공간에 여유가 없는 상태이므로 부모에게 전달하거나 전체 높이를 1 줄이기)
sibling_node -> color == RBTREE_RED;
// x와 형제 노드 모두 black을 parent에 주기
// x는 double black -> black / 형제 노드는 black -> red가 됨
// parent가 기존에 red였으면 black 이 되고, black이었으면 double black이 되므로 parent를 x로 설정해서 재귀 돌려주기
x = x -> parent;
// NIL 제거
if (x -> left == NIL) {
x -> left = NULL;
NIL -> parent = NULL;
}
}
else {
// case3) x는 double black, 형제 노드 black, 형제의 왼쪽 자식 red, 형제의 오른쪽 자식 black
if (sibling_node -> right -> color == RBTREE_BLACK) {
sibling_node -> left -> color == RBTREE_BLACK;
sibling_node -> color == RBTREE_RED;
right_rotate(t, sibling_node);
sibling_node = x -> parent -> right;
//새로운 형제노드는 black이 되며, 새로운 형제노드의 오른쪽 자식이 red가 됨
//case4와 동일한 상황이 됨
}
else {
// case4) x는 double black, 형제노드 black, 형제의 왼쪽 자식 black, 형제의 오른쪽 자식 red
// 빠진 자리의 인접한 노드를 가져와 채우는 것
sibling_node -> color = x -> parent -> color;
x -> parent -> color = RBTREE_BLACK;
sibling_node -> right -> color = RBTREE_BLACK;
left_rotate(t, x -> parent);
// NIL 제거
if (x -> parent -> left == NIL) {
x -> parent -> left = NULL;
NIL -> parent = NULL;
}
}
}
}
else {
sibling_node = x -> parent -> left;
// case1)
if (x -> color == RBTREE_RED) {
sibling_node -> color = RBTREE_BLACK;
x -> parent -> color = RBTREE_RED; // 무조건 바꾸는 경우, recolor로 바꿔서 표기할것
right_rotate(t, x);
sibling_node = x -> parent -> left; // 새로운 형제 노드 설정
}
// case2)
if (sibling_node -> right-> color == RBTREE_BLACK && sibling_node -> left -> color ==RBTREE_BLACK) {
// 형제의 왼쪽 자식 또는 오른쪽 자식이 black인 경우
sibling_node -> color == RBTREE_RED;
x = x -> parent;
// NIL 제거
if (x -> left == NIL) {
x -> left = NULL;
NIL -> parent = NULL;
}
}
else {
// case3)
if (sibling_node -> left -> color == RBTREE_BLACK) {
sibling_node -> right -> color == RBTREE_BLACK;
sibling_node -> color == RBTREE_RED;
left_rotate(t, sibling_node);
sibling_node = x -> parent -> left;
}
else {
// case4)
sibling_node -> color = x -> parent -> color;
x -> parent -> color = RBTREE_BLACK;
sibling_node -> left -> color = RBTREE_BLACK;
right_rotate(t, x -> parent);
if (x -> parent -> right == NIL) {
x -> parent -> right = NULL;
NIL -> parent = NULL;
}
}
}
}
}
if (x != NULL) x -> color = RBTREE_BLACK;
}
Author And Source
이 문제에 관하여([RED-BLACK TREE] Deletion), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@tpclsrn7942/RED-BLACK-TREE-Deletion저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)