Как выбрать случайный узел из дерева

Question

Как можно было бы выбрать случайный элемент из дерева?Нужно ли заранее знать глубину / размер дерева?

Answer 1

Это не так.Чтобы случайным образом выбрать узел равномерно, просто выполните итерацию по дереву в любом порядке.Пусть исследуемый n-й узел будет выбранным с вероятностью 1 / n.То есть сохраняйте запись узла, который вы бы вернули, в переменной, а когда вы смотрите на n-й узел, замените текущий узел на n-й с вероятностью 1 / n.По индукции вы можете показать, что это возвращает узел равномерно в случайном порядке, без необходимости заранее знать, сколько их.

Answer 2

Если вы структурировали свои листья так, чтобы они сохранялись в индексируемом типе данных, таком как массив, то вы можете легко (псевдокод):

random_leaf = leaf_pile[ random( size of leaf pile ) ]

Это хороший, освежающий O1): -)

Конечно, могут быть дыры, поэтому вам, возможно, придется итерировать оттуда.Если он хранится в виде связанного списка, вы можете выполнить итерацию.

Просто предоставьте альтернативу очевидному.Это действительно зависит от вашей структуры данных и вашего наиболее распространенного варианта использования.

Answer 3

Просто выполните для каждого узла случайный вызов в диапазоне от 0 до (количество дочерних элементов) -1 и выберите следующего дочернего элемента после этого номера.

Повторяйте это, пока не окажетесь в листе.