Вероятность двоичного дерева поиска

Question

Предположим, что BST был построен исключительно с вставками, и все блокировки клавиш одинаково вероятны. Вам задан корень определенного дерева, какова вероятность того, что данное дерево было построено?

Answer 1

Ответ на этот вопрос может быть рассчитан рекурсивно.

проблема. дерева = проблема. правильного выбора корня * prob. образующегося левого поддерева * prob. правого поддерева

Теперь нам нужно найти проблему. правильного выбора корня, который равен 1/num. узлов.