AVL 트리에서 특정 범위 내의 노드 수를 카운트

Question

< O (log n) 시간의 순위를 사용하여 균형 잡힌 이진 검색 트리에서 주어진 노드 2 개 사이의 노드 수 (개수)를 찾는 방법이 있습니까?

각 노드의 순위 (또는 높이)를 Node 클래스의 멤버 변수로 동적으로 저장한다고 가정 할 수 있습니다. 그래서, 우리는 그것을 직접 접근 할 수 있습니다.

Answer 1

예, lowest common ancestor 쿼리를 사용하면 일정한 시간 간격으로 노드를 계산할 수 있습니다. 선형 시간에 한 번 트리 전처리가 필요합니다.

두 노드의 가장 낮은 공통 조상의 순위를 알고있는 경우 자식 노드의 순위에서 조상의 순위를 빼서 노드와 조상 사이의 노드 수를 계산할 수 있습니다.

nodes_between = a.rank + b.rank - 2*(lowest_common_ancestor(a, b).rank) + 1 

하면 위의 두 끝점을 포함하여 노드 a와 b 사이의 경로의 길이를 반환합니다. + 1은 가장 낮은 공통 조상 그 자체입니다. lowest_common_ancestor 찾기는 일정 시간 내에 수행 될 수 있으며 계산은 일정 시간입니다.