트리 정렬(Tree Sort)

 

 

1. 트리 정렬이란?

트리 정렬(Tree Sort)은 이진 탐색 트리(Binary Search Tree, BST)를 기반으로 한 정렬 알고리즘입니다. 데이터를 BST에 삽입한 후, 중위 순회(Inorder Traversal)를 수행하여 정렬된 데이터를 얻는 방식으로 동작합니다.

이 정렬 방식은 평균적으로 O(n log n)의 시간 복잡도를 가지며, 안정적인 정렬을 보장합니다.

2. 트리 정렬 동작 원리

트리 정렬은 다음과 같은 방식으로 동작합니다:

1. 데이터를 하나씩 이진 탐색 트리에 삽입합니다.
2. 중위 순회(Inorder Traversal)를 수행하여 정렬된 데이터를 출력합니다.

예제: 트리 정렬 과정 (오름차순 정렬)

다음과 같은 배열이 있다고 가정하겠습니다.

[5, 3, 8, 4, 2]

트리 정렬이 진행되는 과정은 다음과 같습니다.

1. BST에 데이터를 삽입

    5
   / \
  3   8
 / \
2   4

1. 중위 순회(Inorder Traversal) 수행 → [2, 3, 4, 5, 8]

3. 트리 정렬 구현

class TreeNode {
    int val;
    TreeNode left, right;
    
    public TreeNode(int val) {
        this.val = val;
        left = right = null;
    }
}

class TreeSort {
    private TreeNode root;
    
    public void insert(int val) {
        root = insertRec(root, val);
    }
    
    private TreeNode insertRec(TreeNode root, int val) {
        if (root == null) {
            return new TreeNode(val);
        }
        if (val < root.val) {
            root.left = insertRec(root.left, val);
        } else {
            root.right = insertRec(root.right, val);
        }
        return root;
    }
    
    public void inorderTraversal(TreeNode root) {
        if (root != null) {
            inorderTraversal(root.left);
            System.out.print(root.val + " ");
            inorderTraversal(root.right);
        }
    }
    
    public void treeSort(int[] arr) {
        for (int num : arr) {
            insert(num);
        }
        inorderTraversal(root);
    }
    
    public static void main(String[] args) {
        int[] arr = {5, 3, 8, 4, 2};
        TreeSort treeSort = new TreeSort();
        treeSort.treeSort(arr);
        // 출력: 2 3 4 5 8
    }
}

4. 트리 정렬의 시간 복잡도

경우	시간 복잡도
최선의 경우	O(n log n)
평균의 경우	O(n log n)
최악의 경우	O(n²) (편향 트리 발생 시)

• 균형이 잡힌 BST에서는 O(n log n)의 성능을 보장합니다.
• **편향된 트리(Skewed Tree)**가 발생하면 O(n²)까지 성능이 저하될 수 있습니다.

5. 트리 정렬의 장점과 단점

✅ 장점

• 안정적인 정렬 (Stable Sort)
• 추가적인 메모리가 필요 없음 (In-place 정렬 가능)
• 트리를 활용하여 검색, 삽입, 삭제 연산도 가능

❌ 단점

• BST가 균형을 이루지 않으면 성능 저하(O(n²))
• 추가적인 트리 구조가 필요하여 구현이 복잡

6. 트리 정렬이 적합한 경우

• 데이터의 중복이 적고, 무작위로 분포된 경우
• 정렬과 동시에 데이터 검색이 필요한 경우
• 삽입과 삭제가 빈번하게 발생하는 경우

 

 

 

트리 정렬은 이진 탐색 트리를 활용하여 데이터를 정렬하는 방식으로, 검색과 정렬을 동시에 수행할 수 있는 강력한 알고리즘입니다. 하지만 트리가 균형을 이루지 못하면 성능이 저하될 수 있으므로, AVL 트리나 Red-Black 트리와 같은 균형 잡힌 트리와 함께 사용하는 것이 일반적입니다.