[자료구조] 트리의 특성과 종류, 구현

그래프

• 그래프는 정점(Vertex)과 간선(Edge)으로 이루어진 자료구조
• 여러 요소(정점) 간의 관계를 나타내기 위해 사용
• 구성요소로는 정점, 간선, 가중치가 있음.

분류

• 방향 그래프(Directed Graph): 간선에 방향이 있습니다. (A,B)는 A→B를 의미하며, B→A는 별개의 간선으로 취급됩니다.
• 무방향 그래프(Undirected Graph): 간선에 방향이 없으며 (A,B)와 (B,A)가 동일합니다.
• 가중치 그래프(Weighted Graph): 간선에 가중치가 포함된 그래프입니다.
• 비가중치 그래프(Unweighted Graph): 간선에 가중치가 없는 그래프입니다.

---

트리

• 계층적 구조를 표현하는 특수한 형태의 그래프
• 무방향이면서 사이클이 없는 연결 그래프
• 임의의 두 정점을 연결하는 Simple Path가 유일한 그래프
  • 서로다른 정점 사이 간선은 무조건 한개
• V개의 정점을 가지고, V-1개의 간선을 가짐.
• 루트 노드는 부모가 없는 유일한 노드
• 트리의 간선은 위에서 아래(부모 → 자식)로 연결

---

트리의 종류

일반 트리

• 기본적인 트리 구조로, 각 노드는 제한 없이 여러 개의 자식을 가질 수 있음.

이진 트리

• 각 노드가 최대 두 개의 자식 노드를 가질 수 있는 트리

트라이

• 문자열 탐색에 특화된 트리
• 문자열의 각 문자가 트리의 노드로 표현됨.

세그먼트 트리

• 구간 쿼리(Query)와 업데이트를 효율적으로 처리하기 위한 트리
• 특정 구간의 합, 최소값, 최대값 등을 빠르게 계산. O(logN)
• 범위 합 구하기, 구간 최소값/최대값 구하기

---

이진 트리에서 파생되는 트리

• 각 노드가 최대 두 개의 자식 노드를 가질 수 있는 트리
• 정렬과 검색 알고리즘을 위한 자료구조

포화 이진 트리

• 모든 노드가 0개 또는 2개의 자식을 가지는 이진 트리
• 모든 레벨이 꽉 찬 상태

완전 이진 트리

• 트리의 모든 레벨이 완전히 채워져 있으며, 마지막 레벨의 노드는 왼쪽에서부터 순서대로 채워져 있음.
• 힙(heap) 구현에 주로 사용

균형 이진 트리

• 트리의 높이가 가능한 균형을 이루는 이진 트리
• 왼쪽과 오른쪽 서브트리의 높이 차이가 1 이하
• 높이가 낮으므로 탐색, 삽입, 삭제가 효율적
• AVL, 레드-블랙 트리 구현에 사용

이진 탐색 트리

• 데이터를 정렬된 형태로 저장하여 효율적인 검색을 보장하는 이진 트리
  • 왼쪽 서브트리의 모든 값은 루트보다 작음.
  • 오른쪽 서브트리의 모든 값은 루트보다 큼.
• 평균 탐색 시간 복잡도 : O(logN)
• 최악의 경우(편향 트리) : O(N)
• 효율적인 탐색, 삽입, 삭제

힙(Heap)

• 완전 이진 트리를 기반으로 하는 트리 자료구조로 아래 조건을 만족하는 트리
  • 최소 힙(Min-Heap): 부모 노드의 값이 자식 노드보다 작거나 같음.
  • 최대 힙(Max-Heap): 부모 노드의 값이 자식 노드보다 크거나 같음.
• 우선순위 큐 구현에 사용
• 시간 복잡도: 삽입, 삭제 O(logN)

 

요약

종류	특징	활용
완전 이진 트리	마지막 레벨을 제외하고 모든 노드가 채워진 상태	힙 자료구조
포화 이진 트리	모든 레벨이 완전히 채워짐	학습 자료 등 간단한 구조 모델링
균형 이진 트리	서브트리 간의 높이 차이가 1 이하로 유지됨	검색 및 수정이 중요한 경우
이진 탐색 트리	왼쪽은 작고, 오른쪽은 큰 데이터 구조	검색, 정렬
힙	우선순위 기반으로 정렬된 완전 이진 트리	우선순위 큐, 힙 정렬
AVL 트리	항상 균형을 유지하는 이진 탐색 트리	메모리 관리, 고성능 검색
레드-블랙 트리	삽입/삭제를 빠르게 처리하며 균형 유지	STL(Map, Set), 데이터베이스
트라이	문자열을 노드로 표현하는 트리	검색 추천, 사전 구현

---

트리의 구현

트리도 일반적으로 그래프에서 파생되는 자료구조.

• 인접 리스트
• 인접 행렬

두 가지로 구현 가능.

이진 트리의 경우 왼쪽, 오른쪽 자식을 구분하기 위해 사용자 정의 객체를 만들어서 구현.

 

인접행렬로 구현

