1. 배열이 정렬되어 있지 않은 경우의 검색 소요 시간을 연결 리스트의 검색 시간과 비교해보기.
2. 값을 검색할 때 이진 검색 트리가 기본 연결 리스트에 비해 가지는 장점과 단점은 무엇이 있을까?

boostcourse의 모두를 위한 컴퓨터 과학 (CS50 2019) 강의를 듣고 정리한 필기입니다. 😀

1.연결 리스트 : 장단점

1.1 장점 : 유동적 구조

배열과 비교해서 연결 리스트는 새로운 값을 추가할 때 다시 메모리를 할당하지 않아도 된다는 장점이 있다. 새 숫자를 넣기 위해서는 malloc을 하면 되고, 그렇기 때문에 원하는 만큼의 리스트를 만들 수 있다는 것이다. 예시에서는 고작 4였지만 40번, 400번 더 리스트를 추가할 수도 있다. 즉, 연결리스트의 장점은 배열처럼 숫자를 정렬하며 추가하기 위해서 크기를 조절하고 기존값을 옮기는 일을 하지 않아도 된다는 것이다. 그저 node의 number 필드와 추가할 값을 비교해 next 필드를 수정하는 되는 것이다. 때문에 우리는 연결리스트로 자료구조를 만들면 역동성을 추가한다는 장점이 있다.

1.2 단점 : 임의 접근법 상실

하지만 이런 유동적인 구조는 그 대가가 따른다. 구조가 정적인 배열과 달리 연결 리스트에서는 임의 접근이 불가능하다.

연결리스트는 메모리 덩어리들로 이루어져 있고, 컴퓨터는 한 번에 하나의 메모리만 볼 수 있다. 즉, 컴퓨터에게는 위의 그림처럼 보인다는 것이다. 그렇기 때문에 3을 검색하거나 1이나 5가 추가되려면 각자의 위치를 찾기 위해 모든 문을 하나씩 열어봐야 한다. 처음에 추가하면 다행이지만, 중간에 추가해야 한다면 부등호(<,>)와 if문을 이용해야 할 것이다. 그리고 최악의 경우 모든 리스트를 확인해야 할 수도 있다.

따라서 연결 리스트의 크기가 n 일 때 그 실행 시간은 O(n)이 된다. 배열의 경우 임의 접근이 가능하므로 (정렬 되어 있는 경우)이진 검색을 이용하면 O(log n)의 실행 시간이 소요되는 것에 비해서 다소 불리하다는 단점이 있다.

이처럼 여러 데이터 구조는 각각 장단점이 존재한다. 프로그래밍할 때 목적에 부합하는 가장 효율적인 데이터 구조를 고민해서 사용하는 것이 중요하다.

2. 연결리스트 : 트리

배열에서는 기존 배열을 새 배열에 복사해야 해서 조금 오래 걸리지만 크기를 바꿀 수도 있고, 입의 접근을 통해서 이진 탐색도 쓸 수 있기 때문에 정렬된 리스트에서 탐색할 때는 실생시간이 O(log n)이된다. 이러한 점에서, 연결리스트가 배열보다 퇴보적이라고 생각할 수도 있다. 연결리스트에는 역동성이 있기 때문에 값을 옮기는 시간을 낭비하지는 않지만, 임의접근을 할 수 없다는 사실 때문일 것이다. 하지만 포인터와 자료구조를 사용해서 메모리에 여러 요소를 잇고 화살표를 통해서 붙여서 더 좋은 것을 만들 수 있다. 지금부터 볼 것은 연결리스트를 기반으로 한 새로운 데이터 구조이다.

연결리스는 각 노드들의 연결이 1차원적으로 구성되어있다면, 트리는 2차원적인 연결로 구성되어있다. 트리에는 층이 존재하고 각노드들이 규칙에 의해 일정 층에 속하게 된다. 그리고 마치 가게도처럼 다음층의 노드를 가리키는 포인터를 가지게 된다. 위 사진은 해리포터에 나오는 블랙가문의 가게도이다. 트리는 마치 저런 모습으로 위에서부터 아래로 내려오게된다.

배열에서 이진탐색을 할 때를 떠올려보자 위와 같은 정렬된 배열이 있다고 하자.

1차원일 때 우리가 처음으로 한 것은 중간부터 찾았을 것이다.

그 다음은 찾는 숫자에 따라 왼쪽 또는 오른쪽의 중간 값을 찾았다.

그 다음 또한 찾는 값에 따라 왼쪽 또는 오른쪽의 값을 열어본다.

이제 이러한 것을 2차원적으로 표현하면 위 사진과 같다. 1, 2, 3, 4, 5, 6, 7이 들어있는 배열이지만, 서로 다른 높이에 표시되어있다. 이것은 이진탐색트리와 마찬가지로 중간인 4에서 시작해서 왼쪽이나 오른쪽으로 간다. 그리고나서 다음 층인 2와 6을 살펴보고 다시 왼쪽이나 오른쪽으로 갈 것이다. 완전히 이진탐색트리와 같은데 2차원적으로 표현되었다. 이것을 1부터 7까지 순서대로 연결하는 것은 그냥 연결리스트와 같다.

그래서 연결리스트와는 달리 포인터의 방향은 위 그림과 같다. 더 많은 공간을 할당하고 노드들을 이어붙여서 개념상 2차원을 만드는 것이다. 트리는 꼭 하나의 포인터만 가져야할 필요는 없다. 연결리스트에서는 next라는 하나의 포인터만을 가졌던 것과는 달리 두 개의 포인터를 가진 구조체(node)를 만들면 되는 것이다.

typedef struct node
{
    int number;
    struct node *left;
    struct node *right;
}

