[CS50] 자료구조: 연결 리스트 - 트리

❄️ David Malan 교수의 모두를 위한 컴퓨터 과학(CS50 2019)을 바탕으로 정리한 내용입니다.

트리는 연결리스트를 기반으로 한 새로운 데이터 구조입니다.
연결리스트에서의 각 노드 (연결 리스트 내의 한 요소를 지칭)들의 연결이 1차원적으로 구성되어 있다면,
트리에서의 노드들의 연결은 2차원적으로 구성되어 있다고 볼 수 있습니다.
각 노드는 일정한 층에 속하고, 다음 층의 노드들을 가리키는 포인터를 가지게 됩니다.

아래 그림은 트리의 한 예입니다. 나무가 거꾸로 뒤집혀 있는 형태를 생각하면 됩니다.
가장 높은 층에서 트리가 시작되는 노드를 ‘루트’라고 합니다.
루트 노드는 다음 층의 노드들을 가리키고 있고, 이를 ‘자식 노드’라고 합니다.



위 그림에 묘사된 트리는 구체적으로 ‘이진 검색 트리’ 입니다.
각 노드가 구성되어 있는 구조를 살펴보면 일정한 규칙을 알 수 있습니다.

먼저 하나의 노드는 두 개의 자식 노드를 가집니다.
또 왼쪽 자식 노드는 자신의 값 보다 작고, 오른쪽 자식 노드는 자신의 값보다 큽니다.
따라서 이런 트리 구조는 이진 검색을 수행하는데 유리합니다.

아래 코드에서는 이진 검색 트리의 노드 구조체와 “50”을 재귀적으로 검색하는 이진 검색 함수를 구현하였습니다.

//이진 검색 트리의 노드 구조체
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;
    }
}

이진 검색 트리를 활용하였을 때 검색 실행 시간과 노드 삽입 시간은 모두 O(log n) 입니다.

생각해보기

값을 검색할 때 이진 검색 트리가 기본 연결 리스트에 비해 가지는 장점과 단점은 무엇이 있을까요?

• 장점: 리스트의 처음부터 모든 노드를 탐색하며 검색해야 하는 기본 연결리스트에 비해 검색 시간이 O(log n)으로 줄일 수 있습니다.
• 단점: 이진 검색 트리를 구현하기 위해서 left, right과 같은 2개의 노드 포인터 가 필요하기 때문에 더 많은 메모리를 사용합니다. 또한 연결 리스트보다 삽입 및 삭제 작업이 더 복잡합니다.

---

💛 개인 공부 기록용 블로그입니다. 👻

맨 위로 이동하기