알고리즘/자료구조
[CS] 인덱스 트리와 구현 (JAVA)
인덱스 트리 (Indexed Tree) 포화 이진 트리 형태의 자료구조 순서를 갖는 정보들이 주어졌을 때, 구간의 대표 값이나 연산 결과를 빠르게 얻을 수 있는 자료구조 구간 합, 구간 내 최댓값, 구간 내 카운트 등을 구할 때 많이 쓰인다. 세그먼트 트리는 인덱스 트리가 포함하고 있는 한 종류이다. 리프 노드 : 배열에 적혀 있는 수 내부 노드 : 왼쪽 자식과 오른쪽 자식의 합 리프 노드의 개수가 S개인 포화 이진 트리는 높이가 logS 이고 총 노드 개수는 (2 x S - 1) 개이다. 인덱스 트리 구현 방법 Top-Down 방식 : DFS 기반 트리 탐색 (재귀 호출) 인덱스 트리 개념을 그대로 코드로 수행 왼쪽 자식 = 2 x node, 오른쪽 자식 = 2 x node + 1 이용 가지치기가 가능..
