์ •๊ธ€/TIL

[TIL] - 2023.05-10

Casteira 2023. 5. 10. 11:15

๐Ÿ“Œ - RBํŠธ๋ฆฌ ์‚ญ์ œ

int rbtree_erase(rbtree *t, node_t *z) {
 
  node_t *y = z; // ์‚ญ์ œํ•˜๋ ค๋Š” ๋…ธ๋“œ z๋ฅผ ์šฐ์„  y์— ์ €์žฅ. 
  node_t *x;
  color_t y_original_color = y->color; // y์˜ ์ปฌ๋Ÿฌ๋ฅผ ์ €์žฅ

 
  
  if (z->left == t->nil){//์œ ํšจํ•œ ๊ฐ’์„ ๊ฐ€์ง„ ์ž์‹์ด ์˜ค๋ฅธ์ชฝ์—๋งŒ ํ•˜๋‚˜ ์žˆ๋Š” ๊ฒฝ์šฐ
    x = z->right; //์˜ค๋ฅธ์ชฝ ์ž์‹์„ x์— ๋‹ด์•„๋‘๊ณ 
    transplant(t, z, z->right); //z์˜ ์˜ค๋ฅธ์ชฝ ์ž์‹์„ z์— ์œ„์น˜์— ์ด์‹(transplant)ํ•˜๋ฉด์„œ z๋Š” ์ œ๊ฑฐ
    
    
  }else if(z->right == t->nil){//์œ ํšจํ•œ ๊ฐ’์„ ๊ฐ€์ง„ ์ž์‹์ด ์™ผ์ชฝ์—๋งŒ ํ•˜๋‚˜ ์žˆ๋Š” ๊ฒฝ์šฐ
    x = z->left;
   
    transplant(t, z, z->left);  // z์˜ ์™ผ์ชฝ ์ž์‹์„ z์— ์œ„์น˜์— ์ด์‹ํ•˜๋ฉด์„œ z๋Š” ์ œ๊ฑฐ๋จ
  }else{// ์œ ํšจํ•œ ์ž์‹์ด ๋‘˜์ธ ๊ฒฝ์šฐ
    y = tree_minimum(t,z->right);   // y = z์˜ ์˜ค๋ฅธ์ชฝ ์„œ๋ธŒํŠธ๋ฆฌ์˜ ์ตœ์†Œ๊ฐ’ ( z์˜ successor)
    y_original_color = y->color; // ์‚ญ์ œ ๋˜๋Š” ์ปฌ๋Ÿฌ ์ €์žฅ
    x = y->right; // x๋Š” y์˜ ์˜ค๋ฅธ์ชฝ ์„œ๋ธŒํŠธ๋ฆฌ
    if (y->parent == z){ // y์˜ ๋ถ€๋ชจ๊ฐ€ z์ผ๋•Œ
      x->parent = y; // x์˜ ๋ถ€๋ชจ๋Š” y  -> z๊ฐ€ ์‚ญ์ œ ๋˜๋ฉด์„œ y๊ฐ€ ์–ด์ฐจํ”ผ parent์˜ ์œ„์น˜๋กœ ๊ฐ€๊ธฐ ๋•Œ๋ฌธ
    }else{ 
      transplant(t, y, y->right); // y๋ฅผ ์‚ญ์ œํ•˜๋ฉด์„œ y์˜ ์˜ค๋ฅธ์ชฝ์„ y๋กœ ๋ณ€๊ฒฝ
      y->right = z->right; // y์˜ ์˜ค๋ฅธ ์ž์‹ = z์˜ ์˜ค๋ฅธ ์ž์‹
      y->right->parent = y; // y์˜ ์˜ค๋ฅธ์ชฝ ์ž์‹์˜ ๋ถ€๋ชจ = y
    }
    transplant(t, z, y);//z๋ฅผ ์‚ญ์ œํ•˜๋ฉด์„œ y๋ฅผ z์˜ ์œ„์น˜๋กœ ๋ณ€๊ฒฝ
    y->left = z->left; // z์˜ ์™ผ์ชฝ ์„œ๋ธŒํŠธ๋ฆฌ๋ฅผ y์˜ ์™ผ์ชฝ์œผ๋กœ ์ด์‹
    y->left->parent = y;
    y->color = z->color;
  }
  
  // fix up
  if (y_original_color == RBTREE_BLACK){ //์ง€์›Œ์ง€๋Š” ์ƒ‰์ด ๊ฒ€์ •์ผ ๊ฒฝ์šฐ
    node_t *brother;
    while (x!=t->root && x->color == RBTREE_BLACK){// x๊ฐ€ ๋ฃจํŠธ๊ฐ€ ์•„๋‹ˆ๊ณ , x์˜ ์ปฌ๋Ÿฌ๊ฐ€ ๋ธ”๋ž™์ผ๋•Œ
      if(x == x->parent->left){ // x๊ฐ€ ์™ผ์ชฝ ์ž์‹์ผ ๋•Œ
        brother = x->parent->right; // x์˜ ํ˜•์ œ
        // x ์˜ ํ˜•์ œ๊ฐ€ RED ์ธ ๊ฒฝ์šฐ
        if(brother->color == RBTREE_RED){ // ํ˜•์ œ์˜ ์ปฌ๋Ÿฌ๊ฐ€ ๋ ˆ๋“œ์ผ๋•Œ case # 1
          brother->color = RBTREE_BLACK; // ํ˜•์ œ์˜ ์ปฌ๋Ÿฌ = ๊ฒ€์ •
          x->parent->color = RBTREE_RED; // x์˜ ๋ถ€๋ชจ์˜ ์ปฌ๋Ÿฌ = ๋นจ๊ฐ•
          left_rotate(t, x->parent); // ๋ถ€๋ชจ ๊ธฐ์ค€์œผ๋กœ ์™ผ์ชฝ ํšŒ์ „
          brother = x->parent->right; // ํ˜•์žฌ๋Š” x๋ถ€๋ชจ์˜ ์˜ค๋ฅธ์ชฝ
        }
        // X์˜ ํ˜•์ œ๋Š” BLACK์ด๊ณ  ํ˜•์ œ์˜ ๋‘ ์ž์‹์ด ๋ชจ๋‘ BLACK์ธ ๊ฒฝ์šฐ
        if(brother->left->color == RBTREE_BLACK && brother->right->color==RBTREE_BLACK){ // ํ˜•์ œ์˜ ์™ผ์ชฝ ์ƒ‰์ด ๊ฒ€์ •์ด๊ณ  ํ˜•์ œ์˜ ์˜ค๋ฅธ์ชฝ ์ปฌ๋Ÿฌ๊ฐ€ ๊ฒ€์ •์ผ๋•Œ case # 2
          brother->color = RBTREE_RED; // ํ˜•์ œ์˜ ์ปฌ๋Ÿฌ = ๋นจ๊ฐ•
          x = x->parent; // x๋Š” x์˜ ๋ถ€๋ชจ
        // X์˜ ํ˜•์ œ๋Š” BLACK, ํ˜•์ œ์˜ ์™ผ์ชฝ ์ž์‹์€ RED, ํ˜•์ œ์˜ ์˜ค๋ฅธ์ชฝ ์ž์‹์€ BLACK์ธ ๊ฒฝ์šฐ
        }else{ 
          if(brother->right->color == RBTREE_BLACK){ //ํ˜•์ œ์˜ ์˜ค๋ฅธ์ชฝ ์ƒ‰ = ๊ฒ€์ • case # 3
            brother->left->color = RBTREE_BLACK; // ํ˜•์ œ์˜ ์™ผ์ชฝ ์ƒ‰ = ๊ฒ€์ •
            brother->color = RBTREE_RED; // ํ˜•์ œ์˜ ์ปฌ๋Ÿฌ = ๋นจ๊ฐ•
            right_rotate(t, brother); // ์˜ค๋ฅธ์ชฝ ํšŒ์ „
            brother = x->parent->right; // ํ˜•์ œ = x์˜ ๋ถ€๋ชจ์˜ ์˜ค๋ฅธ์ชฝ์ž์‹
          }
          // X์˜ ํ˜•์ œ๋Š” BLACK์ด๊ณ  ํ˜•์ œ์˜ ์˜ค๋ฅธ์ชฝ ์ž์‹์€ RED์ธ ๊ฒฝ์šฐ
          brother->color = x->parent->color; // ํ˜•์ œ์˜ ์ƒ‰ = x์˜ ๋ถ€๋ชจ์˜ ์ƒ‰ case # 4
          x->parent->color = RBTREE_BLACK;  
          brother->right->color = RBTREE_BLACK;
          left_rotate(t, x->parent);
          x = t->root;
        }
      }else{
        //์˜ค๋ฅธ์ชฝ ์ผ€์ด์Šค ( ์™ผ์ชฝ, ์˜ค๋ฅธ์ชฝ๋งŒ ๋ฐ˜๋Œ€๊ณ  ๋™์ผํ•จ)
        brother = x->parent->left;
        if(brother->color == RBTREE_RED){
          brother->color = RBTREE_BLACK;
          x->parent->color = RBTREE_RED;
          right_rotate(t, x->parent);
          brother = x->parent->left;
        }
        if(brother->right->color == RBTREE_BLACK && brother->left->color==RBTREE_BLACK){
          brother->color = RBTREE_RED;
          x = x->parent;
        }else{
          if(brother->left->color == RBTREE_BLACK){
            brother->right->color = RBTREE_BLACK;
            brother->color = RBTREE_RED;
            left_rotate(t, brother);
            brother = x->parent->left;
          }
          brother->color = x->parent->color;
          x->parent->color = RBTREE_BLACK;
          brother->left->color = RBTREE_BLACK;
          right_rotate(t, x->parent);
          x = t->root;
        }
      }
    }
    x->color = RBTREE_BLACK;
  }
  free(z);
  return 0;
  // erase ๋
}

 

