📝 배운 것들

---

🏷️ AVL과 RBT의 차이

AVL은 리프 노드들 사이 +-1까지만 높이 차이 허용
RBT는 리프 노드들까지의 길이가 2배까지는 날 수 있음

그래서 AVL이 검색은 더 빠름
근데 엄격하게 하다보니까 뭐 하나만 바꾸면 막 움직여야됨 삽입 삭제 비교적 느림

RBT는 탐색은 느리지만 삽입, 삭제에 유리함

둘 다 탐색 O(log n)이긴 함

현실에선 데이터 삽입, 삭제 빈번하게 일어나므로 RBT 주로 쓴다

RBT 쓰는 곳 : 리눅스 커널, c++ map,set 자료형
AVL 쓰는 곳 : 딕셔너리

추가 자료 : https://bo5mi.tistory.com/212

📦 Red-black tree

---

오늘까지 만든 코드

#include "rbtree.h"
#include <stdlib.h>

///////////////////////// function prototypes ////////////////////////////////////

// 메모리: 트리 생성/삭제
rbtree *new_rbtree(void);
void delete_rbtree(rbtree *);

// 좌회전, 우회전
void right_rotate(rbtree *t, node_t *x);
void left_rotate(rbtree *t, node_t *x);

// 위치 바꾸기
void rb_transplant(rbtree *t, node_t *u, node_t *v);

// 노드 삽입/삭제
node_t *rbtree_insert(rbtree *t, const key_t);
int rbtree_erase(rbtree *t, node_t *z);

// 삽입/삭제 fixup
void rb_insert_fixup(rbtree *t, node_t *z);
void rb_erase_fixup(rbtree *t, node_t *x);

// 노드 검색
node_t *rbtree_find(const rbtree *, const key_t);
node_t *rbtree_min(const rbtree *);
node_t *rbtree_max(const rbtree *);

// 노드에서부터 찾기
node_t *min_from_node(rbtree *t, node_t *x);
node_t *max_from_node(rbtree *t, node_t *x);

// 트리를 배열로 변환 -> inorder traversing으로 구현!!!
// traversing 순서: node, node->left, node->right
int rbtree_to_array(const rbtree *, key_t *, const size_t);

//////////////////////////////////////////////////////////////////////////

rbtree *new_rbtree(void)
{
  // TODO: initialize struct if needed
  rbtree *p = (rbtree *)calloc(1, sizeof(rbtree));

  p->nil = (node_t *)malloc(sizeof(node_t));
  p->nil->color = RBTREE_BLACK;
  p->nil->key = 0;
  p->nil->parent = NULL;
  p->nil->left = NULL;
  p->nil->right = NULL;
  p->root = p->nil;
  return p;
}

void left_rotate(rbtree *t, node_t *x)
{
  node_t *y = x->right;
  x->right = y->left;
  if (y->left != t->nil)
  {
    y->left->parent = x;
  }
  y->parent = x->parent;
  if (x->parent == t->nil)
  {
    t->root = y;
  }
  else if (x == x->parent->left)
  {
    x->parent->left = y;
  }
  else
  {
    x->parent->right = y;
  }
  x->left = x;
  x->parent = y;
}

void right_rotate(rbtree *t, node_t *x)
{
  node_t *y = x->left;
  x->left = y->right;
  if (y->right != t->nil)
  {
    y->right->parent = x;
  }
  y->parent = x->parent;
  if (x->parent == t->nil)
  {
    t->root = y;
  }
  else if (x == x->parent->right)
  {
    x->parent->right = y;
  }
  else
  {
    x->parent->left = y;
  }
  x->right = x;
  x->parent = y;
}

void rb_transplant(rbtree *t, node_t *u, node_t *v)
{
  if (u->parent == t->nil)
  {
    t->root = v;
  }
  else if (u == u->parent->left)
  {
    u->parent->left = v;
  }
  else
  {
    u->parent->right = v;
  }
  v->parent = u->parent;
}

void delete_rbtree(rbtree *t)
{
  // TODO: reclaim the tree nodes's memory
  free(t);
}

node_t *rbtree_insert(rbtree *t, const key_t key)
{
  // TODO: implement insert
  node_t *y = t->nil;
  node_t *x = t->root;
  node_t *z = (node_t *)malloc(sizeof(node_t));
  z->color = RBTREE_RED;
  z->key = key;

  while (x != t->nil)
  {
    y = x;
    x = (z->key < x->key) ? x->left : x->right;
  }

  z->parent = y;

  if (y == t->nil)
  {
    t->root = z;
  }
  else
  {
    if (z->key < y->key)
    {
      y->left = z;
    }
    else
    {
      y->right = z;
    }
  }
  z->left = t->nil;
  z->right = t->nil;

  rb_insert_fixup(t, z); // 이게 문제!

  return z;
}

