<자료구조> 트리구조

* 연결리스트의 장단점

 - 연결리스트는 배열과 달리 새로운 값을 추가하면 메모리를 추가하지 않아도 되었다.

 

 - 그러나 배열과 달리 임의 접근이 불가능하다.

 

 - 위와 같은 단점은 값의 추가, 검색에서 손실을 가져온다. 추가와 검색을 위해 연결리스트의 각 node를 하나하나 이동해야하기 때문이다.

 

 - 배열의 경우에는 정렬만 되어 있다면 임의 접근이 가능하여 이진검색을 이용하면 O(log n)의 실행시간을 갖는다. 그러나 위와 같은 단점때문에 연결리스트는 O(n)이 된다.

 

* 트리구조의 등장

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

 

 - 연결리스트에서 노드의 연결이 1차원이었다면 트리에서의 노드의 연결은 2차원이다.

 

 - 위에서 언급되었던 단점을 해결한 '이진 검색 트리' 를 살펴보자.

 

 - 가장 높은 층에서의 노드는 '루트' 노드라고 한다.

 

 - 루트 노드 아래의 노드들은 '자식' 노드라고 한다.

 

 - 위의 트리구조가 갖는 규칙을 보자. 왼쪽 자식노드가 자신의 값보다 반드시 작고, 오른쪽 자식노드는 반드시 자신보다 크다. 이는 재귀적 정의를 따른다.

 

 - 위와 같은 트리구조는 이진검색에서 매우 유리하다.

 

 - 만약 22를 재귀적으로 검색하는 함수를 구현한다고 하자. 그럼 다음과 같이 코드를 작성할 수 있을 것이다.

 

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

// 이진 검색 함수 (*tree는 이진 검색 트리를 가리키는 포인터)
bool search(node *tree)
{
    if (tree == NULL)
    {
        return false;
    }
    else if (22 < tree->number)
    {
        return search(tree->left);
    }
    else if (22 > tree->number)
    {
        return search(tree->right);
    }
    else {
        return true;
    }
}

 

 - 코드를 살펴보면 트리가 비어있으면 함수를 종료하고, 모든 조건이 만족하지 않으면 노드의 값이 22이므로 바로 true를 반환한다.

 

 - 22보다 작으면 왼쪽 노드를 확인하고 22보다 크면 오른쪽 노드를 확인한다.

 

 - 이진 검색 트리를 활용하면 검색시간, 삽입시간 모두 O(log n)이 된다.

 

 

---

 

 

참고

 

 

 이 글은 하버드 대학교 David Malan 교수의 CS50 강의를 수강 후 정리하며 쓴 글입니다. 코드는 C언어로 작성되었으며, 개발환경은 CS50 IDE에 최적화되어 있습니다. 일부 라이브러리는 다른 환경에서 별도의 설정이 필요할 수 있습니다.

 

 

 

CS50 공식사이트

CS50

 

부스트코스

다 함께 배우고 성장하는 부스트코스

 

CS50 IDE

CS50 IDE