[JUNGLE] TIL_37. RB Tree 삭제 일부 구현

RB Tree 삭제 구현

삭제까지는 구현했고 삭제 후 rebalacing을 하는 중이다! 내일까지 끝낼 수 있도록 하자!@!!@

node_t * get_sibling(node_t * node, node_t * parent) {
    if (node == NULL || parent == NULL) return NULL;

    if (node == parent->left)
        return parent->right;
    return parent->left;
}

void rebalanceAfterDeletion(rbtree *t, node_t **rp_node, node_t** parent_of_rp) {
    node_t *replace_node = *rp_node;
    node_t *parent_of_replace = *parent_of_rp;

    node_t *sibling = get_sibling(replace_node, parent_of_replace);
    // case 1. 형제 노드가 빨간색일 경우
    if (sibling->color == RBTREE_RED) {
        sibling->color = RBTREE_BLACK;
        replace_node->color = RBTREE_RED;
        if (parent_of_replace->right == sibling) {
            left_rotate(&parent_of_replace);
        } else {
            right_rotate(&parent_of_replace);
        }
    }
}

int rbtree_erase(rbtree *t, node_t *p) {
    if (t == NULL || p == NULL || t->root == NULL) {
        return 0;
    }

    node_t *find_node = rbtree_find(t, p->key);
    if (find_node == NULL) {
        return 0;
    }

    node_t *removed_node = NULL;
    node_t *replacement_node = NULL;
    node_t *parent_of_replacement = NULL;
    color_t removed_color;

    int is_root_deleted = find_node == t->root;

    // Case 1: 자녀가 하나 혹은 없을 경우
    if (find_node->left == NULL || find_node->right == NULL) {
        removed_color = find_node->color;
        parent_of_replacement = find_node->parent;
        replacement_node = (find_node->left != NULL) ? find_node->left : find_node->right;

        removed_node = remove_node_with_one_or_zero(&find_node);

        if (is_root_deleted) {
            t->root = find_node;
        }
    }
    // Case 2: 자녀가 두 개일 경우
    else {
        node_t *successor = find_successor(find_node);

        removed_color = successor->color;

        replacement_node = successor->right;
        parent_of_replacement = successor->parent;

        if (parent_of_replacement == find_node) {
             parent_of_replacement = successor;
        }

        removed_node = remove_node_with_one_or_zero(&successor);

        find_node->key = successor->key;
    }

    if (removed_color == RBTREE_BLACK) {
        rebalanceAfterDeletion(t, replacement_node, parent_of_replacement);
    }

    if (removed_node != NULL) {
        free(removed_node);
    }

    return 1;
}

농구

306호 분들과 농구시합을 하였다! 3대2로 처참히 졌지만,, 다음번엔 꼭 이기리라..!