๐Ÿ“Œ - RBํŠธ๋ฆฌ ๊ต์ฒด

// ์ด์‹ํ•˜๋Š” ํ•จ์ˆ˜
// ์„œ๋ธŒ ํŠธ๋ฆฌ ์ด๋™์„ ์œ„ํ•ด ๋…ธ๋“œ๊ฐ€ u๊ฐ€ ๋ฃจํŠธ์ธ ์„œ๋ธŒํŠธ๋ฆฌ๋ฅผ ๋…ธ๋“œ v๊ฐ€ ๋ฃจํŠธ์ธ ์„œ๋ธŒํŠธ๋ฆฌ๋กœ ๊ต์ฒด
void transplant(rbtree *t, node_t *u, node_t *v){
  if (u->parent == t->nil){ // u์˜ ๋ถ€๋ชจ๊ฐ€ nil ์ฆ‰, u๊ฐ€ ๋ฃจํŠธ๋…ธ๋“œ๋ผ๋ฉด
    t->root = v; //v๋ฅผ  ํŠธ๋ฆฌ์˜ ๋ฃจํŠธ๋…ธ๋“œ๋กœ ์‚ผ๋Š”๋‹ค.
  }else if(u == u->parent->left){ //u๊ฐ€ ๋ถ€๋ชจ์˜ ์™ผ์ชฝ ์ž์‹์ผ ๊ฒฝ์šฐ
    u->parent->left = v; //v๋ฅผ ์™ผ์ชฝ ์ž์‹์œผ๋กœ ์ด์‹ (u๋ฅผ ๋Œ€์ฒด)
  }else{ //์˜ค๋ฅธ์ชฝ ์ž์‹์ผ ๊ฒฝ์šฐ
    u->parent->right = v; //v๋ฅผ ์˜ค๋ฅธ์ชฝ ์ž์‹์œผ๋กœ ์ด์‹
  }
  v->parent = u->parent;
}

 

 

