레드-블랙 트리 Fat Finger ISSUE

문제 상황

test_find_erase_fixed() 테스트에서 세그멘테이션 폴트가 발생

test-rbtree

int main(void) {
  test_init();
  test_insert_single(1024);
  test_find_single(512, 1024);
  test_erase_root(128);
  test_find_erase_fixed();
  // test_minmax_suite();
  // test_to_array_suite();
  // test_distinct_values();
  // test_duplicate_values();
  // test_multi_instance();
  // test_find_erase_rand(10000, 17);
  printf("Passed all tests!\n");
}

test_erase_root(128) 성공

test_find_erase_fixed() Segmaent fault 발생

레드-블랙 트리 세그멘테이션 폴트 분석

문제

test_find_erase_fixed() 테스트에서 세그멘테이션 폴트가 발생

실행 결과

• test_erase_root(128): 성공
• test_find_erase_fixed(): 세그멘테이션 폴트 발생

원인 분석

성공 / 실패

성공(test_erase_root(128))

// 단순한 리프 노드 삭제
if (z->left == t->nil)  // z의 왼쪽 자식이 NIL
{
  x = z->right;         // x = NIL
  rbtree_transplant(t, z, z->right);  // z를 NIL로 교체
}
// else 블록 실행 안됨 (복잡한 로직 미사용)

실패(test_find_erase_fixed())

// 복잡한 노드 삭제 (자식이 둘 다 있는 경우)
else
{
  y = rbtree_sub_min(z->right, t->nil);  // 후계자 찾기
  y->original_color = y->color;
  x = y->right;
  
  if (y != z->right)
  {
    rbtree_transplant(t, y, y->right);
    y->right = z->right;
    y->right->parent = y;
  }
  else
  {
    x->parent = y;
    rbtree_transplant(t, z, y);  // else에서만 실행 됨 
 	y->left = z->left; 
  	y->left->parent = y;         
  	y->color = z->color;
  }
}

코드 실행 범위의 차이

세그멘테이션 폴트가 발생하는 이유

예시: y != z->right인 경우 (y가 z의 자식이 아닌 경우)

문제 발생 과정:

1. if 블록만 실행됨(자식이 둘 있을 때):

if (y != z->right) {
  rbtree_transplant(t, y, y->right);
  y->right = z->right;
  y->right->parent = y;
}

2. 공통적으로 실행되지 않음: 모든 케이스에서 z를 y로 교체

   • rbtree_transplant(t, z, y) ← z를 y로 교체하지 않음!
   • y->left = z->left ← z의 왼쪽 자식을 y가 상속
   • y->left->parent = y ← 왼쪽 자식의 부모를 y로 설정
   • y->color = z->color ← z의 색상을 y가 상속

3. 결과:

   • z가 트리에서 제대로 제거되지 않음
   • y가 z의 위치로 이동하지 않음
   • z의 왼쪽 서브트리가 연결되지 않음
   • 트리 구조가 망가짐

4. 세그폴트 발생:

   • 이후 delete_fixup이나 다른 연산에서 잘못된 포인터에 접근
   • 망가진 트리 구조로 인한 메모리 접근 오류

CLRS 의사코드:

12 if y ≠ z.right
13   RB-TRANSPLANT(T, y, y.right)
14   y.right = z.right
15   y.right.p = y
16 else x.p = y
17 RB-TRANSPLANT(T, z, y)  // ← 모든 경우에 공통 실행
18 y.left = z.left
19 y.left.p = y
20 y.color = z.color

핵심: 17-20번째 줄은 모든 경우에 공통으로 실행

결론

세그멘테이션 폴트의 주요 원인:
1. 코드 실행 범위 오류: if (y != z->right) 케이스에서 필수 로직이 실행되지 않음
2. 트리 구조 불일치: z가 제대로 제거되지 않아 포인터 상태가 망가짐
3. 의사코드 미준수: 공통 실행 부분을 조건문 안에 넣음 의사 코드도 잘 보고 따라하자
해결책: 의사코드의 구조를 정확히 따라 공통 실행 부분을 조건문 밖에 배치

erase 함수

int rbtree_erase(rbtree *t, node_t *z) {
  // z - 삭제할 노드
  // delete_fixup은 실제로 제거된 노드 y의 색상과 그 자리를 차지한 노드 x를 기준으로 수행되기 때문
  node_t *x;  // y의 자리를 차지하는 노드
  node_t *y;  // 실제로 제거되는 노드 (z를 직접 삭제하거나, z의 후계자를 삭제)
  color_t y_original_color;  // 원래 색상 저장 변수

  y = z;
  y_original_color = y->color;  // 원래 색상 저장

  if (z->left == t->nil)  // 자식이 하나만 있을 경우 (오른쪽만 있음)
  {
    x = z->right;    //  x를 z의 오른쪽 자식으로 설정
    rbtree_transplant(t, z, z->right);  // 삭제될 z 노드는 z의 오른쪽 자식으로 대체 
  }
  else if (z->right == t->nil)  // 자식이 하나만 있을 경우 (왼쪽만 있음)
  {
    x = z->left;  //  삭제할 z 노드의 왼쪽으로 설정 
    rbtree_transplant(t, z, z->left); // 삭제될 z 노드는 z의 왼쪽 자식으로 대체 
  }
  else // 자식이 둘 있을 때
  {
    y = rbtree_sub_min(z->right, t->nil);  // z의 후계자(successor) 찾기
    y_original_color = y->color;  // 원래 색상 저장
    x = y->right;     // y의 자리를 대체할 x를 y의 오른쪽으로 설정
    
    if (y != z->right)    // y가 z의 직계 자식이 아니라면 
    {
      rbtree_transplant(t, y, y->right);  // 삭제될 y 노드는 y의 오른쪽 자식으로 대체 
      y->right = z->right;  // 삭제될 y의 오른쪽 자식을 삭제할 노드z의 오른쪽으로 지정
      y->right->parent = y; // y의 오른쪽의 부모를 y로 지정
    }
    else  // 직계 자식이라면
    {
      x->parent = y;  // x의 부모를 y로 지정
      // rbtree_transplant(t, z, y);
      // y->left = z->left;
      // y->left->parent = y;
      // y->color = z->color;
    }
    rbtree_transplant(t, z, y);  // 삭제될 z 노드는 y로 대체 
    y->left = z->left;  // y의 오른쪽을 z의 왼쪽으로 지정
    y->left->parent = y; // y의 왼쪽의 부모를 y로 지정
    y->color = z->color; // y의 색깔을 z의 색으로 지정
  }

  if (y_original_color == RBTREE_BLACK)  // 만약 원래 색이 블랙이면 
  {
    rbtree_delete_fixup(t, x);  // 삭제한 후 레드블랙 트리 고치기 
  }
  
  free(z);  // 사용한 동적 메모리 반환
  return 0; 
}