inorder 알고리즘을 사용하여 이진 검색 트리에서 후미 요소를 찾기위한 상각 된 시간은 얼마입니까?

Question

분석을 할부 상환하고 계승 함수 (inorder 알고리즘에서 다음 요소를 찾는 함수)가 평균 O (1)을 취하는 것을 증명할 수 있습니까? 찾은 마지막 요소에서 후속 함수가 작동한다고 가정합니다. O (1)도 맞습니까? 그것은 O (log n)입니까?

Answer 1

그것에 대해 생각하는 한 가지 방법은 후속 기능의 응용 프로그램 전체 트리를 통과하는 것입니다. N 전체 트리를 가로 지르는 과정의 복잡성은 무엇입니까? 그리고 그것이 N 함수 호출을 통해 상각 될 때 무엇입니까?