정글사관학교 35일차 TIL: 이진탐색트리 with 연결 리스트, make & Makefile

RB트리를 구현하기 전에 개념을 익힐 겸 연결 리스트로 이진 트리를 구현하는 연습(by C)을 진행한다. 공부자료는 이것을 참조함.

 

이진트리 with 연결리스트

1. 이진탐색트리(Binary Search Tree, BST)란?

원소를 특정한 조건에 따라 정렬해 놓은 이진 트리를 말한다.

2. 이진탐색트리 특징

• 모든 원소는 유일한 키값을 갖는다. (중복 내용을 갖는 항목은 없다.)
• 왼쪽 서브트리의 모든 원소들은 루트의 key보다 작은 값을 갖는다.
• 오른쪽 서브트리의 모든 원소들은 루트의 key보다 큰 값을 갖는다.
• 왼쪽/오른쪽 서브트리 역시 이진 탐색 트리이다.(재귀적으로 정의된다.)

3. 이진탐색트리에서 탐색 시 시간 복잡도

이진탐색트리에서 특정한 키값을 찾을 때, 그 값이 비교하려는 노드의 값보다 크면 오른쪽 서브트리를 방문하고 작으면 왼쪽 서브트리를 방문한다. 이 시점에서, 한 서브트리로 진입하는 순간 반대편 서브트리는 전혀 고려할 필요가 없어진다. 때문에 한 번 방문할 때마다 검색 대상이 1/2씩 줄어들어 시간복잡도는 O(logN)이다.

4. 이진탐색트리에서 3가지 연산: 탐색 / 삽입 / 삭제

1) 탐색

루트 노드를 주고서 우리가 찾고 싶은 x라는 key값을 찾는다. => search(root, x) 그러면 x를 root값부터 비교해가면서 root보다 크면 오른쪽 서브트리를, root보다 작으면 왼쪽 서브트리를 방문한다. 만약 x가 root값과 같으면 바로 root를 반환한다. 위의 3번에서 시간 복잡도에 대해 설명하면서 탐색이 어떻게 진행되는지 그 메커니즘을 소개했는데 이를 보다 자세하게 코드로 살펴보자.

 

search함수를 만들어보자. 이때, search 함수의 반환형은 노드 구조체를 가리키는 포인터 형이다. 그래야 나중에 삽입/삭제 시에도 계속해서 이 search 함수를 갖다쓸 수 있다.

 

먼저, 인자로 준 root를 받아 내부에 root를 가리키는 구조체 포인터 p를 선언한다. 자식이 없는 노드는 양끝에 NULL을 달고 있으니 이 p값이 NULL이 될 때까지, 즉 트리의 맨끝에 방문할 때까지 우리가 찾고자 하는 x와 방문하는 노드의 key값을 비교해가며 계속 이동시킨다. 이때, p->key가 x값과 같으면 바로 p를 반환하고, 그렇지 않으면 x와 key 값을 비교해 왼쪽 혹은 오른쪽 자식 노드로 p가 가리키는 노드의 위치를 옮긴다.

 

Node* searchBST(Node* root, char x){
    Node* p = root;
    while (p!=NULL){
        if (p->key == x)
            return p;
        else if (p->key < x) 
            p = p->right;
        else
            p = p->left;
    } 
    return NULL;

 

2) 삽입

이제 새로운 노드를 삽입하는 경우를 생각해보자. 노드는 어디서 삽입해야 할까? 위에서 언급한 이진탐색트리(이하 BST)의 특징 중 하나는 바로

• 모든 원소는 유일한 키값을 갖는다. (중복 내용을 갖는 항목은 없다.)

이다. 따라서, 새로운 노드를 삽입한다고 하면 이 새로운 노드의 키값은 반드시 기존 BST에 있지 않아야 한다. 그렇다는 말은 즉, 기존 이진탐색 트리를 탐색해서 새로운 노드에 대한 값을 찾으려고 한다면 탐색에 실패할 것이다. 근데 그 실패했다고 알리는 위치는 기존 이진 탐색 트리를 스캔하면서 새로운 노드가 들어가야 하는 자리에 해당한다. 따라서 탐색에 실패한 그 위치에다가 새로운 노드를 삽입하면 된다. 이는 즉, 기본적으로 탐색을 먼저 해야 한다는 말이 된다. 아래 코드를 살펴보자.

 

