트리 구조

기술노트
Admin (토론 | 기여)님의 2025년 4월 17일 (목) 15:06 판 (컴퓨터 과학 용어 정리 - 트리 구조 추가)
(차이) ← 이전 판 | 최신판 (차이) | 다음 판 → (차이)

트리 구조

트리의 기본 개념

트리(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"