자료구조) 이진트리

이진 트리(Binary Tree)는 각 노드가 최대 두 개의 자식 노드를 가지는 계층적 자료구조이다. 이러한 구조는 빠른 탐색, 정렬, 계층적 데이터 표현 등에 유용하며, 다양한 알고리즘과 데이터 구조의 기반이 된다.

이진 트리를 사용하는 이유

• 탐색 속도 향상

  • 배열(Array)과 연결 리스트(Linked List)에서는 탐색이 O(n)이다.

  • 이진 탐색 트리(Binary Search Tree, BST)를 사용하면 평균 탐색 속도가 O(log n)까지 줄어든다.

• 정렬 및 균형 유지

  • 힙(Heap)이나 AVL 트리 같은 균형 이진 트리를 활용하면 정렬된 데이터를 빠르게 검색할 수 있다.

• 트리 구조 데이터 표현

  • 파일 시스템, 계층적 메뉴, 조직도 등 계층적 데이터 표현이 필요할 때 유용하다.

• 효율적인 연산

  • 트리 기반 알고리즘은 그래프 탐색(DFS, BFS), 데이터 압축(Huffman Coding), AI(Search Trees) 등 다양한 분야에서 활용된다.

이진 트리의 구조

이진 트리는 노드(Node)들로 이루어진 계층적 구조를 가진다. 각 노드는 다음과 같은 정보를 가진다.

struct Node {
    T item = T();       // 저장할 데이터
    Node* left = nullptr;  // 왼쪽 자식 노드
    Node* right = nullptr; // 오른쪽 자식 노드
};

• item: 노드가 저장하는 데이터이다.
• left: 왼쪽 자식 노드를 가리킨다.
• right: 오른쪽 자식 노드를 가리킨다.
• 루트(Root) 노드: 트리의 가장 상위 노드이다.
• 단말(Leaf) 노드: 자식 노드가 없는 노드이다.

이진 트리 주요 연산

트리의 높이 계산

트리의 높이는 루트 노드에서 가장 깊은 리프 노드까지의 경로 길이를 의미한다. 높이는 재귀적 방식으로 계산할 수 있다.

int Height(Node* node) {
    if (!node) return 0;
    return 1 + std::max(Height(node->left), Height(node->right));
}

시간 복잡도: O(n)

노드의 합 계산

모든 노드의 값을 합산하는 연산이다. 이 역시 재귀적 방식으로 수행된다.

int Sum(Node* node) {
    if (!node) return 0;
    return node->item + Sum(node->left) + Sum(node->right);
}

시간 복잡도: O(n)

트리 순회 방법

이진 트리는 다양한 방법으로 순회(Traversal)할 수 있다. 각 순회 방법은 노드 방문 순서에 따라 달라진다.

전위 순회 (Preorder)

루트 → 왼쪽 → 오른쪽 순서로 방문한다.

void Preorder(Node* node) {
    if (node) {
        Visit(node);
        Preorder(node->left);
        Preorder(node->right);
    }
}

출력 예시: A B D E C F G

중위 순회 (Inorder)

왼쪽 → 루트 → 오른쪽 순서로 방문한다.

void Inorder(Node* node) {
    if (node) {
        Inorder(node->left);
        Visit(node);
        Inorder(node->right);
    }
}

출력 예시: D B E A F C G

이진 탐색 트리(BST)에서는 중위 순회 시 **“오름차순 정렬”된 결과를 얻을 수 있다.**

후위 순회 (Postorder)

왼쪽 → 오른쪽 → 루트 순서로 방문한다.

void Postorder(Node* node) {
    if (node) {
        Postorder(node->left);
        Postorder(node->right);
        Visit(node);
    }
}

출력 예시: D E B F G C A

트리를 삭제할 때 유용하다. (자식 노드를 먼저 삭제한 후, 부모 노드를 삭제)

레벨 순회 (Level Order)

루트에서 시작하여 같은 깊이의 노드를 먼저 방문하는 방식이다. 큐(Queue)를 사용하여 구현한다.

void LevelOrder() {
    if (IsEmpty()) return;

    Queue<Node*> nodeQueue;
    nodeQueue.Enqueue(root);

    while (!nodeQueue.IsEmpty()) {
        Node* currentNode = nodeQueue.Front();
        nodeQueue.Dequeue();

        Visit(currentNode);

        if (currentNode->left) nodeQueue.Enqueue(currentNode->left);
        if (currentNode->right) nodeQueue.Enqueue(currentNode->right);
    }
}

시간 복잡도: O(n)

이진 트리 삭제 (Post-order)

트리를 삭제할 때는 후위 순회(Postorder Traversal) 를 사용하여, 자식 노드를 먼저 삭제한 후 부모 노드를 삭제해야 한다.

void DeleteTree(Node* node) {
    if (node) {
        DeleteTree(node->left);
        DeleteTree(node->right);
        delete node;
    }
}

메모리 누수를 방지하기 위해 중요하다.

이진 트리의 특징

특징	설명
시간 복잡도	삽입, 삭제, 탐색 평균 O(log n) (BST 기준)
균형 유지 여부	균형이 맞지 않으면 최악의 경우 O(n)
데이터 저장	계층적 구조를 활용한 정렬 및 탐색 가능
메모리 사용	연결 리스트 기반이라 추가적인 포인터 공간 필요

---

이진 트리 vs. 선형 자료구조 비교

비교 항목	배열/연결 리스트	이진 트리
삽입/삭제	O(n)	O(log n) (BST 기준)
탐색 속도	O(n) (정렬되면 O(log n))	O(log n)
공간 효율성	낮음 (정렬 유지 필요)	높음 (연결 기반)
데이터 정렬 유지	수동 정렬 필요	자동 정렬 가능 (BST)

이진 트리 활용 예시

• 이진 탐색 트리(Binary Search Tree, BST)
  • 정렬된 데이터를 빠르게 탐색하는 데 사용된다.
• 힙(Heap)
  • 우선순위 큐(Priority Queue) 구현에 활용된다.
• 트라이(Trie)
  • 문자열 검색, 자동 완성 기능에 사용된다.
• 허프만 트리(Huffman Tree)
  • 데이터 압축 알고리즘에서 활용된다.