트리 (1) - 이진 트리(Binary Tree)의 모든 것: 원리, 구조, 예제 코드(C언어 Java, Python), 장단점, 사용 사례

이진트리

 

 

 

데이터 구조를 배우는 데 있어 이진 트리(Binary Tree)는 중요한 개념입니다. 이진 트리는 효율적인 데이터 저장과 검색을 가능하게 하며, 다양한 응용 분야에서 사용됩니다. 또한 코딩 테스트 문제 풀이 시 시간 복잡도를 O(logN)으로 만들어 문제 풀이의 키 아이디어가 되는 경우가 매우 많습니다. 이번 글에서는 이진 트리의 원리, 구조, C/Java/Python으로 구현한 예제, 장단점, 그리고 실생활 사용 사례를 살펴봅니다.

---

1. 이진 트리란? (원리와 개념)

반응형

이진 트리는 각 노드가 최대 두 개의 자식을 가지는 트리 자료구조입니다. 부모-자식 관계로 구성되며, 이진 탐색 트리, 힙, AVL 트리 등 다양한 형태로 확장됩니다.

주요 용어

• 루트(Root): 트리의 시작 노드.
• 부모(Parent): 자식 노드를 가지는 노드.
• 자식(Child): 부모 노드에 연결된 노드.
• 깊이(Depth): 루트에서 특정 노드까지의 거리.
• 레벨(Level): 트리의 특정 깊이에 있는 노드 집합.

---

 

2. 이진 트리의 구조

이진 트리는 다음과 같은 세 가지 형태로 나뉩니다:

1. 포화 이진 트리 (Full Binary Tree)

모든 노드가 두 개의 자식을 가지며, 마지막 레벨까지 노드가 가득 찬 트리입니다.

2. 완전 이진 트리 (Complete Binary Tree)

마지막 레벨을 제외하고 모든 레벨이 채워져 있으며, 마지막 레벨의 노드들은 왼쪽에서 오른쪽으로 순서대로 채워진 트리입니다.

3. 편향 이진 트리 (Skewed Binary Tree)

모든 노드가 한쪽 방향으로만 연결된 트리로, 선형 구조와 비슷합니다.

---

 

3. 이진 트리 구현 예제 코드

C 언어

#include <stdio.h>
#include <stdlib.h>

struct Node {
    int data;
    struct Node *left, *right;
};

struct Node* createNode(int data) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = data;
    newNode->left = newNode->right = NULL;
    return newNode;
}

void inorderTraversal(struct Node* root) {
    if (root == NULL) return;
    inorderTraversal(root->left);
    printf("%d ", root->data);
    inorderTraversal(root->right);
}

int main() {
    struct Node* root = createNode(1);
    root->left = createNode(2);
    root->right = createNode(3);
    root->left->left = createNode(4);
    root->left->right = createNode(5);

    printf("Inorder Traversal: ");
    inorderTraversal(root);
    return 0;
}

---

 

Java

class Node {
    int data;
    Node left, right;

    public Node(int data) {
        this.data = data;
        left = right = null;
    }
}

public class BinaryTree {
    Node root;

    void inorderTraversal(Node node) {
        if (node == null) return;
        inorderTraversal(node.left);
        System.out.print(node.data + " ");
        inorderTraversal(node.right);
    }

    public static void main(String[] args) {
        BinaryTree tree = new BinaryTree();
        tree.root = new Node(1);
        tree.root.left = new Node(2);
        tree.root.right = new Node(3);
        tree.root.left.left = new Node(4);
        tree.root.left.right = new Node(5);

        System.out.print("Inorder Traversal: ");
        tree.inorderTraversal(tree.root);
    }
}

---

 

Python

class Node:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None

def inorder_traversal(root):
    if root is None:
        return
    inorder_traversal(root.left)
    print(root.data, end=" ")
    inorder_traversal(root.right)

# Tree creation
root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)

print("Inorder Traversal:", end=" ")
inorder_traversal(root)

---

 

4. 이진 트리의 장단점

장점

1. 효율적인 데이터 검색: 트리 높이에 비례한 시간 복잡도(O(log n))를 제공.
2. 유연한 데이터 관리: 삽입, 삭제, 탐색 연산이 용이.
3. 다양한 확장성: AVL 트리, 힙 등으로 확장 가능.

단점

1. 불균형 문제: 편향 트리는 선형 구조(O(n))로 성능 저하 발생. -> 편향되지 않도록 구현하는게 포인트!
2. 메모리 사용량 증가: 각 노드가 포인터를 가지므로 추가 메모리 소모.

---

 

5. 이진 트리의 사용 사례

1. 이진 탐색 트리: 검색 알고리즘에서 사용.
2. 힙(Heap): 우선순위 큐 구현.
3. 파싱(Tree Parsing): 컴파일러와 언어 처리기에서 사용.
4. 파일 시스템: 디렉토리 구조 관리.
5. 네트워크 라우팅: 패킷 전달 최적화.

---

 

2024.12.18 - [자료구조] - 트리(2) - 이진 탐색 트리(Binary Search Tree)의 원리, 구조, 예제 코드(C언어, Java, Python), 장단점, 사용 사례 총정리

트리(2) - 이진 탐색 트리(Binary Search Tree)의 원리, 구조, 예제 코드(C언어, Java, Python), 장단점, 사용

 

2024.12.18 - [자료구조] - 트리(3) - 문자열 검색 문제에 최적화된 트라이(Trie) 자료구조(C언어, Java, Python 예시코드 포함)

트리(3) - 문자열 검색 문제에 최적화된 트라이(Trie) 자료구조(C언어, Java, Python 예시코드 포함)