확률 및 점근선

Question

이진 탐색 트리에 대해 동일한 입력이없는 경우를 고려하십시오. 노드를 삽입하는 동안 x.left 및 x.right 중에서 무작위로 선택합니다.

clrs (12-1- (d))에는이 설정의 예상 실행 시간을 유도하는 질문이 있습니다. 직관적으로 대답은 단순히 O (ng n)입니다. 그러나 어떻게 증명할 수 있습니까?

어떤 조언을 부탁드립니다.

문.

Answer 1

이 프로세스가 완료된 후 최종 트리가 있다고 가정 해보십시오. 숫자 1, 2, 3, ..., n을 사용하여 트리의 각 노드에 레이블을 지정하여 결과 트리가 이진 검색 트리가되도록합니다. 이제 트리를 구성하는 프로세스를 재생하여 각 요소가 어디에서 끝났는지를 상상해보십시오. 추적을 끝내는 프로세스는 숫자 값을 기반으로 각 요소에 대해 일반 BST 삽입을 수행하는 것과 동일합니다. 따라서이 문제는 다음 문제와 동일합니다. 1, 2, 3, ..., n 요소의 임의의 순열을 이진 검색 트리에 삽입하면 예상되는 소요 시간은 얼마입니까? 그래서?

이 문제에 대한 답변을 이미 알고 있다면 완료되었습니다. 그렇지 않다면, 하나의 귀여운 트릭은이 프로세스가 요소 1, 2, 3, ..., n의 배열에 대해 무작위로 추출 된 quicksort를 실행하는 것과 동일하다는 것을 깨닫는 것입니다. 이것을 볼 수있는 한 가지 방법이 있습니다. 트리의 루트 요소는 선택된 첫 번째 피벗 요소에 해당합니다. 삽입 된 모든 요소는이 요소와 비교되어 왼쪽 또는 오른쪽 하위 트리에 배치됩니다. 루트의 왼쪽 하위 요소는 초기 피벗보다 작은 요소에 대한 재귀 호출에서 선택한 피벗과 일치합니다. 초기 피벗보다 작은 모든 요소는 왼쪽 피벗과 비교됩니다. 유도를 사용하여이 인수를 공식화 할 수 있습니다. 길이 n의 임의의 배열에 대해 원소 1, 2, 3, ..., n의 무작위 순열을 이진 검색 트리에 삽입 할 때 비교 횟수를 구조체가 트리에 주어진 패턴을 따르는 피벗을 사용하여 해당 배열에서 quicksort를 수행합니다.

연결이 완료되면 예상되는 무작위 퀵 소트 비용이 Θ (n log n)이므로 완료됩니다.