자료구조 : 트리

코테에서 “트리”로 꼭 알아야 하는 것

 

1) 트리 기본 성질

• 간선 수 = 노드 수 – 1
• 사이클 없음
• 연결 그래프
• 부모/자식, 루트, 깊이(depth)

 

 

CBT(Complete Binary Tree, 완전 이진 트리)

• 왼쪽부터 빈틈없이 채워진 이진 트리
• 높이가 같으면 왼→오른쪽 순으로 채움
• CBT 전체 노드 = 2^(h+1) - 1

왜 중요?

• 배열로 자연스럽게 표현 가능 → parent = i, left = 2i, right = 2i+1
• 힙/세그트리 모두 이 원리로 저장됨.

 

힙(Heap)

 

 

 

세그먼트 트리

“배열의 특정 구간(L~R)의 값을 빠르게 계산(합/최대/최소 등)하기 위해 배열을 트리 형태로 쪼개서 저장한 자료구조.”

 

 

                      [1~8]
                /                   \
         [1~4]                         [5~8]
       /       \                    /         \
   [1~2]    [3~4]             [5~6]      [7~8]
    /  \      /  \             ...
 [1] [2]   [3] [4]

 

 

세그먼트 트리 구간 합 찾기

세그먼트 트리가 구간 합을 찾는 방법은 아래 3가지 규칙을 DFS 방식으로 적용하는 것 

 

•  규칙 1 — 완전 불일치 (No Overlap)
  • 현재 노드 구간이 query_l ~ query_r와 전혀 겹치지 않으면 → 0 반환
• 규칙 2 — 완전 일치 (Total Overlap)
  • 현재 노드 구간 (l, r)이 질문 구간에 완전히 포함되면 → 이 노드의 value 바로 사용
• 규칙 3 — 부분 겹침 (Partial Overlap)
  • 완전 불일치도 아니고, 완전 포함도 아니면 → 구간을 절반으로 분할하여 양쪽 값을 더함

 

구간 합 예시

예: query(2, 8) 구하는 과정은 다음과 같은 판단의 반복이다:

• root(1~8): 완전 포함 → 내려감
• 왼쪽(1~4): 부분 겹침 → 분할
• 오른쪽(5~8): 완전 포함 → 바로 값 사용
• 다시 왼쪽(1~2): 부분 겹침 → 분할
• (1): 완전 불일치 → 0
• (2): 완전 포함 → 8 사용
• (3~4): 완전 포함 → 9 사용

 

세그먼트 트리 구현

 

 

public class SegmentTree {

    private int n;              // 배열 크기
    private long[] tree;        // 세그먼트 트리 배열
    private long[] arr;         // 원본 데이터

    public SegmentTree(long[] input) {
        this.n = input.length;
        this.arr = input.clone();

        // 트리 크기는 대략 4배면 충분
        tree = new long[n * 4];

        build(1, 0, n - 1);
    }

    /**
     * 트리 초기 생성 (Build)
     * node: 현재 트리 노드 번호
     * start, end: 담당 구간 [start, end]
     */
    private void build(int node, int start, int end) {
        if (start == end) {
            // leaf node → 단일 값 저장
            tree[node] = arr[start];
        } else {
            int mid = (start + end) / 2;

            build(node * 2, start, mid);          // 왼쪽 자식
            build(node * 2 + 1, mid + 1, end);    // 오른쪽 자식

            // ★ 원하는 연산(sum/min/max)으로 변경
            tree[node] = tree[node * 2] + tree[node * 2 + 1]; // SUM
        }
    }

    /**
     * 단일 값 업데이트 (point update)
     * idx 위치를 val로 변경
     */
    public void update(int idx, long val) {
        update(1, 0, n - 1, idx, val);
    }

    private void update(int node, int start, int end, int idx, long val) {
        if (start == end) {
            // leaf node 갱신
            arr[idx] = val;
            tree[node] = val;
        } else {
            int mid = (start + end) / 2;

            if (idx <= mid)
                update(node * 2, start, mid, idx, val);
            else
                update(node * 2 + 1, mid + 1, end, idx, val);

            // ★ 원하는 연산(sum/min/max)으로 변경
            tree[node] = tree[node * 2] + tree[node * 2 + 1]; // SUM
        }
    }

    /**
     * 구간 질의 (range query)
     * [left, right] 구간의 합/최솟값/최댓값 등 조회
     */
    public long query(int left, int right) {
        return query(1, 0, n - 1, left, right);
    }

    private long query(int node, int start, int end, int left, int right) {

        // 1) 전혀 겹치지 않는 경우 → identity 반환
        // ★ sum = 0, min = INF, max = -INF
        if (right < start || end < left)
            return 0; // SUM 기준 identity

        // 2) 완전히 포함되는 경우
        if (left <= start && end <= right)
            return tree[node];

        // 3) 부분적으로 겹치는 경우 → 두 자식에게 질의 분할
        int mid = (start + end) / 2;
        long q1 = query(node * 2, start, mid, left, right);
        long q2 = query(node * 2 + 1, mid + 1, end, left, right);

        // ★ 원하는 연산(sum/min/max)으로 변경
        return q1 + q2; // SUM
    }
}

 

Fenwick Tree(BIT)란?

refix Sum(누적합)을 O(log N)으로 빠르게 업데이트하는 데이터 구조.