๐Ÿ“Œ - RBํŠธ๋ฆฌ ์ตœ์†Œ, ์ตœ๋Œ€, ์„œ๋ธŒ๋ฃจํŠธ์˜ ์ตœ์†Œ๊ฐ’

node_t *rbtree_min(const rbtree *t) {  // ์ตœ์†Œ๊ฐ’ ๋ฐ˜ํ™˜
  // TODO: implement find
  node_t *min_node = t->root; // t->root๋ถ€ํ„ฐ ์‹œ์ž‘
  while (min_node->left != t->nil){ // ์™ผ์ชฝ๋…ธ๋“œ๊ฐ€ nil์ผ๋•Œ๊นŒ์ง€
     min_node = min_node->left;
  }
  return min_node;
}

node_t *rbtree_max(const rbtree *t) { // ์ตœ๋Œ€๊ฐ’ ๋ฐ˜ํ™˜
  // TODO: implement find
   node_t *max_node = t->root; // t->root๋ถ€ํ„ฐ ์‹œ์ž‘
  while (max_node->right != t->nil){ // ์˜ค๋ฅธ์ชฝ ๋…ธ๋“œ๊ฐ€ nil์ผ๋•Œ๊นŒ์ง€
     max_node = max_node->right;
  }
  return max_node;
}