위 코드는 가계도와 같은 트리를 만드는데에 사용되며, 좀 더 정확하게는 이진 탐색 트리라고 부른다. 왼쪽 포인터를 left, 오른쪽은 right라고 하면 된다.

가장 높은 층에서 트리가 시작되는 노드를 ‘루트’라고 한다. 그리고 루트 노드는 다음 층의 노드들을 가리키고 있고, 이를 ‘자식 노드’라고 한다. 트리의 노드들이 모두 최대 두 개의 자식 노드가 있고, 그래서 이진법의 이진을 따와서 ‘이진’ 탐색 트리이라는 표현을 사용했다. 또한, 순서를 맞추기 위해 신경을 썼다는 의미로 이진 ‘탐색’ 트리라는 표현을 사용한 것이다.

위 그림을 보면 규칙을 한 개 더 알 수 있는데, 모든 노드에서 오른쪽 자신이 더 크고, 왼쪽은 더 크다. 이것은 사실 재귀에 가장 적합한 방법이다. 이전에 Mario의 피라미드를 만들 때나 팩토리얼이나 어떤 수를 계속 더하는 것 같은 재귀를 말하는 게 맞다. 이것이 재귀적인 이유는 어떤 노드에서라도 왼쪽이 더 작고, 오른쪽이 더 크다는 것이다.

이진탐색트리는 이진 탐색을 할 수 있다는 장점이 있다. 포인터를 이용했기 때문에 연결 리스트처럼 역동성도 가진다. 위 그림처럼 가장 작은 수가 될 0을 추가하면 1의 왼쪽으로 갈 것이고, 가장 큰 수가 될 8을 추가하면 7의 오른쪽으로 가게 될 것이다. 배열처럼 무언가를 복사하고 붙여넣는 등의 활동이 없어도 추가할 수 있다.

bool search(node *tree)
{
    if(tree === NULL){
        return false;
    }
    else if (50 < tree->number) {
        return search(tree->left)
    }
    else if (50 > tree->number)
    {
        return search(tree->right);
    }
    else {
        return true;
    }
}

위는 search라는 함수는 트리를 탐색해 50이 있으 면true, 없으면 false를 반환한다. 방법은 다음과 같다.

일단 매개변수로 node *tree 즉, 트리를 입력받는다. 정확히는 트리의 주소(* 연산자가 tree 앞에 있다.)일 것이다. 트리를 탐색하려면 연결리스트에서처럼 트리의 가장 위에 있는 노드만 알려주면 된다. 그러면 해당 트리의 모든 곳으로 갈 수 있다.

다음으로는 전달받은 주소가 NULL인지 아닌지를 확인해야한다 . NULL이라면 false를 반환해야 할 것이다. 특50이 존재하는지를 묻기 위해서는 트리가 존재한다는 전재 조건이 필요하기 때문이다. 트리가 없다면 50도 없다.

이제 50이 tree의 number보다 크냐 작냐를 확인하면 된다. 더 작으면 왼쪽으로 가면 될 것이고, 더 크다면 오른쪽으로 가면 될 것이다. 그리고 tree의 number가 50보다 크지도 작지도 않다면, tree의 number는 50과 같은 수이기 때문에 true를 반환하게 될 것이다.

그렇다면 이진 탐색트리의 속도는 어떨까? 이진탐색은 배열과 같은 실행시간을 갖는다.

트리의 높이는 로그를 따른다. 위 그림은 정확히 밑이 3인 로그인 것이다. 이 트리에서 9개의 요소가 있다면 어떠한 값을 찾는데 최대 4단계 밖에 걸리지 않는다. (7개의 요소가 있으면 3단계가 걸릴 것이다.) 필요한 단계 수가 O(n)이 아니라 log n이 된다.

이진탐색을 추가할 때도 마찬가지이다. 추가하고 싶은 숫자를 여기저기에다가 넣을 수는 없다. 계속해서 작은 숫자를 넣거나 계속해서 큰 숫자를 넣으면 트리가 아주 얇고 길어진다. 왼쪽이나 오른쪽 둘 중 하나만 길어지는 것이다. 이렇게 된다면 트리는 균형을 잃게 된다. 그래서 이진 검색 트리의 균형을 유지할 수 있는 알고리즘이 존재한다. 즉, 1, 2, 3, 5, 6, 7, 8로 이루어진 트리에다가 4를 추가하게 되면 요소들을 움직이게 된다는 것이다. 이때 기존에 있던 트리를 삭제하는 것이 아니라 그냥 포인터를 업데이트해서 자료구조가 길어지는 것을 막는다. 이러한 이유로 이진 탐색트리의 추가도 log n 이라는 시간복잡도를 갖는다.

아래는 이진탐색 트리를 구현한 것이다.

//이진 검색 트리의 노드 구조체
typedef struct node
{
    // 노드의 값
    int number;

    // 왼쪽 자식 노드
    struct node *left;
 
   // 오른쪽 자식 노드
    struct node *right;
} node;

// 이진 검색 함수 (*tree는 이진 검색 트리를 가리키는 포인터)
bool search(node *tree)
{
    // 트리가 비어있는 경우 ‘false’를 반환하고 함수 종료
    if (tree == NULL)
    {
        return false;
    }
    // 현재 노드의 값이 50보다 크면 왼쪽 노드 검색
    else if (50 < tree->number)
    {
        return search(tree->left);
    }
    // 현재 노드의 값이 50보다 작으면 오른쪽 노드 검색
    else if (50 > tree->number)
    {
        return search(tree->right);
    }
    // 위 모든 조건이 만족하지 않으면 노드의 값이 50이므로 ‘true’ 반환
    else {
        return true;
    }
}