트리 계산을 위한 배열(인덱스) 표현

*'Do it! 알고리즘 코딩 테스트 자바편'을 참고했습니다.

직관적이면서 편리한 트리 자료구조는 "배열"

위키독스 이미지

인덱스	0	1	2	3	4	5	6	7
값	A	B	C	D	E	F	None	G

트리의 노드와 배열의 인덱스 사이 상관관계

이동 목표 노드	인덱스 연산	제약 조건(N = 노드)
root node	index = 1
parent node	index = index / 2	not root node
left child node	index = index * 2	index * 2 <= N
right child node	index = index * 2 + 1	index * 2 + 1 <= N

위 인덱스 연산 방식은 segment tree나 LCA(lowest common ancestor) 알고리즘에서도 기본이 되는 연산이므로 숙지해야 한다.