C언어로 이진 검색 트리 구현하기 | 트리 자료구조 개념부터 코드까지

🌳 C언어로 트리(Tree) 구조 이해하기

연결 리스트보다 한 단계 더 나아간 자료구조

연결 리스트를 이용하면 데이터를 유연하게 연결할 수 있었다. 하지만 각 노드가 한 노드만을 가리키는 1차원적인 구조였기 때문에, 복잡한 구조를 표현하거나 빠른 검색이 필요할 때는 제한이 있었다.

그래서 등장한 것이 트리(Tree)다. 트리는 연결 리스트의 연장선에서 만들어졌지만, 각 노드가 여러 개의 노드를 가리킬 수 있도록 확장된 구조다. 이번엔 트리의 개념과 함께, C언어로 간단한 이진 검색 트리(Binary Search Tree)를 구현해보았다.

 

Goals

• 트리(Tree)의 구조를 이해하고 직접 구현할 수 있다.
• 연결 리스트와 트리 구조의 차이점 및 장단점을 설명할 수 있다.

 

핵심 개념

• 트리(Tree)
• 루트(Root)
• 이진 검색 트리(Binary Search Tree, BST)
• 재귀(Recursion)

 

트리 구조란?

트리는 루트(root)라고 불리는 하나의 노드에서 시작한다.
루트는 자식 노드(child node)들을 가리키고, 그 자식 노드들도 또 자식들을 가질 수 있다.
이런 식으로 계층 구조를 형성하게 된다.

트리 구조는 마치 거꾸로 된 나무처럼 생겼다.
루트는 위에 있고, 가지처럼 아래로 자식들이 퍼져나간다.

트리는 재귀적인 자료 구조다.
하나의 노드가 또 다른 여러 트리를 포함할 수 있는 구조로 정의되기 때문이다.

 

이진 검색 트리(Binary Search Tree)

이번 글에서는 그 중에서도 이진 검색 트리(BST)를 다룬다.
BST는 각 노드가 최대 2개의 자식 노드를 가지며, 다음과 같은 규칙을 따른다:

• 왼쪽 자식 노드는 현재 노드보다 작은 값
• 오른쪽 자식 노드는 현재 노드보다 큰 값

이 구조 덕분에 값을 빠르게 검색할 수 있다.
검색 시간과 삽입 시간은 평균적으로 O(log n)이다.

 

구조체로 정의하는 트리 노드

typedef struct node
{
    int number;               // 노드가 저장할 값
    struct node *left;        // 왼쪽 자식 노드
    struct node *right;       // 오른쪽 자식 노드
} node;

이 구조체는 재귀적으로 정의된 자료구조다.
자기 자신을 포인터로 가리킴으로써, 무한히 확장 가능한 구조를 만들 수 있다.

 

검색 함수 (재귀 방식)

bool search(node *tree)
{
    if (tree == NULL)
    {
        return false;
    }
    else if (50 < tree->number)
    {
        return search(tree->left);
    }
    else if (50 > tree->number)
    {
        return search(tree->right);
    }
    else
    {
        return true;
    }
}

🔍 어떻게 작동할까?

1. 트리가 비어 있으면 false를 반환하고 종료.
2. 현재 노드 값이 50보다 크면 → 왼쪽 노드로 이동
3. 50보다 작으면 → 오른쪽 노드로 이동
4. 같으면 → true 반환, 즉 찾은 것!

→ 이처럼 재귀 호출을 통해 트리를 순회하며 값을 찾는다.
→ 구조가 재귀적이기 때문에 탐색 함수도 자연스럽게 재귀로 짠다.

 

💡 트리 vs 연결 리스트

  

항목	연결 리스트	트리
구조	1차원	계층적, 2차원
접근 속도	O(n)	O(log n) (평균)
삽입/삭제	쉬움	규칙에 맞춰 조심스럽게 해야 함
임의 접근	불가	불가 (검색 알고리즘 필요)
구현 난이도	낮음	높음

 

생각해보기

배열이 정렬되어 있지 않은 경우의 검색 소요 시간을
연결 리스트의 검색 시간과 비교해보자.

• 정렬되지 않은 배열: O(n)
• 연결 리스트: O(n)
  → 둘 다 최악의 경우는 전부 다 봐야 하니까 똑같다.

하지만 트리는?
→ 이진 검색 트리를 잘 만들면 O(log n)으로 확 줄어든다.
(단, 트리가 너무 한쪽으로 치우치면 O(n)이 될 수도 있음)

---

트리는 연결 리스트에서 출발한 재귀적인 자료 구조다. 단순히 데이터를 나열하는 것을 넘어서, 계층적인 관계나 빠른 검색이 필요한 상황에서 빛을 발한다.

재귀적 정의, 포인터를 통한 참조, 그리고 이진 검색 트리의 규칙을 차근차근 이해하면서, 자료 구조가 실제 문제 해결에 어떻게 쓰이는지 감을 잡아가는 게 중요하다는것✨.