node_t *tree_minimum(const rbtree *t, node_t *sub_root){
    // TODO: implement find
    node_t *r = sub_root;
    if (r == t -> nil)
        return r;
    while (r -> left != t -> nil)
    {
        r = r -> left;
    }
    return r;
}

 

 


 

๋”๋ณด๊ธฐ

ใ€Œ ๋ถˆ์šด์ด๋ž€ ๋ฌด์—‡์ผ๊นŒ? ์ƒ๊ฐ์ด๋ผ๋„ค. ๊ฐˆ๋“ฑ, ๋…ผ์Ÿ, ์ฑ…๋ง, ๋น„๋‚œ ๋ถˆ์†, ๊ฒฝ๋ง์Šค๋Ÿฌ์›€ ๋“ฑ์€ ๋ฌด์—‡์„ ๋งํ•˜๋Š” ๊ฑธ๊นŒ? ์ด๊ฒƒ๋“ค ๋˜ํ•œ ์ƒ๊ฐ์ด๋ผ๋„ค. ใ…ก๋ฆฌ๊ณ  ์ด ์‚ฌ์‹ค๋ณด๋‹ค ์ค‘์š”ํ•œ ๊ฒƒ์€ ์ด๋Ÿฐ ์ƒ๊ฐ๋“ค์ด ์šฐ๋ฆฌ์˜ ํ•ฉ๋ฆฌ์  ์„ ํƒ ๋ฐ”๊นฅ์— ๋†“์—ฌ ์žˆ์„ ๋•Œ์ง€. ๊ทธ๋•Œ ๊ทธ๊ฒƒ๋“ค์€ ์„  ์•„๋‹ˆ๋ฉด ์•…์˜ ๋ชจ์Šต์œผ๋กœ ๋‚˜ํƒ€๋‚œ๋‹ค๋„ค. ์ž์‹ ์˜ ์„ ํƒ ์˜์—ญ ์•ˆ์— ์†ํ•˜๊ฒŒ ํ•  ๋•Œ๋งŒ ์ด ์ƒ๊ฐ๋“ค์„ ๋ฐ”๊ฟ€ ์ˆ˜๊ฐ€ ์žˆ๋‹ค๋„ค. ๊ทธ๋Ÿฌ๋ฉด ๋ฌด์Šจ ์ผ์ด ์ผ์–ด๋‚˜๋“  ์‚ฌ๋žŒ๋“ค์€ ํ‰ํ™”๋กœ์›€์„ ์œ ์ง€ํ•  ์ˆ˜ ์žˆ๋‹ค๋„ค. ใ€

-์—ํ”ฝํ…Œํ† ์Šค, ๋Œ€ํ™”๋ก, 3.3.18b-19

 

