[RED-BLACK TREE] Deletion

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