6) 연결 리스트: 트리

트리의 구조를 설명하고 활용하는 코드를 작성할 수 있습니다.

 

• 트리
• 루트

 

 

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

연결리스트에서의 각 노드 (연결 리스트 내의 한 요소를 지칭)들의 연결이 1차원적으로 구성되어 있다면, 트리에서의 노드들의 연결은 2차원적으로 구성되어 있다고 볼 수 있습니다.

각 노드는 일정한 층에 속하고, 다음 층의 노드들을 가리키는 포인터를 가지게 됩니다. 

 

아래 그림은 트리의 한 예입니다. 나무가 거꾸로 뒤집혀 있는 형태를 생각하면 됩니다.

가장 높은 층에서 트리가 시작되는 노드를 ‘루트’라고 합니다. 루트 노드는 다음 층의 노드들을 가리키고 있고, 이를 ‘자식 노드’라고 합니다. 

위 그림에 묘사된 트리는 구체적으로 ‘이진 검색 트리’ 입니다.

각 노드가 구성되어 있는 구조를 살펴보면 일정한 규칙을 알 수 있습니다.

먼저 하나의 노드는 두 개의 자식 노드를 가집니다.

또 왼쪽 자식 노드는 자신의 값 보다 작고, 오른쪽 자식 노드는 자신의 값보다 큽니다.

따라서 이런 트리 구조는 이진 검색을 수행하는데 유리합니다.

 

추가적으로 만약에 0과 8을 추가한다고 해보자 그러면 0은 4보다 작으므로 왼쪽으로 가고 8은 오른쪽으로 가면 쭉쭉 내려간후 추가하면된다!

 

 

아래 코드에서는 이진 검색 트리의 노드 구조체와 “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) 입니다.