Node* insertBST(Node* root, char x){
    Node* p = root;
    Node* parent = NULL; //p의 발자취를 따라가는 변수 -> parent가 한 발짝도 못 갈 수 있음 -> 그때는 루트 자체에다가 새 노드 삽입! 
    while (p!=NULL){
        parent = p;
        if (p->key == x)  {
            printf("같은 키가 있습니다.\n");
            return p;
        }
        else if (p->key <x)
            p = p->right;
        else
            p = p->left;
    }
    // 이 시점이 찾기 실패했을 때! 즉, p가 가리키는 값이 NULL인 상황
    // 1. 새 노드 할당: 아직 기존 트리에 붙이지는 않고 노드만 만들어둔 상황

    Node *newNode = (Node *)malloc(sizeof(Node));
    newNode->key = x;
    newNode->left = newNode->right = NULL;

    //2.parent의 자식으로 새 노드 붙이기: 왼쪽 자식에 붙일 거니 오른쪽 자식에 붙일 거니?
    if (parent != NULL) {
        if (parent->key < newNode->key)
            p->right = newNode; //newNode가 포인터니까
        else
            p->left = newNode;
    }
    return newNode;
}

 

노드 포인터 형을 반환하는 함수 insertBST를 보면 위의 9줄까지는 searchBST와 동일하다. 그런데 while문이 종료될 때까지 search함수는 새로운 노드를 기존 트리 값과 비교해가며 새로운 노드가 위치해야 할 장소까지 포인터를 이동할 것이다. 먼저, 그 상황에서 새로운 노드에 대한 메모리를 동적으로 할당한다. 

 

그런데 search 함수 부분을 보면 뭔가 다른 점이 하나 있다. 바로 parent의 존재. 코드를 보면 parent는 NULL에서 출발해 갱신되기 이전의 p값을 이어받는다. 즉, p의 부모 노드라고 생각하면 된다. 이렇게 parent를 만드는 이유는 p가 NULL까지 가게 될 경우 그 위의 노드가 무엇인지 보고서 그 노드를 기준으로 삽입해야 하기 때문이다.

 

3. 삭제

 

삭제는 좀 더 까다로운 편인데, 일단 코드만 먼저 붙여두고 이어서 설명할 예정. 삭제하려는 노드가 1) 자식 노드가 0(=차수가 0)인 경우, 2) 차수가 1인 경우, 차수가 2인 경우 이렇게 세 가지 경우로 나눈다고만 미리 말해둔다.

 

// 노드 삭제
Node* deleteBST(Node* root, char x){
    Node* p = root;
    Node* parent = NULL; //p의 발자취를 따라가는 변수 -> parent가 한 발짝도 못 갈 수 있음 -> 그때는 루트 자체에다가 새 노드 삽입! 
    while((p!=NULL) && (p->key != x)) { // key를 만나거나 삭제할 게 없으면 while문 종료!
        parent = p;
        if (p->key < x)
            p = p->right;
        else
            p = p->left;
    }
    if (p == NULL) {
        printf("찾는 노드가 없습니다.\n");
        return root;
    }
    // 이 아래부터는 p->key == x인 상황

    if (p->left == NULL && p->right == NULL) { // 차수가 0인 경우
        if (parent == NULL)
            root = NULL; // 해당 노드가 루트 노드인 경우! 루트를 삭제
        else {
            if (parent->left == p)
                parent->left = NULL;
            else
                parent->right = NULL;

        }
    }

    else if (p->left == NULL || p->right == NULL) { // 차수가 1인 경우! 이렇게 쓰면 0인 것도 들어오는데 차수가 0인 케이스는 위에서 걸러짐.
        Node* child = (p->left != NULL) ? p->left : p->right; //3항 연산자: p->left가 0이 아니면 걔를 child가 가리키게 하고 p->right !=0이면 걔를 child가 가리키게.
        if (parent == NULL) // 루트 노드를 삭제하는 케이스
            root = child; // 바로 아래 자식이 루트가 된다. => 최종적으로 root 반환
        else {
            if (parent->left == p)
                parent->left = child;
            else
                parent->right = child;
        }
    }

    else {// 차수가 2 => 후계자를 찾으러 떠나야 하니까 succ_parent, succ를 만드는 것!
        Node* succ_parent = p; // 후계자의 parent 노드를 유지하면서 따라간다
        Node* succ = p->right; // 후계자를 오른쪽 서브트리에서 찾으려고 하니 p->right 
        while (succ->left != NULL) {
            succ_parent = succ; // succ parent는 현재 succ를 가리키게 하고
            succ = succ->left; // succ는 왼쪽 자식 노드를 가리키게 옮겨. 
        }

        p->key = succ->key; // 후계자가 해당 노드의 값으로 가게 한다. 우리는 p를 삭제하는 게 아니라 succ를 삭제할 것.
        if (succ_parent->left == succ) // 후계자가 후계자 부모의 왼쪽 자식 노드라면 
            succ_parent->left = succ->right; // 현재 succ_parent의 왼쪽노드에는 암것도 없어야 할 상황이니 오른쪽 자식을 가리키게 한다.
        else
            succ_parent->right = succ->right; // 오른쪽 가리키던 곳은 그대로 오른쪽.
        p = succ;
    }
    
    free(p);
    return root; // root가 위의 과정을 통해 값이 바뀌었을 수 있으니 root를 반환!
}

 

 

 

 

 

 

