CLRS의 주장에 혼동 이진 검색 트리 증명을 임의로 만들었습니다

Question

대신 수학 stackexchange에 넣어야할지 잘 모르겠지만 오. CLRS의 페이지 (300)에

...

Theorem 12.4 
The expected height of a randomly built binary search tree on n distinct keys is O(lgn). 

그들은 3 개 확률 변수 ...

'Xn' is the height of a randomly built binary search on n keys. 
'Yn' is the "exponential height", where Yn = 2^(Xn) 
'Rn' is the position that the root key would occupy if the key's were sorted, its rank. 

및 표시 확률 변수 Zn,1 Zn,2 Zn,3 ... Zn,n ...

'Zn,i = I{Rn = i}' 

을 정의 그래서 그들은 증거를 만들기 위해 계속 진행하지만 (텍스트 참조), 그 가운데에서 다음과 같은 주장을합니다 ...

We claim that the indicator random variable Zn,i = I{Rn = i} is independent of the 
values of Yi-1 and Yn-i. Having chosen Rn = i, the left subtree (whose exponential 
height is Yi-1) is randomly built on the i-1 keys whose ranks are less than i. This 
subtree is just like any other randomly built binary search tree on i-1 keys. 
Other than the number of keys it contains, this subtree's structure is not affected 
at all by the choice of Rn = i, and hence the random variables Yi-1 and Zn,i are 
independent. 

마찬가지로 Yn-1. 내 문제는 그 부분입니다 ... 예, 하위 트리의 구조는 Rn의 영향을받지 않지만 Rn이 하위 트리의 키 수에 영향을 미칩니다. 의존성은 서브 트리의 높이를 어떻게 제한하는지에 따라 달라집니다.

분명히 중요한 관계가 누락되었습니다. 감사합니다. 감사합니다.

Answer 1

예상되는 시간 동안 모든 삽입이 독립적 인 이벤트라고 생각할 수 있습니다. 삽입 기는 적대적이지 않습니다 (즉, 이진 트리를 손상시키지 않음). 자, 이것이 정말로 무작위 인 경우, 다른 모든 (홀수 또는 모든 짝수) 값을 나쁜 노드로 삽입하는 것으로 삽입 할 수 있습니다. 나쁜 노드는 트리의 높이를 증가시키는 노드입니다. 나쁜 노드는 그들 사이에 좋은 노드를 가지고있다.

높이가 'h'인 트리가 이미있는 경우 (O (2^h) 노드라고 생각할 때), O (2^(h-1)) 개 노드가 잎 노드는 잎). 새로운 값이 어디든지 이동하는 동일한 확률이 있습니다 (즉, 해당 노드 중 하나의 하위 노드). 그 중 절반은 나뭇잎의 자식으로 남을 것이고 (나머지 하나는 잎 노드의 높이를 1로 증가시킬 것입니다) 나머지 절반은 그 잎의 오른쪽 자식이 될 것으로 예상됩니다. 이것은 트리에 예상되는 O (log n) 높이를 제공합니다. 따라서, 그러한 트리에 대한 모든 연산은 O (log n)의 비용이 듭니다.