[CS] 인덱스 트리와 구현 (JAVA)

인덱스 트리 (Indexed Tree)

포화 이진 트리 형태의 자료구조

순서를 갖는 정보들이 주어졌을 때, 구간의 대표 값이나 연산 결과를 빠르게 얻을 수 있는 자료구조
구간 합, 구간 내 최댓값, 구간 내 카운트 등을 구할 때 많이 쓰인다.
세그먼트 트리는 인덱스 트리가 포함하고 있는 한 종류이다.

출처 : https://beenii.tistory.com/156

• 리프 노드 : 배열에 적혀 있는 수
• 내부 노드 : 왼쪽 자식과 오른쪽 자식의 합

리프 노드의 개수가 S개인 포화 이진 트리는 높이가 logS 이고 총 노드 개수는 (2 x S - 1) 개이다.
 

인덱스 트리 구현 방법

• Top-Down 방식 : DFS 기반 트리 탐색 (재귀 호출)

인덱스 트리 개념을 그대로 코드로 수행
왼쪽 자식 = 2 x node, 오른쪽 자식 = 2 x node + 1 이용
가지치기가 가능함 (더 이상 탐색하지 않아도 되는 곳은 가지 않음)
x번째로 빠른 숫자 등 카운팅 쿼리가 가능함

• Bottom-Up 방식 : 반복문 기반 트리 탐색

인덱스의 홀짝 특성을 이용함
부모 노드 = node / 2 이용
코드가 더 단순함
수행 속도가 미세하게 빠름
 

트리 구성 방법 구현

트리의 노드 개수는 약 2N 개이다. 따라서, 수행시간은 \(O(N)\) 이다.

• Top-Down 방식

long init(int left, int right, int node) {
    // 리프 노드일 경우
    if (left == right) {
        if (left <= N)
            tree[node] = nums[left];
        else
            tree[node] = 0;
    }
    // 내부 노드일 경우
    else {
        int mid = (left + right) / 2;
        long leftResult = init(left, mid, node * 2);
        long rightResult = init(mid + 1, right, node * 2 + 1);
        tree[node] = leftResult + rightResult;
    }

    return tree[node];
}

• Bottom-Up 방식

void init() {
    // 자식 노드는 데이터로 채움
    for (int i = 0; i < N; i++) {
        tree[S + i] = nums[i];
    }

    // 내부 노드는 자식의 합으로 채움
    for (int i = S - 1; i >= 0; i--) {
        tree[i] = tree[i * 2] + tree[i * 2 + 1];
    }
}

 

쿼리 수행 방법 구현

• Top-Down 방식 : 루트 노드에서 리프 노드까지 탐색하므로 수행시간은 \(O(logN)\) 이다.

long query(int left, int right, int node, int queryLeft, int queryRight) {
    // 1. 연관 없음
    if (queryRight < left || right < queryLeft) {
        return 0;
    }
    // 2. 판단 가능 (쏙 들어있음)
    else if (queryLeft <= left && right <= queryRight) {
        return tree[node];
    }
    // 3. 판단 불가 (걸쳐 있음)
    else {
        int mid = (left + right) / 2;
        long leftResult = query(left, mid, node * 2, queryLeft, queryRight);
        long rightResult = query(mid + 1, right, node * 2 + 1, queryLeft, queryRight);
        return leftResult + rightResult;
    }
}

• Bottom-Up 방식 : 리프 노드에서 루트 노드까지 올라가면서 연산하므로 수행시간은 \(O(logN)\) 이다.

long query(int queryLeft, int queryRight) {
    long sum = 0;
    int left = S + queryLeft - 1;
    int right = S + queryRight - 1;

    while (left <= right) {
        if (left % 2 == 1) {
            sum += tree[left++];
        }

        if (right % 2 == 0) {
            sum += tree[right--];
        }

        left /= 2;
        right /= 2;
    }

    return sum;
}

 

데이터 갱신 방법 구현

• Top-Down 방식 : 루트 노드에서 리프 노드까지 내려가면서 갱신하므로 수행시간은 \(O(logN)\) 이다.

void update(int left, int right, int node, int target, long diff) {
    // 1. 연관 없음
    if (target < left || right < target)
        return;
    // 2. 연관 있음
    else {
        tree[node] += diff;
        if (left != right) {
            int mid = (left + right) / 2;
            update(left, mid, node * 2, target, diff);
            update(mid + 1, right, node * 2 + 1, target, diff);
        }
    }
}

• Bottom-Up 방식 : 리프 노드에서 루트 노드까지 올라가면서 갱신하므로 수행시간은 \(O(logN)\) 이다.

void update(int target, int value) {
    int node = S + target - 1;
    tree[node] = value;
    node /= 2;
    while (node > 0) {
        tree[node] = tree[node * 2] + tree[node * 2 + 1];
        node /= 2;
    }
}