Я могу вспомнить три основных метода, один из которых включает в себя частую проверку, а другой - хранение дополнительной информации.Я думаю, что выполнение одной или другой из этих вещей неизбежно.Я собираюсь начать с дополнительной информации:
В каждом узле сохраните число count, которое представляет количество его потомков.Для каждого узла вам нужно иметь число от 1 до count, чтобы этот узел сообщал вам, идти ли влево или вправо, сравнивая его с количеством левых детей.Вот алгоритм:
n := random integer between 1 and root.count
node := route
while node.count != 1
if n <= node.left.count
node = node.left
else
node = node.right
n = n - node.left.count
Итак, по сути, мы накладываем порядок слева направо на все узлы и выбираем n-й слева.Это довольно быстро, только имея O (глубину дерева), что, вероятно, лучшее, что мы можем сделать, не делая чего-то вроде создания вектора, который содержит все метки узла.Это также добавляет издержки O (глубина дерева) к любым изменениям в дереве, так как количество должно быть исправлено.Если вы идете другим путем и вообще никогда не меняете дерево, а собираетесь многократно выбирать случайные узлы, просто укусите маркер и поместите все метки узлов в вектор.Таким образом, вы можете выбрать случайную единицу в O (1) после O (N) начального времени установки.
Если, однако, вы не хотите использовать какое-либо место для хранения, вот альтернатива смного переоценки.Сначала найдите границу (которую я обозначу B) для глубины дерева (мы можем использовать N-1, если необходимо, но, очевидно, это очень свободная граница. Чем жестче граница, которую можно найти, тем быстрее алгоритмработает).Далее мы собираемся сгенерировать возможную метку узла случайным, но равномерным способом.Есть 2 ^ (B + 1) -1 возможностей.Это не просто 2 ^ B, потому что, например, строки «0011» и «11» - это совершенно разные строки.В результате нам нужно посчитать все возможные двоичные строки длиной от 0 до B. Очевидно, у нас есть 2 ^ i строк длины i.Таким образом, для строк длиной i или меньше мы имеем сумму (от i = 0 до B) {2 ^ i} = 2 ^ (B + 1) -1.Итак, мы можем просто выбрать число от 0 до 2 ^ (B + 1) -2 и затем найти соответствующую метку узла.Конечно, преобразование чисел в метки узлов не является тривиальным, поэтому я предоставлю это здесь.
Мы преобразуем выбранное число в строку битов обычным способом.Затем, читая слева, если первая цифра равна 0, то метка узла - это оставшаяся строка справа (возможно, пустая строка, которая является допустимой меткой узла, хотя вряд ли будет использоваться).Если первая цифра - 1, то мы выбрасываем ее и повторяем этот процесс.Таким образом, если B = 4, то метка узла «0001» будет исходить из числа «00001».Метка узла «001» будет исходить из числа «10001».Метка узла "01" будет исходить из числа "11001".Метка узла "1" будет исходить из числа "11101".И метка узла "" будет исходить из числа "11110".Мы не включили число 2 ^ (B + 1) -1 (в данном случае «11111»), которое не имеет действительной интерпретации по этой схеме.Я оставлю это в качестве упражнения для читателя, чтобы доказать себе, что каждая строка длиной от 0 до B может быть представлена в этой схеме.Вместо того, чтобы пытаться доказать это, я просто утверждаю, что это будет работать.
Так что теперь у нас есть метка узла.Следующий шаг - проверить, существует ли эта метка, пройдя по дереву.Если это произойдет, мы сделали.Если этого не произойдет, выберите новый номер и начните все сначала (это проверяющая часть).Вероятно, придется много пересматривать, поскольку будет использоваться только небольшая доля легальных меток узлов, но это не искажает справедливость, а только увеличивает время.
Вот псевдокодовая версияэтот процесс в четырех функциях:
function num_to_binary_list(n,digits) =
if digits == 0 return ()
if n mod 2 == 0 return 0 :: num_to_digits(n/2,digits-1)
else return 1 :: num_to_digits((n-1)/2,digits-1)
function binary_list_to_node_label_list(l) =
if l.head() == 0 return l.tail()
else return binary_list_to_node_label_list(l.tail())
function check_node_label_list_against_tree(str,node) =
if node == null return false,null
if str.isEmpty()
if node.isLeaf() return true,node
else return false,null
if str.head() == 0 return check_node_label_list_against_tree(str.tail(),node.left)
else check_node_label_list_against_tree(str.tail,node.right)
function generate_random_node tree b =
found := false
while (not found)
x := random(0,2**(b+1)-2) // We're assuming that this random selects inclusively
node_label := binary_list_to_node_label(num_to_binary_list(x,b+1))
found,node := check_node_label_list_against_tree(node_label,tree)
return node
Анализ времени для этого, конечно, довольно ужасен. Обычно цикл while будет выполняться в среднем (2 ^ (B + 1) -1) / N раз. Итак, в худшем случае это O ((2 ^ N) / N), что ужасно. В лучшем случае B будет порядка log (N), поэтому оно будет примерно равно O (1), но для этого необходимо, чтобы дерево было достаточно сбалансированным, чего не может быть. Тем не менее, если вы действительно не хотите лишнего пространства, этот метод делает это.
Я не думаю, что вы можете сделать лучше, чем этот последний метод, не сохраняя некоторую информацию. Это звучит привлекательно, чтобы иметь возможность обходить дерево, принимать случайные решения на ходу, но без сохранения дополнительной информации о структуре вы просто не сможете это сделать. Каждый раз, когда вы принимаете решение о ветвлении, у вас может быть только один узел с левой стороны и миллион узлов с правой стороны, или миллион узлов с левой стороны и только один с правой стороны. Поскольку оба варианта возможны, и вы не знаете, в чем дело, просто нет способа принять хотя бы случайное решение между двумя сторонами. Очевидно, что 50-50 не работает, и любой другой выбор будет таким же проблематичным.
Итак, если вам не нужно дополнительное пространство, второй метод будет работать, но будет медленным. Если вы не возражаете добавить дополнительное место, первый метод будет работать и будет быстрым. И, как я уже говорил ранее, если вы не собираетесь менять дерево, и вы будете выбирать много случайных узлов, то прикусите пулю и просто переберите дерево и вставьте все листовые узлы в саморазвивающийся массив или вектор, а затем выбрать из этого.