트리 구조

기술노트

트리 구조

트리의 기본 개념

트리(Tree)는 계층적 구조를 표현하는 비선형 자료구조로, 노드(Node)와 간선(Edge)으로 구성됩니다. 트리는 사이클이 없는 연결 그래프의 일종으로, 루트 노드에서 시작하여 자식 노드로 확장되는 구조를 가집니다.

트리의 주요 용어

  • 노드(Node): 트리의 기본 요소, 데이터와 자식 노드에 대한 참조를 포함
  • 루트 노드(Root Node): 트리의 최상위 노드
  • 부모 노드(Parent Node): 직접 연결된 하위 노드를 가진 노드
  • 자식 노드(Child Node): 부모 노드와 연결된 하위 노드
  • 리프 노드(Leaf Node): 자식이 없는 노드
  • 형제 노드(Sibling Node): 같은 부모를 가진 노드들
  • 깊이(Depth): 루트에서 특정 노드까지의 경로 길이
  • 높이(Height): 가장 깊은 리프 노드까지의 경로 길이
  • 서브트리(Subtree): 트리 내의 한 노드와 그 자손들로 구성된 트리

트리의 종류

이진 트리(Binary Tree)

이진 트리는 각 노드가 최대 2개의 자식 노드를 가질 수 있는 트리입니다.

특별한 이진 트리 유형
  • 완전 이진 트리(Complete Binary Tree): 마지막 레벨을 제외한 모든 레벨이 완전히 채워져 있고, 마지막 레벨은 왼쪽부터 순차적으로 채워진 트리
  • 포화 이진 트리(Full Binary Tree): 모든 노드가 0개 또는 2개의 자식을 가지는 트리
  • 완전 포화 이진 트리(Perfect Binary Tree): 모든 내부 노드가 2개의 자식을 가지고, 모든 리프 노드가 같은 레벨에 있는 트리
  • 균형 이진 트리(Balanced Binary Tree): 왼쪽과 오른쪽 서브트리의 높이 차이가 1 이하인 트리
// 이진 트리 노드 클래스
class TreeNode {
    int data;
    TreeNode left;
    TreeNode right;
    
    public TreeNode(int data) {
        this.data = data;
        this.left = null;
        this.right = null;
    }
}

// 이진 트리 클래스
class BinaryTree {
    TreeNode root;
    
    // 트리 생성 예시
    public void createBinaryTree() {
        root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        root.left.left = new TreeNode(4);
        root.left.right = new TreeNode(5);
    }
    
    // 중위 순회 (Inorder Traversal)
    public void inorderTraversal(TreeNode node) {
        if (node == null) return;
        
        inorderTraversal(node.left);
        System.out.print(node.data + " ");
        inorderTraversal(node.right);
    }
}

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

이진 탐색 트리는 왼쪽 자식 노드의 값이 부모 노드보다 작고, 오른쪽 자식 노드의 값이 부모 노드보다 큰 속성을 가진 이진 트리입니다.

특징
  • 중위 순회 시 정렬된 순서로 값을 얻을 수 있음
  • 평균적인 탐색, 삽입, 삭제의 시간 복잡도: O(log n)
  • 최악의 경우(불균형 트리): O(n)
// 이진 탐색 트리 클래스
class BinarySearchTree {
    TreeNode root;
    
    // 노드 삽입
    public void insert(int key) {
        root = insertRec(root, key);
    }
    
    private TreeNode insertRec(TreeNode root, int key) {
        if (root == null) {
            root = new TreeNode(key);
            return root;
        }
        
        if (key < root.data)
            root.left = insertRec(root.left, key);
        else if (key > root.data)
            root.right = insertRec(root.right, key);
            
        return root;
    }
    
    // 노드 검색
    public boolean search(int key) {
        return searchRec(root, key);
    }
    
    private boolean searchRec(TreeNode root, int key) {
        if (root == null)
            return false;
            
        if (root.data == key)
            return true;
            
        if (key < root.data)
            return searchRec(root.left, key);
        else
            return searchRec(root.right, key);
    }
}

균형 트리(Balanced Tree)

균형 트리는 트리의 높이를 최소화하여 연산의 시간 복잡도를 개선한 트리입니다.

주요 균형 트리 유형
  1. AVL 트리:
    • 모든 노드에서 왼쪽과 오른쪽 서브트리의 높이 차이가 최대 1
    • 삽입/삭제 후 회전을 통해 균형 유지
    • 검색, 삽입, 삭제 모두 O(log n) 보장
  1. 레드-블랙 트리:
    • 각 노드는 레드 또는 블랙 색상을 가짐
    • 루트와 모든 리프 노드(NIL)는 블랙
    • 레드 노드의 자식은 항상 블랙
    • 루트에서 모든 리프까지의 블랙 노드 수는 동일
    • 실제 많은 라이브러리와 시스템에서 사용됨
  1. B-트리:
    • 다분기 트리로, 각 노드가 여러 개의 키와 자식을 가짐
    • 디스크 접근을 최소화하도록 설계됨
    • 데이터베이스와 파일 시스템에서 널리 사용

