인덱스 트리 Index Tree
: 이진트리를 응용한 트리
특정 배열 혹은 수열에서 최댓값, 최솟값, 구간합 등을 구할 때 사용한다.
배열의 값이 여러번 변경되고, 변경될 때마다 최대/최솟값 혹은 부분합을 구해야 할 때 유용하다.
(사실 인덱스 트리보다 세그먼트 트리가 더 흔히 사용된다.)
✔️ 인덱스 트리 VS 세그먼트 트리
- 인덱스 트리: bottom-up 방식
- 세그먼트 트리: top-down 방식
세그먼트 트리가 조금 더 효율적이나 재귀를 사용하여야 하고 인덱스 트리는 while문으로 구현이 가능함
인덱스 트리 시간 복잡도
: O(MlongN)
인덱스 트리의 특징
- 리프 노드에는 실제 데이터가 들어있고 내부 노드에는 왼쪽 자식+오른쪽 자식 이렇게 합이 들어있다.
- (📌)포화 이진 트리 형태의 자료구조를 가진다.
(리프가 모두 차있는 구조로 데이터가 없더라도 0으로 초기화 시켜놓아야 한다.) - 내부 노드의 값을
누적합(구간합)/최대, 최소값/gcd 연산등으로 바꿔 응용이 가능하다.
📌 포화 이진 트리 vs 완전 이진 트리
- 포화 이진 트리: 모든 잎의 레벨이 동일(=깊이가 모두 같음)한 이진 트리로 잎(자식이 없는 노드)이 아닌 내부 노드들은 모두 2개의 자식을 가지는 트리
- 완전 이진 트리: 포화 이진 트리의 leaf들을 오른쪽에서부터 제거해 얻은 트리
포화 이진 트리는 완전 이진 트리이기도 함
높이가
d인 포화 이진 트리의 노드 수 =(2^(d+1))-1완전 이진 트리의 높이가
h라면 노드의 수:2^h < 노드의 수 < 2^(h+1)
완전 이진 트리의 노드 개수가k개라면 트리의 높이는 밑이 2인 log(k)보다 작거나 같음즉, 트리 내에 있는 특정 노드를 찾을 경우 최악의 경우라도
O(log)만에 찾을 수 있음
인덱스 트리 생성
리프 노드는 트리에 최소 N개의 원소를 가지고 있어야 한다. (리프 노드에 실제 데이터를 삽입하기 때문)
따라서 트리를 구현할 배열의 사이즈는 최대 4*N이다.
만약 리프 노드가 8개인 트리에서 5개의 원소가 들어온다면 최댓값을 구할 경우 남는 3개의 노드에 가장 작은 수를 넣고, 최솟값을 구할 경우 가장 큰 수를 넣어 영향을 끼치지 않도록 해준다.
리프 노드를 모두 채웠다면 리프 노드들의 부모 노드를 왼쪽 자식과 오른쪽 자식의 합으로 채워넣는다.
✔️ 구간 s에서 e까지의 합을 구한다고 할 때
s의 인덱스가 홀수라면 오른쪽 부모 노드로 이동,
e의 인덱스가 짝수라면 왼쪽의 부모 노드로 이동하며 값을 저장하면 된다.
이를 수행하다가 경로가 겹치는 순간 더해온 그 값을 반환해주면 원하는 값을 얻을 수 있다.
