void lab2_tree_delete() 구현

[leeshinyook]

개요

• 노드를 삭제하는 함수를 구현해야하고 이는 3가지로 구분된다.
  자식이 없을때, 1개 있을때, 2개있을 때.
• 삭제 역시, 재귀함수호출로 해결하지 않도록한다.

상세

• lab2_bst_test.c 파일

gettimeofday(&tv_start, NULL);
    printf("\n");
    tree = lab2_tree_create();
    for (i=0 ; i < node_count ; i++) {               
        lab2_node* node = lab2_node_create(data[i]);
        lab2_node_insert(tree, node);
    }

    gettimeofday(&tv_end, NULL);
    exe_time = get_timeval(&tv_start, &tv_end);
    print_result(tree,num_threads, node_count, LAB2_TYPE_SINGLE,LAB2_OPTYPE_INSERT ,exe_time);
    lab2_tree_delete(tree);

    /* 
     * multi therad insert test coarse-grained 
     */
    is_sync = LAB2_TYPE_COARSEGRAINED;
    tree = lab2_tree_create();

    gettimeofday(&tv_insert_start, NULL);
    for(i=0; i < num_threads ; i++){
        thread_arg *th_arg = &threads[i];
        th_arg->tree = tree;
        th_arg->is_sync = is_sync;
        th_arg->data_set = data;
        th_arg->start = i*term;
        th_arg->end = (i+1)*term;

        pthread_create(&threads[i].thread,NULL,thread_job_insert,(void*)th_arg);
    }

    for (i = 0; i < num_threads; i++)
        pthread_join(threads[i].thread, NULL);

    gettimeofday(&tv_insert_end, NULL);
    exe_time = get_timeval(&tv_insert_start, &tv_insert_end);
    print_result(tree,num_threads, node_count, is_sync,LAB2_OPTYPE_INSERT ,exe_time);
    lab2_tree_delete(tree);

exe_time을 측정을 하고, tree_delete로 트리의 초기화를 담당하고 있는 부분이 반복되는 것을 볼 수 있고, 이를
살펴보면, node_remove는 tree_delete의 실행의 의해서 Call된다는 사실을 알 수 있다. 결국은 tree_delete() 함수바디 안에, node_remove()를 실행시켜 주어야한다.

void lab2_tree_delete(lab2_tree *tree) {
    lab2_node *temp = tree -> root;
    if(!temp) return;
    while(temp) {
        int key = temp -> key;
        lab2_node_remove(tree, key);
        temp = tree -> root;
    }
}

int lab2_node_remove(lab2_tree *tree, int key) {
    lab2_node *temp = tree -> root;
    lab2_node *parent, *child = NULL;
    if(temp == NULL) {
        return SUCCESS;
    }
    while(temp -> key != key) {
        if(temp -> key < key) {
            parent = temp;
            temp = temp -> right;
        } else {
            parent = temp;
            temp = temp -> left;
        }
    }
    if(temp -> left == NULL && temp -> right == NULL) { // 아래에 자식 노드가 없을 경우
        if(parent -> left == temp) {
            parent -> left = NULL;
        }
        if(parent -> right == temp) {
            parent -> right == NULL;
        }
        lab2_node_delete(temp);
        return SUCCESS;
    }
    if(temp -> left == NULL || temp -> right == NULL) { // 아래에 1개의 자식 노드가 있을 경우
        if(temp -> left) {
            child = temp -> left;
        } else {
            child = temp -> right;
        }
        if(parent -> left == temp) {
            parent -> left = child;
        } else {
            parent -> right = child;
        }
        lab2_node_delete(temp);
        return SUCCESS;
    }
    if(temp -> left != NULL && temp -> right != NULL) { // 아래에 2개의 자식 노드가 있을 경우
        lab2_node *temp2 = temp;
        temp2 = temp2 -> right;
        if(temp2 -> left == NULL) {
            lab2_node *left_temp = temp -> left;
            child = temp2;
            if(parent -> right == temp) {
                parent -> right = child;
                child -> left = left_temp;
            } else {
                if(parent -> left == temp) {
                    parent -> left = child;
                    child -> left = left_temp;
                }
                lab2_node_delete(temp);
                return SUCCESS;
            }
            while(temp2 -> left != NULL) {
                parent = temp2;
                temp2 = temp2 -> left;
            }
            parent -> left = NULL;
            temp -> key = temp2 -> key;
            lab2_node_delete(temp);
        }
        return SUCCESS;
    }
}

중간에 보면, lab2_node_delete()의 쓰임새이다. 노드를 지울때 사용하라 정의 해둔것 같다. 노드를 제거할 때는
free()로 메모리할당을 제거하지 않으면, 메모리 누수가 발생하고 오래 사용되어 이게 쌓이게 되면 결국 성능저하로 이어진다. 이 메모리해제를 하는 부분을 lab2_node_delete() 에서 수행하라는 뜻에서 만들어 둔게 아닌가 예상해본다.

void lab2_node_delete(lab2_node *node) {
    free(node);
}

이렇게 사용해준다.

[hs-krispy]

2개의 자식노드가 있는 경우 수정제안

if(temp -> left != NULL && temp -> right != NULL) {
    lab2_node *temp2 = temp -> right;
    while(temp2->left != NULL){
        parent = temp2; 
        temp2 = temp2->left;
    }
    temp->key = temp2->key;
    if(temp2->right != NULL){
        parent->left = temp2->right;
    }
    lab2_node_delete(temp2);
}