[4] Tree의 개념 및 Tree의 종류별 연산 시간

Tree Data Structure

1. 개념

Tree는 순환하지 않고 연결된 그래프로, 임의의 두 노드 사이에 하나의 경로만 존재하는 계층적 자료구조입니다.

2. 특징

• 루트 노드: 트리의 시작점이 되는 최상위 노드
• 부모-자식 관계: 두 노드가 간선으로 연결되었을 때, 위쪽이 부모, 아래쪽이 자식
• 단순 경로: 두 노드간 경로가 오직 하나만 존재
• 사이클 없음: 순환하지 않는 그래프
• 노드의 개수 = 간선의 개수 + 1

3. 트리의 종류

3.1 이진 트리 (Binary Tree)

각 노드가 최대 2개의 자식을 가지는 트리

종류:

• 완전 이진 트리: 마지막 레벨을 제외하고 모든 레벨이 채워져 있는 트리
• 포화 이진 트리: 모든 내부 노드가 2개의 자식 노드를 가지는 트리 (리프노드 제외)
• 편향 트리: 한쪽으로만 자식을 가지는 트리
• 균형 트리: 모든 노드의 왼쪽 서브트리와 오른쪽 서브트리의 높이 차이가 1 이하인 트리

3.2 이진 탐색 트리 (BST)

• 왼쪽 서브트리의 모든 값 < 현재 노드 < 오른쪽 서브트리의 모든 값
• 중위 순회 시 정렬된 결과
• 균형이 무너지면 성능 저하 발생

3.3 힙 (Heap)

• 완전 이진트리 구조
• 최대 힙 또는 최소 힙
• 우선순위 큐 구현에 사용

4. 시간복잡도

Binary Search Tree (BST)

연산	평균	최악
조회	O(log n)	O(n)
삽입	O(log n)	O(n)
삭제	O(log n)	O(n)

Heap

연산	평균	최악
조회	O(n)	O(n)
삽입	O(log n)	O(log n)
삭제	O(log n)	O(log n)
최대/최소 조회	O(1)	O(1)

AVL Tree

연산	평균	최악
조회	O(log n)	O(log n)
삽입	O(log n)	O(log n)
삭제	O(log n)	O(log n)

5. DFS를 활용한 트리 탐색

트리의 다양한 정보를 DFS로 O(N) 시간에 구하는 방법:

void dfs(int cur, int prv) {
    size[cur] = 1;  // 현재 노드의 크기 초기화

    for(인접 리스트에서 cur이 가진 모든 노드에 방문) {
        int nxt = cur이 가진 다음 자식노드;
        if(nxt == prv) continue;  // 부모노드 재방문 방지

        // 정보를 아래로 전달
        parent[nxt] = cur;        // 부모 노드 정보
        depth[nxt] = depth[cur] + 1;  // 깊이 정보
        sum[nxt] = sum[cur] + nxt;    // 노드 번호의 합

        dfs(nxt, cur);  // 재귀 호출

        // 정보를 위로 전달
        size[cur] += size[nxt];  // 서브트리 크기 갱신
    }
}

DFS 탐색으로 얻을 수 있는 정보

• size[]: 각 노드를 루트로 하는 서브트리의 크기
• parent[]: 각 노드의 부모 노드 정보
• depth[]: 각 노드의 깊이
• sum[]: 루트에서 현재 노드까지의 노드 번호 합