C 이진 트리 삽입/삭제 매개변수로 왜 이중 포인터를 받는지 이해할 수 없어요

Question

C 이진 트리 삽입/삭제 매개변수로 왜 이중 포인터를 받는지 이해할 수 없어요

조회수 1599회

pointer

tree

parameter

0

싫어요

C 이진 트리 삽입/삭제 매개변수로 단일 포인터만 받아도 충분 한 것 같은데 책이나 몇 블로그에선 왜 이중 포인터를 매개변수로 받는지 도무지 이해불가입니다.

다음은 삽입 코드인데요, 삭제는 기니까 삽입만 올릴께요

typedef struct Treenode {
    int key; // 트리의 노드에 들어가는 값
    struct Treenode *left, *right; //해당 노드의 두 자식노드를 가리킬 포인터
} Treenode;

// 밑에서 Treenode* root로 매개변수 형을 바꾸고, //
void insert_treenode(Treenode **root,  int key) 
{
    Treenode
    *p = NULL, //부모 노드, NULL 초기화
    *t = *root, // t = root로 바꾸고,  //
    *n; //새 노드

    //삽입 하려는 키 값이 기존 트리에 이미 있는지 체크
    while (t != NULL)
    {
        if (key == t->key) return; //이미 존재할 경우 함수 종료
        p = t;
        if (key < p->key)
            t = p->left;
        else
            t = p->right;
    } //여기 까지 왔으면 중복된 key값은 없으므로 삽입 가능

    n = (Treenode *)malloc(sizeof(Treenode)); //새 노드를 동적 할당

    if (n == NULL) return;
    //key값 복사
    n->key = key;
    n->left = n->right = NULL;

    //부모 노드와 연결
    if (p != NULL)
    {
        if (key < p->key)
            p->left = n;
        else
            p->right = n;
    }   
    else
        *root = n; // root = n으로 바꾸면 안되나요? //
}

//트리 노드 값 설정합니다
void setTreenode(Treenode *ThisNode, int data, Treenode *L, Treenode *R)
{
        ThisNode->key = data;
        ThisNode->left = L;
        ThisNode->right = R;
}

//main함수
main()
{
    Treenode
        *n0 = (Treenode*)malloc(sizeof(Treenode)),
        *n1 = (Treenode*)malloc(sizeof(Treenode)),
        *n2 = (Treenode*)malloc(sizeof(Treenode)),
        *n3 = (Treenode*)malloc(sizeof(Treenode)),
        *n4 = (Treenode*)malloc(sizeof(Treenode)),
        *n5 = (Treenode*)malloc(sizeof(Treenode)),
        *n6 = (Treenode*)malloc(sizeof(Treenode));

    setTreenode(n0, 30, n1, n2);
    setTreenode(n1, 20, n3, n4);
    setTreenode(n2, 40, n5, n6);
    setTreenode(n3, 13, NULL, NULL);
    setTreenode(n4, 25, NULL, NULL);
    setTreenode(n5, 35, NULL, NULL);
    setTreenode(n6, 50, NULL, NULL);

    insert_treenode(&n0, 4);
}

잘 보면 위 상황에서 t는 결국 현재 트리의 최고봉에 있는 루트 노드를 직접 가리키게 되는데요. 주석에 달린 것 처럼 포인터 범위를 2단계에서 1단계로 줄이도록 코드를 아주 살짝 바꿔도 역시 t는 그때도 루트노드를 가리킵니다.

책에서는 이중 포인터 쓴이유가 삽입에선

"루트 노드 포인터가 변경돼야 하므로..."

삭제에선 "루트 노드가 삭제 및 변경 될 수 있으므로..." 라는 식으로 나오는데

매개변수를 이중포인터까지 안하고도 전혀 문제가 없어보이는데요

VS2017로 직접 돌려봐도 매개변수가 단일 포인터, 이중 포인터일 때 결과는 똑같습니다.

실제로 몇몇 블로그는 단일 포인터만 사용하던데, 왜그럴까요?

(참고로 main함수애서는 Treenode 구조체 타입의 포인터를 선언후 malloc으로 동적 할당 했어요)

(•́ ✖ •̀)
알 수 없는 사용자

main 을 올려주세요. Sunjong Park 2018.11.29 09:32
네 죄송합니다! 알 수 없는 사용자 2018.11.29 10:10
수정했어요! 알 수 없는 사용자 2018.11.29 10:15

댓글 입력

score 1 · Accepted Answer

올려주신 코드 내에서는 특별히 문제가 없습니다만, 예를 들어 Root Node가 교체되는 경우에는 main 함수 내에서 가지고 있는 Root 노드가 교체되어야하는데 Insert 함수에서 Root 노드를 교체해봐야 main 함수의 Root 노드 포인터에 영향을 주지 않으므로 이중 포인터를 매개변수로 넘겨주어야 하는 경우가 발생합니다.

void changeRoot(Node* root)
{
    root = new Node();
}

int main()
{
    Node* root = new Node();
    changeRoot(root);
}

아주 많이 생략하고 간단히 작성한 코드이니 감안하고 보시면 main에서는 root가 변경이 안되어있겠죠.

void changeRoot(Node** root)
{
    *root = new Node();
}

int main()
{
    Node* root = new Node();
    changeRoot(&root);
}

이렇게 바꾸면 main의 root가 바뀌어있겠죠. root를 삭제하는 경우에 반드시 필요하겠죠?

이중포인터를 왜 써야하는지 이해하면 굳이 공식처럼 외울 필요는 없을겁니다.