자료구조 - 인덱스 트리 (Indexed Tree)

1. 인덱스 트리란?

  인덱스 트리(Indexed Tree)란 포화 이진트리 형태의 자료구조로 리프 노드는 배열에 적혀있는 수를 의미하고 내부 노드는 왼쪽 자식과 오른쪽 자식의 합을 이야기 한다.

  리프 노드의 개수가 N개 이상인 포화 이진트리는 높이가 최소 logN이다 리프 노드의 개수가 N개 보다 많아 비어있는 공간이 발생할 경우 구조에 지장이 가지 않도록 초기값을 설정한다.

 

2. 트리 구성 방법

① 리프 노드의 개수가 N개 이상이 되도록 높이가 T인 트리 배열을 만든다. 배열 크기 : 2^T

② 리프 노드에 데이터를 입력한다.

③ 내부 노드를 양쪽 자식 값을 참조하여 데이터를 입력한다.

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

 

3. 구간합 구하는 쿼리 수행 방법

① 루트 노드에서 시작해서 트리를 전위 순회 하는 방식으로 탐색한다.

② 현재 노드가 구하고자 하는 구간에 완전히 속해있으면 그 노드의 결과값을 반환한다.

③ 왼쪽 자식에서 반환된 값과 오른쪽 자식에서 반환된 값을 더해서 반환한다.

◈ 색칠된 노드를 찾기 위해 루트 노드에서 리프 노드까지 탐색하므로 수행 시간은 O(logN)

 

4. 데이터 갱신 방법

① 해당 노드 위치의 값을 수정한다. 

② 부모를 따라 올라가면서 결과값을 수정한다.

③ 3번 위치의 데이터가 3으로 바뀐다면 다음 색칠한 노드들이 수정된다.

◈ 리프 노드부터 루트 노드까지 올라가므로 수행 시간은 O(logN)이다.