Запутано в требовании в CLRS, случайным образом построенное доказательство бинарного дерева поиска

Question

Не уверен, стоит ли вместо этого помещать это в математический обмен стека, ну да ладно.

На странице 300 CLRS ...

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-i. Моя проблема в том, что часть, Кроме количества ключей, которые она содержит ... Да, структуры поддеревьев не зависят от Rn, но тот факт, что Rn влияет на количество ключей в поддеревьях, по-видимому, подразумевает зависимость из-за того, как оно ограничивает высоту поддеревьев.

Мне явно не хватает некоторых ключевых отношений. Любая помощь приветствуется, спасибо.

Answer 1

Для ожидаемого времени вы можете считать, что каждая вставка является независимым событием.Средство вставки не является состязательным (то есть не пытается сломать ваше двоичное дерево).Теперь, если это действительно случайно, то вы можете рассматривать каждое другое (каждое нечетное или каждое четное) значение, которое будет вставлено, как вставленное как плохой узел.Плохие узлы - это те, которые заставляют дерево увеличиваться в высоте.У плохих узлов есть хорошие узлы между ними.

Если у вас уже есть дерево с высотой 'h' (считайте, что оно имеет O (2 ^ h) узлов), то у него будет O (2 ^ (h-1))) узлы в виде листьев (примерно половина всех узлов - листья).Существует равная вероятность того, что новое значение может появиться где угодно (то есть как дочерний элемент любого из этих узлов).Ожидается, что половина из них станет левым потомком листа (увеличив высоту узла листа на 1), а другая половина станет правым потомком этого листа.Это дает ожидаемую O (log n) высоту дерева.Следовательно, каждая операция с таким деревом стоит O (log n).