연결 리스트: 트리

트리는 연결리스트를 기반으로 한 새로운 데이터 구조입니다.

연결리스트에서의 각 노드 (연결 리스트 내의 한 요소를 지칭)들의 연결이 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) 입니다.

 

https://www.boostcourse.org/cs112/lecture/119041?isDesc=false