힙(Heap)

힙은 완전 이진 트리 기반의 자료구조로, 최대 힙(Max Heap)과 최소 힙(Min Heap)이 있습니다.

특징
  • 최대 힙: 부모 노드의 값이 자식 노드보다 크거나 같음
  • 최소 힙: 부모 노드의 값이 자식 노드보다 작거나 같음
  • 우선순위 큐 구현에 사용
  • 삽입, 삭제 연산의 시간 복잡도: O(log n)
  • 최대/최소값 접근: O(1)
// 최소 힙 예시 (Java의 PriorityQueue 사용)
import java.util.PriorityQueue;

public class HeapExample {
    public static void main(String[] args) {
        // 최소 힙 생성
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();
        
        // 요소 추가
        minHeap.add(5);
        minHeap.add(2);
        minHeap.add(8);
        minHeap.add(1);
        
        // 최솟값 확인 (제거하지 않음)
        System.out.println("최솟값: " + minHeap.peek()); // 1
        
        // 요소 추출 (최솟값부터 순서대로)
        while (!minHeap.isEmpty()) {
            System.out.print(minHeap.poll() + " "); // 1 2 5 8
        }
    }
}

트리 순회 방법

트리 순회는 트리의 모든 노드를 방문하는 과정입니다. 이진 트리에서 주로 사용되는 순회 방법은 다음과 같습니다:

  1. 전위 순회(Preorder Traversal):
    • 루트 → 왼쪽 서브트리 → 오른쪽 서브트리
    • 구현: 현재 노드 방문 → 왼쪽 서브트리 순회 → 오른쪽 서브트리 순회
  1. 중위 순회(Inorder Traversal):
    • 왼쪽 서브트리 → 루트 → 오른쪽 서브트리
    • 구현: 왼쪽 서브트리 순회 → 현재 노드 방문 → 오른쪽 서브트리 순회
    • 이진 탐색 트리에서는 정렬된 결과 제공
  1. 후위 순회(Postorder Traversal):
    • 왼쪽 서브트리 → 오른쪽 서브트리 → 루트
    • 구현: 왼쪽 서브트리 순회 → 오른쪽 서브트리 순회 → 현재 노드 방문
  1. 레벨 순회(Level Order Traversal):
    • 트리의 각 레벨을 왼쪽에서 오른쪽으로 순회
    • 구현: 큐를 사용하여 BFS(너비 우선 탐색) 방식으로 순회
// 트리 순회 메서드 구현
class TreeTraversal {
    // 전위 순회
    public void preorder(TreeNode node) {
        if (node == null) return;
        
        System.out.print(node.data + " ");
        preorder(node.left);
        preorder(node.right);
    }
    
    // 중위 순회
    public void inorder(TreeNode node) {
        if (node == null) return;
        
        inorder(node.left);
        System.out.print(node.data + " ");
        inorder(node.right);
    }
    
    // 후위 순회
    public void postorder(TreeNode node) {
        if (node == null) return;
        
        postorder(node.left);
        postorder(node.right);
        System.out.print(node.data + " ");
    }
    
    // 레벨 순회
    public void levelOrder(TreeNode root) {
        if (root == null) return;
        
        java.util.Queue<TreeNode> queue = new java.util.LinkedList<>();
        queue.add(root);
        
        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();
            System.out.print(node.data + " ");
            
            if (node.left != null)
                queue.add(node.left);
            
            if (node.right != null)
                queue.add(node.right);
        }
    }
}

트리의 응용

1. 계층 구조 표현

  • 파일 시스템의 디렉토리 구조
  • 조직도
  • XML/HTML DOM

2. 검색 구조

  • 이진 탐색 트리로 효율적인 검색 구현
  • 데이터베이스 인덱싱
  • 트라이(Trie)를 이용한 문자열 검색

3. 정렬

  • 힙 정렬

4. 의사 결정

  • 결정 트리
  • 게임 트리 (미니맥스 알고리즘)

5. 통신 네트워크

  • 최소 신장 트리 (MST)

시간 복잡도 비교

연산 균형 이진 탐색 트리 불균형 이진 탐색 트리 힙
검색 O(log n) O(n) O(n)
삽입 O(log n) O(n) O(log n)
삭제 O(log n) O(n) O(log n)
최소값/최대값 접근 O(log n) O(n) O(1)

관련 항목

원본 주소 "https://technote.wiki/index.php?title=트리_구조&oldid=523"