Предыдущий ответ правильный, но я подумал, что картинки могут помочь.
Пробное пространство (или пространство вероятностей) - это набор всех возможных результатов. И индивидуальные вероятности всех этих исключительных результатов в сумме составят 1. Например, если в конкретном пространстве выборки есть только два взаимоисключающих результата A и B, а вероятность A равна 1/4, то вероятность Bдолжно быть 3/4.
В вашем случае есть два результата: либо k-1-й наименьший узел находится в левом подпапке корня, либо k-1-й наименьший узел находится в правом подпапке.
Прежде чем подумать о том, куда мы поместим наименьший узел kth , примерное пространство выглядит следующим образом. Два результата представлены квадратом, и оба квадрата равны по размеру (1/2 + 1/2 = 1)
Но тогда предложениесказал что-то вроде «давайте предположим, что k-й наименьший узел находится в одной из подголовок, и давайте выберем левый, потому что нам это нравится»Всего можно выбрать из N-1 узлов (N-1, потому что корень не является частью этого выбора). Ниже показано, где мы разместили k-й наименьший узел. Общее количество узлов, из которых можно выбрать k-1-е наименьшее, изменилось (и этот факт изменит формы в нашем образце пространства).
Итак, теперь вероятность того, что k-1-й наименьший узел окажется в левом подголовнике, была уменьшена на (1 / N-1).
И это показано ниже путем удаления треугольника из Черного квадрата. (Это могла быть любая форма, но я выбрал треугольник). Этот треугольник должен куда-то идти, потому что все должно складываться до 1. Количество узлов не имеет значения. Мы уменьшили вероятность одного результата на размер этого треугольника, и, следовательно, увеличили вероятность другого результата на ту же величину. Теперь пространство выглядит следующим образом.
Дерево вероятностей - полезный способ думать об этом.