์šฐ๋ฆฌ๋Š” ์‰ผ ์—†์ด ์ƒ๊ฐ์„ ํ•œ๋‹ค. ์˜ค๋Š˜ ํ•˜๋ฃจ ๋‹น์‹ ์€ ์ด๋Ÿฐ์ €๋Ÿฐ ์ƒ๊ฐ์„ ํ–ˆ์„ ๊ฒƒ์ด๋‹ค.์ƒ๊ฐํ•˜๋‹ค๊ฐ€ ์ž์ฃผ ๋ถ„๋…ธ์— ์‚ฌ๋กœ์žกํžˆ๋Š” ๊ฒƒ์€ ๋†€๋ž์ง€ ์•Š์€ ์ผ์ด๋‹ค. 

ํ•˜์ง€๋งŒ ์ƒ๊ฐ์„ ๋†“์•„๋ฒ„๋ฆฐ๋‹ค๋ฉด ์–ด๋–ป๊ฒŒ ๋ ๊นŒ? ์žก์ดˆ๋ฅผ ์ œ๊ฑฐํ•˜๋Š” ๊ฒƒ์ฒ˜๋Ÿผ ์ƒ๊ฐ์„ ์ž๋ฅด๊ณ  ์†Ž์•„๋‚ด์ž. ์ข‹๊ฑฐ๋‚˜ ๋‚˜์˜๋‹ค๋Š” ๋А๋‚Œ์— ์‚ฌ๋กœ์žกํžˆ์ง€ ์•Š์œผ๋ฉด์„œ ์ƒ๊ฐ์ด๋‚˜ ํŒ๋‹จ์— ๋ฌผ๋“ค์ง€ ์•Š๋Š” ๊ฒƒ์ด๋‹ค. ๋‹จ์ง€ ๊ทธ๊ฒƒ๋ฟ์ด๋‹ค.

๋”๋ณด๊ธฐ

ใ€Œ ์—ํ”ฝํ…Œํ† ์Šค๊ฐ€ ์ด๋ ‡๊ฒŒ ๋งํ–ˆ๋‹ค. "์šฐ๋ฆฌ๋Š” ๋™์˜ํ•˜๋Š” ๊ธฐ์ˆ ์„ ๋‹ค์‹œ ๋ฐฐ์›Œ์•ผ ํ•œ๋‹ค. ๊ทธ๋ฆฌ๊ณ  ์š•๋ง์— ๋Œ€ํ•ด์„œ๋„ ํŠน๋ณ„ํ•œ ์ฃผ์˜๋ฅผ ๊ธฐ์šธ์—ฌ์•ผ ํ•œ๋‹ค. ์š•๋ง์€ ์ ๋‹นํžˆ ์ œํ•œ ๋ฐ›์•„์•ผ ํ•˜๋ฉฐ, ๊ณต์ต์„ ์ฆ์ง„ํ•  ์ˆ˜ ์žˆ๋„๋ก ํ•ด์•ผ ํ•˜๋ฉฐ, ์‹ค์ œ ๊ฐ€์น˜์— ๋ถ€ํ•ฉํ•  ์ˆ˜ ์žˆ๋„๋ก ์œ ์˜ํ•ด์•ผ ํ•œ๋‹ค.  ใ€

-๋งˆ๋ฅด์ฟ ์Šค ์•„์šฐ๋ ๋ฆฌ์šฐ์Šค, ๋ช…์ƒ๋ก, 11.37

 

์ค‘์š”ํ•œ ๊ฒƒ์€ ๊ฒฝ์ฒญํ•˜๊ณ  ๋ฐฐ์šฐ๋ ค๋Š” ์ž์„ธ๋‹ค. ์šฐ๋ฆฌ๋Š” ์‚ฌํšŒ์  ์ง€์œ„์™€ ์ƒ๊ด€์—†์ด ๋‹ค๋ฅธ ๋ˆ„๊ตฐ๊ฐ€๋กœ๋ถ€ํ„ฐ ๊ธฐ๊บผ์ด ๋ฐฐ์šธ ์ˆ˜ ์žˆ์–ด์•ผํ•œ๋‹ค.

 

 


 

๋Œ“๊ธ€์ˆ˜0