자료구조 Tree(트리) 란?

트리(Tree)란?

트리는 노드(Node) 들로 구성된 자료구조로, 다음 조건을 만족합니다.

• 하나의 루트(Root) 노드에서 시작
• 각 노드는 0개 이상의 자식 노드를 가짐
• 사이클이 없음 (비순환 그래프)
• 계층적 구조

트리는 사실상 그래프의 일종이지만, 사이클이 없고 부모-자식 관계가 명확한 구조라는 점이 특징입니다.

EX)

• 디렉터리 구조
• 데이터베이스 인덱스 (B-Tree 등)
• HTML DOM 트리
• 컴파일러의 구문 트리 (Parse Tree)
• AI 탐색 알고리즘 (Game Tree 등)

---

트리 용어

용어	설명
노드(Node)	데이터 단위
루트(Root)	최상위 노드
리프(Leaf)	자식이 없는 노드
부모/자식 노드	계층적 관계를 의미
서브트리	특정 노드를 루트로 하는 부분 트리
깊이(Depth)	루트에서 특정 노드까지의 거리
높이(Height)	리프에서 루트까지 가장 긴 거리

---

트리의 종류

1) 이진 트리 (Binary Tree)

• 모든 노드가 최대 2개의 자식을 가짐
• 가장 기본적인 트리 구조

2) 이진 탐색 트리 (Binary Search Tree, BST)

• 왼쪽 서브트리 < 부모 < 오른쪽 서브트리
• 정렬된 데이터를 효율적으로 탐색할 수 있음

3) 힙 트리 (Heap)

• 최소 힙 / 최대 힙 형태
• 우선순위 큐 등에서 사용됨 (별도 포스팅 참고)

4) 균형 이진 트리 (AVL, Red-Black Tree 등)

• 트리의 높이를 최소화해 탐색 성능을 높임

5) B-Tree / B+ Tree

• 데이터베이스 인덱싱에 활용
• 디스크 접근 효율성 고려

6) 트라이(Trie)

• 문자열 검색에 최적화된 트리
• 자동완성, 사전 등에서 사용

---

이진 탐색 트리(Java)

class Node {
    int data;
    Node left, right;

    Node(int data) {
        this.data = data;
    }
}

public class BinarySearchTree {
    Node root;

    void insert(int value) {
        root = insertRec(root, value);
    }

    Node insertRec(Node root, int value) {
        if (root == null) return new Node(value);
        if (value < root.data) root.left = insertRec(root.left, value);
        else root.right = insertRec(root.right, value);
        return root;
    }

    void inorder(Node root) {
        if (root != null) {
            inorder(root.left);
            System.out.print(root.data + " ");
            inorder(root.right);
        }
    }

    public static void main(String[] args) {
        BinarySearchTree tree = new BinarySearchTree();
        tree.insert(50);
        tree.insert(30);
        tree.insert(70);
        tree.insert(20);
        tree.insert(40);
        tree.insert(60);
        tree.insert(80);

        tree.inorder(tree.root); // 20 30 40 50 60 70 80
    }
}

 

트리 순회(Tree Traversal)

트리 구조를 탐색하는 방식에는 여러 가지가 있습니다.

1) 깊이 우선 탐색 (DFS)

• 전위 순회 (Preorder): 부모 → 왼쪽 → 오른쪽
• 중위 순회 (Inorder): 왼쪽 → 부모 → 오른쪽
• 후위 순회 (Postorder): 왼쪽 → 오른쪽 → 부모

2) 너비 우선 탐색 (BFS)

• 레벨 순서대로 탐색 (Queue 사용)

---

실무 활용 예시

1) 폴더 구조

운영체제나 파일 탐색기에서 사용하는 디렉터리 구조는 트리 구조입니다. 하위 폴더가 자식 노드로 구성됩니다.

2) HTML DOM

브라우저가 HTML을 렌더링할 때 트리 형태로 파싱하여 DOM 트리를 생성합니다. 자바스크립트에서 DOM 탐색 시 DFS/BFS가 사용됩니다.

3) 데이터베이스 인덱스

B-Tree나 B+ Tree 구조는 RDBMS의 인덱싱 성능을 극대화하는 핵심 요소입니다.

---

시간복잡도

연산	평균 시간복잡도	최악 시간복잡도
탐색	O(log n)	O(n)
삽입	O(log n)	O(n)
삭제	O(log n)	O(n)

이진 탐색 트리의 경우 균형이 맞지 않으면 선형 탐색 수준으로 성능이 저하될 수 있으므로, 실무에서는 AVL Tree나 Red-Black Tree 같은 균형 트리가 주로 사용됩니다.