void rb_insert_fixup(rbtree *t, node_t *z)
{
  while (z->parent->color == RBTREE_RED)
  {
    if (z->parent == z->parent->parent->left)
    {
      node_t *y = z->parent->parent->right;
      if (y->color == RBTREE_RED)
      {
        z->parent->color = RBTREE_BLACK;
        y->color = RBTREE_BLACK;
        z->parent->parent->color = RBTREE_RED;
        z = z->parent->parent;
      }
      else
      {
        if (z == z->parent->right)
        {
          z = z->parent;
          left_rotate(t, z);
        }

        z->parent->color = RBTREE_BLACK;
        z->parent->parent->color = RBTREE_RED;
        right_rotate(t, z->parent->parent);
      }
    }
    else
    {
      node_t *y = z->parent->parent->left;
      if (y->color == RBTREE_RED)
      {
        z->parent->color = RBTREE_BLACK;
        y->color = RBTREE_BLACK;
        z->parent->parent->color = RBTREE_RED;
        z = z->parent->parent;
      }
      else
      {
        if (z == z->parent->left)
        {
          z = z->parent;
          right_rotate(t, z);
        }
        z->parent->color = RBTREE_BLACK;
        z->parent->parent->color = RBTREE_RED;
        left_rotate(t, z->parent->parent);
      }
    }
  }
  t->root->color = RBTREE_BLACK;
}

node_t *rbtree_find(const rbtree *t, const key_t key)
{
  // TODO: implement find
  node_t *f = t->root;
  while (f != t->nil && f->key != key)
  {
    if (key < f->key)
    {
      f = f->left;
    }
    else
    {
      f = f->right;
    }
  }
  if (f == t->nil)
  {
    return NULL;
  }
  return f;
}

node_t *rbtree_min(const rbtree *t)
{
  // TODO: implement find
  return t->root;
}

node_t *rbtree_max(const rbtree *t)
{
  // TODO: implement find
  return t->root;
}

node_t *min_from_node(rbtree *t, node_t *x)
{
  while (x->left != t->nil)
  {
    x = x->left;
  }
  return x;
}

int rbtree_erase(rbtree *t, node_t *z)
{
  // TODO: implement erase
  node_t *x;
  node_t *y = z;
  color_t y_original_color = y->color;
  if (z->left == t->nil)
  {
    x = z->right;
    rb_transplant(t, z, z->right);
  }
  else
  {
    if (z->right == t->nil)
    {
      x = z->left;
      rb_transplant(t, z, z->left);
    }
    else
    {
      y = min_from_node(t, z->right);
      y_original_color = y->color;
      x = y->right;
      if (y->parent == z)
      {
        x->parent = y;
      }
      else
      {
        rb_transplant(t, y, y->right);
        y->right = z->right;
        y->right->parent = y;
      }
      rb_transplant(t, z, y);
      y->left = z->left;
      y->left->parent = y;
      y->color = z->color;
    }
  }
  if (y_original_color == RBTREE_BLACK)
  {
    rb_erase_fixup(t, x);
  }
  return y->key;
}

void rb_erase_fixup(rbtree *t, node_t *x)
{
  node_t *w;
  while ((x != t->root) && (x->color == RBTREE_BLACK))
  {
    if (x == x->parent->left)
    {
      w = x->parent->right;
      if (w->color == RBTREE_RED)
      {
        w->color = RBTREE_BLACK;
        x->parent->color = RBTREE_RED;
        left_rotate(t, x->parent);
        w = x->parent->right;
      }
      if ((w->left->color == RBTREE_BLACK) && (w->right->color == RBTREE_BLACK))
      {
        w->color = RBTREE_RED;
        x = x->parent;
      }
      else
      {
        if (w->right->color == RBTREE_BLACK)
        {
          w->left->color = RBTREE_BLACK;
          w->color = RBTREE_RED;
          right_rotate(t, w);
          w = x->parent->right;
        }
        w->color = x->parent->color;
        x->parent->color = RBTREE_BLACK;
        w->right->color = RBTREE_BLACK;
        left_rotate(t, x->parent);
        x = t->root;
      }
    }
    else
    {
      w = x->parent->left;
      if (w->color == RBTREE_RED)
      {
        w->color = RBTREE_BLACK;
        x->parent->color = RBTREE_RED;
        right_rotate(t, x->parent);
        w = x->parent->left;
      }
      if ((w->right->color == RBTREE_BLACK) && (w->left->color == RBTREE_BLACK))
      {
        w->color = RBTREE_RED;
        x = x->parent;
      }
      else
      {
        if (w->left->color == RBTREE_BLACK)
        {
          w->right->color = RBTREE_BLACK;
          w->color = RBTREE_RED;
          left_rotate(t, w);
          w = x->parent->left;
        }
        w->color = x->parent->color;
        x->parent->color = RBTREE_BLACK;
        w->right->color = RBTREE_BLACK;
        right_rotate(t, x->parent);
        x = t->root;
      }
    }
  }
}

int rbtree_to_array(const rbtree *t, key_t *arr, const size_t n)
{
  // TODO: implement to_array
  return 0;
}

test_find_erase_fixed에서 막힘.
팀원에게 물어봤더니 자기는 일단 이진 탐색 트리 방식으로만 구현했는데
(높이 조절 없음) test_find_erase_fixed까지 통과했다고 함.
뭐지? 하고 rb_insert_fixup(t, z);을 주석처리해봤더니 통과.
이게 문제인듯. 내일 모래 와서 고쳐야겠다.