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

학습 목표

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

 

1. 트리

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

연결리스트에서는 각 노드들의 연결이 1차원적으로 구성되어 있다면, 트리에서 각 노드들의 연결은 2차원적으로 구성되어 있다고 볼 수 있다.

연결리스트에서 각 노드들이 다음에 오는 노드를 가리키는 메모리 주소를 기억하고 있었다면, 트리에서 노드는 다음에 오는 노드들을 가리키고 있다.

• 이 그림은 트리의 예를 보여주고 있는데, 나무가 거꾸로 뒤집혀 있는 모습을 생각해보면 된다.
• 가장 높은 층에서 트리가 시작되는 노드를 루트라고 한다. (4번 노란색 노드)
• 연결 리스트에서 node 라는 이름의 구조체에서는 *next 필드가 정의 되어 있었다면, 그림에서 보면 알 수 있듯이 트리는 왼쪽, 오른쪽 2개의 노드를 가지고 있다.
• 트리는 이진검색이 가능하다. 트리의 구조를 보면 규칙이 보이는데, 하나의 노드를 기준으로 자신의 왼쪽에 있는 노드는 자신의 값 보다 작고, 오른쪽에 있는 노드는 자신의 값보다 크다.
  
  

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)이다.
  
  

3. 이진 검색 트리

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

3.1 장점

• 포인터를 따라 각 노드의 값들을 전부 확인해서 가야하는 연결 리스트에 비해 이진 검색을 사용해 기준을 정하고 범위를 반으로 좁혀 나갈 수 있으므로 검색 시간이 줄어들어 효율적이다.
• 실행시간과 삽입시간이 둘 다 O(log n)이라 시간 복잡도가 좋다.

3.2 단점

• 바로 다음 메모리 주소를 기억하고 있으면 되는 연결 리스트에 비해 이진 검색 트리는 2개의 노드들의 주소를 기억해야 하므로 메모리를 더 많이 차지한다.
• 삽입되는 노드의 값이 불균형해질 수 있다. 예를 들어 값들이 계속해서 왼쪽에 삽입이 되면 트리의 균형이 한쪽으로 치우칠 수 있다.
  이는 이진 검색의 장점을 살렸다고 보기 어렵다.