typedef

typedef: struct 키워드 없이 구조체의 이름만으로 구조체를 선언할 수 있도록 하는 메소드.

- 참조: https://dojang.io/mod/page/view.php?id=409

ifndef

ifndef: 헤더파일 중복 방지 코드

- 참조: https://dhhwang89.tistory.com/59

make & Makefile

아까 잠깐 팀원 형한테 디버깅 도움을 받았는데, 가만 보니 gcc 명령어를 입력하지 않고 make를 입력해서 바로 실행하더라. C언어 실행할 때면 vscode에서 플레이 버튼을 눌러 일일이 실행했는데 이렇게 하니 실행도 훨씬 빨랐다.

뿐만 아니라, 디버깅하면서 알게 된 사실인데 단일 파일만 있을 때와 달리 헤더 파일을 포함해 여러가지 object 파일을 묶어서 실행해야 할 경우에는 vscode에 있는 플레이 버튼을 누르면 실행이 되지 않더라.vscode로 플레이 버튼을 눌러 실행하면 약간 딜레이가 있는 편인데다가 아래처럼 실행되지 않는 상황까지 벌어지니 이제는 CLI로 컴파일해줘야 될 듯 하다.

 makefile 없이 플레이 버튼으로 실행하면 헤더 파일과 구현 파일, 그리고 main.c 사이에 참조가 되지 않아 에러가 뜨는 것을 볼 수 있다.

그런데 원래 gcc로 컴파일하려면 모든 오브젝트 파일 이름을 묶어줘야 하는데 shell에서 해당 디렉토리에 makefile 파일이 있다면, 오직 make 명령어로 컴파일을 실행한다. 이게 어떻게 가능한지 살펴보니, make 라는 명령어가 파일 관리 유틸리티이기 때문이다. 설명을 읽어보면

파일 간의 종속관계를 파악해 Makefile(기술파일)에 적힌대로 컴파일러에 명령하여 shell 명령이 순차적으로 실행될 수 있게 한다.

라고 나와있다.

make를 쓰는 이유

이미 위에서 썼듯, gcc 컴파일러를 쓰려면 main을 실행하기 위해 관련 오브젝트 파일을 전부 만들어줘야 한다. 하지만 make를 쓰게 되면 세 가지 장점이 있다.

1. 각 파일에 대한 반복적 명령의 자동화로 인한 시간 절약
2. 프로그램의 종속 구조를 빠르게 파악할 수 있으며 시간 관리 용이
3. 단순 반복 작업 및 재작성을 최소화

이게 무슨 말인고 하니, 위에서 연습 예제로 다뤘던 이진 트리 순회하는 파일을 실행하는 경우를 생각해보자.

1. gcc를 이용한 기본적인 컴파일 과정

현재 디렉토리에는 BinaryTreeList.c, BinaryTreeList.h(헤더파일), main.c 이렇게 세 가지 파일이 있다.

1) C파일에서 object 파일 생성하기

먼저 각각 C파일에 대한 오브젝트 파일을 만들어줘야 하니

gcc -c -o BinaryTreeList.c
gcc -c -o main.c

라고 명령어를 입력해 각 c 파일에 대한 오브젝트 파일을 생성한다.

2) 각 object 파일을 묶어 컴파일해 main.exe 실행하기

그 다음에는 실행 파일을 만들어줘야 하는데, 위에서 말한 것처럼 모든 오브젝트 파일을 묶어서 컴파일해 실행 파일을 생성한다.

gcc -o main.exe main.o BinaryTreeList.o

이를 실행하면 실행 파일 main.exe가 생성된다.

이제 이 파일을 실행하면 우리가 원하던 결과가 출력된다.

2. Makefile을 이용한 컴파일 과정

근데 이 과정을 make 명령어 단 하나만으로 실행할 수 있다. 물론, 그 전에 Makefile 파일을 미리 만들어둬야 한다. Makefile을 만드는 과정은 아래 링크를 보면 보다 자세하게 이해할 수 있으니 Makefile 관련은 여기까지.

참고 링크: https://bowbowbow.tistory.com/12#make-makefile-%EC%9D%B4%EB%9E%80