[Algorithm] 구간 트리 : Segment Tree

Intro

구간 트리를 이용해 특정 구간을 효율적으로 탐색하는 알고리즘을 학습했다.

구간(부분) 트리

주어진 배열에서 특정 구간의 최소값을 구하는 단순한 알고리즘의 시간복잡도는 O(N)이다. 그러나 구간 트리라는 자료구조를 이용하면 이를 O(logN)으로 줄일 수 있다.

구간 트리는 위의 이미지와 같이 주어진 객체(배열)을 절반으로 나눠 결국 요소 하나만 남을 때까지 반복해서 자료로 저장한다. 만약 저 중 0~4번까지의 데이터가 필요하다면 2번 노드와 12번 노드에만 접근하면 된다. 모두 순회 할 필요가 없는 것이다.

풀어본 문제는 객체의 여러 특정 구간에서 최솟값을 찾는 문제였다. 학습한 코드를 주석으로 풀어내어 기록한다.

const rangeMinimum = function (arr, ranges) {
  // ts: tree start. te: tree end
  // arr의 ts부터 te까지를 tree로 만든다.
  const createMinTree = (arr, ts, te) => {
    // base case
    if (시작점과 마지막점이 동일해지면) {
      // 만들어진 트리를 리턴
    }

    // recursive case
    // 현재 범위를 절반을 기준으로 왼쪽과 오른쪽으로 나눈다
    const mid = parseInt((ts + te) / 2);
    const left = createMinTree(arr, ts, mid);
    const right = createMinTree(arr, mid + 1, te);

    return {
      // value: left값과 right값 중 작은 값을 저장 (최솟값을 구하고 있으므로)
      // left,
      // right,
    };
  };
  const tree = createMinTree(arr, 0, arr.length - 1);

  // 범위를 입력 받는다. rs: range start, re: reange end
  const findMin = (ts, te, rs, re, tree) => {
    // base case
    if (현재 tree와 구간이 일치하거나 구간이 tree를 포함할 경우) {
      // 1번(최초) 노드의 값을 리턴
    }

    if (현재 tree에 주어진 구간이 겹치지 않는 경우) {
      // 임의의(약속된) 값을 리턴
    }

    // 겹치는 부분이 존재하는 경우
    const mid = parseInt((ts + te) / 2);
    return Math.min(입력받은 트리의 왼쪽 중 최솟값, 오른쪽 중 최솟값);
  };

  // 인자 range : 여러 특정 구간
  const mins = ranges.map((range) => {
    const [start, end] = range;
    return findMin(0, arr.length - 1, start, end, tree);
  });
  return mins;
};