[RED-BLACK TREE] Insertion

rbtree.h

#ifndef RBTREE_H_
#define RBTREE_H_

#include <stddef.h>

typedef enum { RBTREE_RED, RBTREE_BLACK } color_t;

typedef int key_t;

typedef struct node_t {
  color_t color;
  key_t key;
  struct node_t *parent, *left, *right;
} node_t;

// 루트 노드만 가리키는 포인터를 멤버로 하는 구조체
typedef struct {
  node_t *root;
} rbtree; 

rbtree *new_rbtree(void);
void delete_rbtree(rbtree *);

node_t *rbtree_insert(rbtree *, const key_t);
node_t *rbtree_find(const rbtree *, const key_t);
node_t *rbtree_min(const rbtree *);
node_t *rbtree_max(const rbtree *);
node_t *make_node(key_t key);
void right_rotate(rbtree *t, node_t *x);
void left_rotate(rbtree *t, node_t *x);
void recolor(node_t *x);
int insert_node_helper(rbtree* t, node_t *new_node, key_t key);
int print_tree(node_t *curr);


#endif 

rbtree.c

#include "rbtree.h"
#include <malloc.h>
#include <stdio.h>

void left_rotate(rbtree *t, node_t* x);
void right_rotate(rbtree *t, node_t* x);
void recolor(node_t *curr);
void recolor_rotate(rbtree *t, node_t *new_node);
int insert_node_helper(rbtree *t, node_t *new_node, key_t key);
node_t *make_node(key_t key);
int print_tree(node_t *curr);

rbtree *new_rbtree(void) {
  rbtree *p = (rbtree *)calloc(sizeof(rbtree), 1);
  return p;
}

node_t *rbtree_insert(rbtree *t, const key_t key) {
  // TODO: implement insert
  // node_t *temp = t -> root;
  node_t *new_node = make_node(key);

  // 적절한 위치에 new_node 추가
  if (insert_node_helper(t, new_node, key)) return new_node;
  // 0이면 아래 실행
  // 1이면 루트 노드이므로, 함수종료(new_node 반환)

  //non-empty tree
  node_t *curr = new_node;
  node_t *parent_node = new_node -> parent;

  while(parent_node -> color != RBTREE_BLACK) {
    //uncle_node 설정
    node_t *uncle_node = NULL;
    if (parent_node -> parent -> left == parent_node) uncle_node = parent_node -> parent -> right;
    else uncle_node = parent_node -> parent -> left;

    // case1: uncle is NULL or black
    // if (uncle_node->color == RBTREE_BLACK || uncle_node == NULL)하게 되면
    // uncle_node가 NULL인 상황인데, null -> color로 접근하면 segmentation error발생 
    if (uncle_node == NULL || uncle_node->color == RBTREE_BLACK) {
      recolor_rotate(t, curr);
      break;
    }

    // uncle_node is red
    else {
      recolor(parent_node);
      recolor(uncle_node);
      if (parent_node -> parent == t -> root) break;
      curr = parent_node -> parent;
      parent_node = curr -> parent;
      recolor(curr);
    }
  }
  return t -> root;
}

node_t *rbtree_find(const rbtree *t, const key_t key) {
  // TODO: implement find
  node_t *curr = t -> root;

  if (curr== NULL) {
    printf("cannot find a node with value %d !!\n", key);
    return curr;
  }

  if (curr -> key == key) return curr;
  if (key < curr -> key) return rbtree_find(curr -> left, key);
  else return rbtree_find(curr -> right, key);

}


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 *rbtree_max(const rbtree *t) {
  // TODO: implement find
  node_t *curr = t-> root;
  while (curr ->right != NULL) curr = curr ->right; 
  return curr;
}

int print_tree(node_t *curr){
    // base case:
    if (curr == NULL) return 0;
    // recursive call: dfs
    print_tree(curr->left);
    printf("key: %d, color: ", curr->key);
    if (curr->color == RBTREE_BLACK) printf("black\n");
    else printf("red\n");
    print_tree(curr->right);
    return 0;
}

void left_rotate(rbtree *t, node_t *x) {
    node_t *y = x -> right; // y는 포인터형 변수이며, x의 right 값임
    x -> right = y -> left; 

    // y의 left가 NULL인 경우
    if (y -> left !=NULL) y -> left -> parent = x;
    y -> parent = x -> parent;

    // x가 루트 노드일 경우
    if (t->root == x) t -> root = y;
    else{     // x is not root node --> x의 기존 위치(left, right)에 y 추가
      if (x->parent->left == x) x->parent->left = y;
      else x->parent->right = y;
    }
    y -> left = x;
    x -> parent = y;
}

void right_rotate(rbtree *t, node_t *x) {
    node_t *y = x -> left; // y는 포인터형 변수이며, x의 left 값임
    x -> left = y -> right; //

    // y의 left가 NULL인 경우
    if (y -> right !=NULL) y -> right -> parent = x;
    y -> parent = x -> parent;

    // x가 루트 노드일 경우
    if (t->root == x) t -> root = y;
    // if (t -> root == x -> parent) t -> root = y;
    else {     // x is not root node --> x의 기존 위치(left, right)에 y 추가
      if (x->parent->left == x) x->parent->left = y;
      else x->parent->right = y;
    } 

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

void recolor_rotate(rbtree* t, node_t *new_node) { 
  recolor(new_node -> parent -> parent); //조부모는 항상 색 변경 필요
  node_t *parent_node = new_node -> parent;
  
  if (parent_node -> parent -> left == parent_node) {
    // LL
    if (parent_node -> left == new_node) {
      recolor(parent_node);
      right_rotate(t, parent_node -> parent);
    }
    // LR
    else {
      recolor(new_node);
      left_rotate(t, parent_node);
      right_rotate(t, new_node -> parent);
    }
  }
  else {
    // RR
    if (parent_node -> right == new_node) {
      recolor(parent_node);
      left_rotate(t, parent_node -> parent);
    }
    // RL
    else {
        recolor(new_node);
        right_rotate(t, parent_node);
        left_rotate(t, new_node -> parent);
      }
  }
}

void recolor(node_t *x) {
  if (x -> color == RBTREE_BLACK) x -> color = RBTREE_RED;
  else x -> color = RBTREE_BLACK;
}

node_t *make_node(key_t key) {
  node_t *new_node = (node_t*)malloc(sizeof(node_t));
  new_node->key = key;
  new_node->parent = NULL;
  new_node->left = NULL;
  new_node->right = NULL;
  new_node->color = RBTREE_RED;
  return new_node;
}

int insert_node_helper(rbtree* t, node_t *new_node, key_t key) {
  // node_t *temp = t -> root;
  // node_t *new_node = make_node(key);

  if (t -> root == NULL) {
    recolor(new_node); //루트 노드는 black이어야 하므로
    t -> root = new_node;
    return 1;
  }

  node_t *curr = t -> root;
  node_t *before = NULL;       // x 직전 node기록하기 위함
  while (curr != NULL) {        
      before = curr;
      if (key < curr->key) curr = curr->left;
      else curr = curr->right;
  }
  // curr == NULL 이면 before은 마지막 leaf node
  // before node 밑에 new_node 추가
  new_node->parent = before;
  if (key < before->key) before->left = new_node;
  else before->right = new_node;
  return 0;
}