Tree 에 관하여

Java에서 Tree 자료구조는 계층적인 데이터 구조를 표현하는 데 사용되며, 다양한 알고리즘과 데이터 구조에서 활용됩니다. 대표적인 트리 구현체로는 TreeSet, TreeMap, BinarySearchTree, AVLTree, Red-Black Tree 등이 있습니다. 이 글에서는 트리의 개념과 주요 구현체들의 특징을 비교하고 적절한 사용 사례를 살펴보겠습니다.

---

1. 트리(Tree)란?

Tree는 노드(Node)와 간선(Edge)으로 구성된 비선형 자료구조입니다. 일반적으로 다음과 같은 특징을 가집니다:

• 계층 구조를 형성 (부모-자식 관계)
• 루트(Root) 노드에서 시작하여 여러 개의 하위 노드로 확장
• 순환(Cycle)이 없는 그래프 구조
• 이진 트리(Binary Tree), 균형 트리(Balanced Tree) 등 다양한 변형 존재

Java에서 트리를 구현하는 대표적인 방법은 TreeSet, TreeMap, 그리고 사용자 정의 이진 탐색 트리(Binary Search Tree) 등이 있습니다.

---

2. 주요 Tree 구현체 비교

2.1 TreeSet

TreeSet은 이진 검색 트리(Red-Black Tree) 기반의 Set 구현체입니다.

특징:

• 중복을 허용하지 않음
• 자동 정렬 유지 (기본적으로 오름차순 정렬, Comparator 사용 가능)
• 검색 성능 우수 (O(log n))
• 삽입 및 삭제 성능 (O(log n))

사용 예제:

import java.util.*;
public class TreeSetExample {
    public static void main(String[] args) {
        Set<Integer> set = new TreeSet<>();
        set.add(30);
        set.add(10);
        set.add(20);
        System.out.println(set); // 출력: [10, 20, 30] (오름차순 정렬 유지)
    }
}

사용 사례:

• 자동 정렬이 필요한 경우
• 중복 제거가 필요하면서 정렬 유지가 필요한 경우

---

 

2.2 TreeMap

TreeMap은 Red-Black Tree 기반의 Map 구현체로, 키를 자동 정렬된 상태로 저장합니다.

특징:

• 키-값 쌍 저장
• 키의 정렬 유지 (Comparable 또는 Comparator 지원)
• 검색 성능 우수 (O(log n))
• 삽입 및 삭제 성능 (O(log n))

사용 예제:

import java.util.*;
public class TreeMapExample {
    public static void main(String[] args) {
        Map<Integer, String> map = new TreeMap<>();
        map.put(30, "Thirty");
        map.put(10, "Ten");
        map.put(20, "Twenty");
        System.out.println(map); // 출력: {10=Ten, 20=Twenty, 30=Thirty} (오름차순 정렬 유지)
    }
}

사용 사례:

• 자동 정렬이 필요한 경우
• 범위 검색이 중요한 경우

---

 

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

BinarySearchTree는 각 노드가 최대 두 개의 자식을 가지는 이진 트리이며, 왼쪽 자식 노드는 부모보다 작고, 오른쪽 자식 노드는 부모보다 큽니다.

특징:

• 정렬된 데이터를 저장할 수 있음
• 검색, 삽입, 삭제 성능 O(log n) (균형을 유지하는 경우)
• 불균형(Balanced) 여부에 따라 성능 저하 가능성 있음

사용 예제:

class Node {
    int key;
    Node left, right;

    public Node(int item) {
        key = item;
        left = right = null;
    }
}

class BinarySearchTree {
    Node root;
    BinarySearchTree() { root = null; }

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

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

사용 사례:

• 검색이 빈번한 경우
• 이진 탐색 알고리즘을 활용해야 하는 경우

---

 

5. 마무리

• Tree는 데이터를 계층적으로 저장하는 강력한 자료구조입니다.
• TreeSet, TreeMap은 Red-Black Tree 기반의 구현체로 자동 정렬 기능을 제공합니다.
• BinarySearchTree는 사용자가 직접 구현하여 특수한 트리 구조를 만들 수 있음.
• 트리 구조를 적절히 활용하면 데이터 검색과 정렬 성능을 최적화할 수 있습니다.