트리(Tree) — 자료구조와 개념

1. 트리 개념

트리는 계층적(hierarchical) 구조를 가진 비선형 자료구조입니다. 노드(Node)들이 부모-자식 관계로 연결되어 있습니다.

• 최상위 노드를 **루트(root)**라고 합니다.
• 각 노드는 0개 이상의 자식 노드를 가질 수 있습니다.
• 노드 간에는 유일한 경로가 존재합니다.

2. 용어

• 루트(root): 트리의 최상위 노드
• 부모(Parent): 바로 위에 연결된 노드
• 자식(Child): 바로 아래 연결된 노드
• 형제(Sibling): 같은 부모를 가진 노드
• 단말 노드(Leaf): 자식이 없는 노드
• 간선(Edge): 노드를 연결하는 선
• 높이(Height): 루트에서 가장 먼 단말 노드까지의 거리
• 깊이(Depth): 루트에서 특정 노드까지의 거리

3. 종류

• 이진 트리(Binary Tree): 각 노드가 최대 두 자식을 가짐
• 이진 탐색 트리(Binary Search Tree, BST): 왼쪽 자식은 부모보다 작고, 오른쪽 자식은 부모보다 큰 값을 가짐
• 균형 트리(AVL, Red-Black Tree 등): 트리의 높이를 균형 있게 유지하여 탐색 효율 개선
• 힙(Heap): 부모가 자식보다 크거나 작은 완전 이진 트리
• 트라이(Trie): 문자열 저장에 특화된 트리 구조

4. 활용 사례

• 계층적 데이터 표현 (파일 시스템, 조직도)
• 탐색 및 정렬 (BST)
• 우선순위 큐 (힙)
• 자동 완성, 검색어 추천 (트라이)

5. 기본 연산

• 탐색, 삽입, 삭제
• 순회(Traversal): 전위(preorder), 중위(inorder), 후위(postorder), 레벨 순서(level-order)

6. 간단한 이진 트리 노드 구조 (Swift)

class TreeNode<T> {
    var value: T
    var left: TreeNode?
    var right: TreeNode?
    
    init(_ value: T) {
        self.value = value
    }
}

7. 마무리

트리는 계층적 관계를 표현하는 데 적합하며, 다양한 변형을 통해 여러 문제를 효율적으로 해결합니다. 자료구조 중 중요도가 높아 알고리즘 공부에 필수적입니다.