[WEEK05 - 5] 36일차. RB tree 구현 2

kozi·2023년 4월 3일
0

SW사관학교 정글

목록 보기
28/33

트리 생성

rbtree *new_rbtree(void) {
  rbtree *p = (rbtree *)calloc(1, sizeof(rbtree)); // 트리 생성
  node_t *NIL = (node_t *)calloc(1, sizeof(node_t)); // nil노드 생성
  NIL->color = RBTREE_BLACK; // nil 노드 색깔 블랙으로
  p->root = NIL; // p의 루트를 nil 노드로
  p->nil = NIL; // p의 nil을 nil노드로
  return p;
}

메모리 해제

void delete_node(rbtree *t, node_t *node) {
  if (node == t->nil) {               // 현재 노드가 트리 nil노드와 같으면 그냥 return
    return;
  }

  delete_node(t, node->left);         // 왼쪽 재귀 호출
  delete_node(t, node->right);        // 오른쪽 재귀 호출
  free(node);                         // 현재 노드가 가리키는 공간 할당 해제
  node = NULL;                        // 노드값 NULL로 초기화
  return;
}

void delete_rbtree(rbtree *t) {
  // TODO: reclaim the tree nodes's memory
  if (t == NULL) {
    return;                           // 트리 없다면 return
  }

  delete_node(t, t->root);            // 생성된 노드가 가리키는 공간 할당 해제
  free(t->nil);                       // 트리의 nil노드가 가리키는 공간 할당 해제
  t->nil = NULL;                      // 트리의 nil노드 값 NULL로 초기화 
  free(t);                            // 트리가 가리키는 공간 할당 해제
  t = NULL;                           // 트리 값 NULL로 초기화
  return;
}

회전

void left_rotate(rbtree *t, node_t *x){
  node_t *y = x->right;               // y에 x의 오른쪽 자녀를 넣음
  x->right = y->left;                 // y 왼쪽 자녀를 x의 오른쪽으로 옮김

  if(y->left != t->nil){              // y 왼쪽 자녀 있다면
    y->left->parent = x;              // 그 왼쪽 자녀의 부모값을 x로 지정
  }
  y->parent = x->parent;              // y의 부모를 x의 부모로 변경

  if (x->parent == t->nil){           // x가 root인 경우 (부모가 nil)
    t->root = y;                      // 트리의 루트를 y로 변경
  
  }else if (x == x->parent->left){    // x가 x부모의 왼쪽 자식인 경우
    x->parent->left = y;              // x부모의 왼쪽 자식을 y로 변경

  }else{                              // x가 x 부모의 오른쪽 자식인 경우
    x->parent->right = y;             // x부모의 오른쪽 자식을 y로 변경
  }
  
  y->left = x;                        // y의 왼쪽자식을 x로
  x->parent = y;                      // x의 부모를 y로
  return;
}

void right_rotate(rbtree *t, node_t *x){ // left rotate 반대로
  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;
  }
  
  y->right = x;
  x->parent = y;
  return;
}
profile
어제보다 잘하고 싶은 개발자 Kozi 입니다.

0개의 댓글