최소공통조상(LCA) 알고리즘

트리에서 특정 두개의 노드의 공통조상을 찾는 알고리즘

선형 탐색을 이용하여 찾을 수도 있다.
이때, 둘 다 높이를 올려가며 찾기 때문에 깊이가 다를 경우 속도가 달라 공통조상을 찾지 못할 수 있다. 따라서 깊이를 동일하게 맞춰준다.

희소배열을 활용해 개선한 경우, $2^i$번째 조상을 비교하여 찾는다.

$2^i$랑 $2^i+1$ 사이에 공통조상이 있을 경우?
동일한 깊이로 조정한 다음 조상을 탐색하기 때문에 희소배열을 이용할 시 자동으로 고려된다고 한다.
-> 인덱스를 말하는 것인지도...

조상 비교시, 역순으로 비교한다.
가장 긴 노드간의 거리 조사하는 거랑 비슷한건가
알고리즘 리뷰도 보고있는데 머리 깨질것같다
으아아아아악

희소배열?
배열 원소의 개수가 무조건 length값 보다 작은 배열.
메모리를 더 적게 사용한다.

참고자료
최소공통조상
희소배열