• 트리를 그래프처럼 2차원 배열로 표현
• adj[i][j] : i번 노드와 j번 노드가 연결되어있는지 여부를 저장.
• 인접행렬의 경우 두 가지의 정보를 모른다.
  • 부모-자식 관계
  • 자식 노드의 왼쪽, 오른쪽 여부

인접리스트로 구현

• 각 노드에 연결된 자식 노드들을 리스트로 관리.
• List<List<Integer>> list 형태에서 list.get(”부모”).add(”자식”) 형태로 각 정점의 자식 정점을 확인
• List<List<Integer>> list 형태에서 list.get(”자식”).add(”부모”) 형태로 각 정점의 부모 정점을 확인
• 트리 특성 상 각 정점의 부모는 한개라서 각 정점의 부모 정점이 누구인지 알아야하는 문제의 경우 Map을 활용할 수 있음.

해시맵을 이용한 구현

• 각 노드의 키-값 쌍을 부모-자식 쌍으로 표현.
• 아래는 부모 정점에 대해 자식 정보를 저장

Map<Integer, List<Integer>> tree = new HashMap<>();
tree.put(0, Arrays.asList(1, 2)); // 0번 노드의 자식: 1, 2
tree.put(1, Arrays.asList(3, 4)); // 1번 노드의 자식: 3, 4

• 아래는 자식 정점에 대해 부모 정보를 저장

Map<Integer, Integer> tree = new HashMap<>();
tree.put(0, 1); // 0번 노드의 부모는 1번
tree.put(1, 2); // 1번 노드의 부모는 2번

노드 클래스 참조 방식

• 왼쪽 자식과 오른쪽 자식을 클래스 참조를 통해서 구현

// 노드 클래스 정의
class TreeNode {
    int value;           // 노드의 값
    TreeNode left;       // 왼쪽 자식 노드
    TreeNode right;      // 오른쪽 자식 노드

    // 생성자
    TreeNode(int value) {
        this.value = value;
        this.left = null;
        this.right = null;
    }
}

// 이진 트리 클래스 정의
class BinaryTree {
    TreeNode root;       // 트리의 루트 노드

    // 생성자
    BinaryTree(int rootValue) {
        this.root = new TreeNode(rootValue);
    }

    // 트리에 노드 추가 (예시: 간단한 이진 트리 생성)
    public void addNode(TreeNode parent, int value, boolean isLeft) {
        if (isLeft) {
            parent.left = new TreeNode(value);
        } else {
            parent.right = new TreeNode(value);
        }
    }
}

// 실행 클래스
public class BinaryTreeDemo {
    public static void main(String[] args) {
        // 트리 생성
        BinaryTree tree = new BinaryTree(1); // 루트 노드 값: 1

        // 노드 추가
        tree.addNode(tree.root, 2, true);  // 루트의 왼쪽 자식: 2
        tree.addNode(tree.root, 3, false); // 루트의 오른쪽 자식: 3
        tree.addNode(tree.root.left, 4, true);  // 2의 왼쪽 자식: 4
        tree.addNode(tree.root.left, 5, false); // 2의 오른쪽 자식: 5

    }
}

 

 

 

트리 구현 방식의 선택 기준

이외에도 트리를 구현하기 위한 다양한 방법이 있음.

트리의 성질과 문제 요구 사항에 따라 적합한 구현 방식을 선택하면 됨.

방법	장점	단점	적합한 경우
인접 행렬	연결 여부 확인이 빠름 (O(1)O(1)O(1))	공간 낭비 심함 (O(N2)O(N^2)O(N2))	간선 정보가 빈번히 필요할 때
인접 리스트	간선 저장 공간 절약 (O(E)O(E)O(E))	연결 여부 확인이 느림 (O(degree)O(\text{degree})O(degree))	희소한 트리에서 간선 정보가 적은 경우
노드 클래스 참조	계층 구조 표현 용이	그래프와 같은 복잡 구조 표현 어려움	구조적 트리 (이진 트리, N-진 트리 등)
배열	구현 간단, 완전 이진 트리에 적합	비완전 트리에서 공간 낭비	완전 이진 트리, 힙 등
부모 배열	부모 정보 확인 빠름 (O(1)O(1)O(1))	자식 정보 확인 추가 연산 필요	부모 관계만 필요한 경우
자식 배열	자식 정보 확인 빠름 (O(1)O(1)O(1))	부모 정보 확인 추가 연산 필요	자식 관계만 중요한 경우
해시맵	유연한 구조 표현 가능	관리 복잡성 증가	동적 트리 표현

 

---

정리

• 트리는 무방향 그래프이면서 사이클이 존재하지 않는다.
• 일반적인 그래프와 다른 점은 부모-자식 관계가 존재하며, 이진 트리의 경우 왼쪽, 자식 노드 구분이 필요할 수 있음.
• 이를 구현하기 위한 방법으로는 다양하며, 요구사항 별로 효율성을 고려하여 방법을 선택하면 된다.
  • 예로 각 정점의 부모노드의 정보만 필요할 경우 Map 혹은 List를 통해서 정보를 저장하고, 효율적으로 부모노드로 탐색이 가능하다.