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

Question

Учитывая BST (может быть или не быть сбалансированным), как можно вернуть "любой" узел равномерно случайным образом? Ограничение: вы не можете использовать внешнюю структуру данных индексации. Вы должны пройти по дереву таким образом, чтобы каждый узел имел равные шансы на посещение.

Этот вопрос меня озадачил довольно давно. Если мы действительно можем использовать внешние хеш-таблицы / указатели, мы могли бы просто рандомизировать их и вернуть соответствующий узел. Однако мой коллега выдвинул довольно сложный вариант вопроса, в котором нельзя использовать дополнительные структуры данных.

• Простое случайное блуждание с вероятностью 50-50 любого из двух вариантов L/R не работает, так как вероятность возврата узла в нижней части дерева намного меньше (вероятности составные)
• Даже случайно генерируя глубину d и проходя не более d узлы для возврата узла (или остановки, если это лист) не генерируют равномерное распределение.

Обновление: вы не можете пройтись по порядку и сохранить результат в массиве.

Как можно достичь такого обхода?

Answer 1

Обходите дерево в любом порядке, сохраняя следующие значения:

• N: количество увиденных узлов

• selected: текущий выбранный узел.

Первоначально, N 0 и selected является None, Посещение узла состоит из следующего:

1. инкремент N

2. Генерация случайного целого числа в диапазоне [0, N),

3. Если выбрано случайное целое число 0, установите selected на текущий узел.

Обратите внимание, что значения N а также selected должны быть изменены во время прогулки. Это означает, что они являются входными и выходными значениями для функции посетителя.

В конце прогулки, N будет количество узлов в дереве, и selected будет случайным узлом, выбранным с одинаковой вероятностью (при условии, что у вас есть хороший генератор случайных чисел).

Этот алгоритм не ограничивается BST. Он будет работать на любом дереве любой формы. В частности, он будет работать с простой линейной последовательностью объектов неизвестной длины, соответствующей хорошо известному алгоритму случайного выбора, который должен выполнять итерацию по объектам, заменяя выбранный случайный объект вновь посещенным с вероятностью 1/N где N количество объектов, увиденных на сегодняшний день.

Если вы отслеживаете посещенные узлы, он также будет работать на любом связанном графе.

Если у вас очень большое дерево (или график), возможно, распределенное по нескольким серверам и / или устройствам хранения, вы можете использовать другое представление этого алгоритма, которое обеспечивает определенный уровень параллелизма (а также предотвращает необходимость сохранить глобальную структуру прогулки или передать значения в прогулку).

Мы предполагаем, что каждый узел-сервер имеет прямой доступ к k объекты и косвенный доступ к некоторому известному количеству дочерних серверов. Алгоритм учитывает избыточные дочерние элементы, но предполагает, что сетевое взаимодействие (почти) идеально; работа с сетевыми разбиениями выходит за рамки этого ответа. Мы также предполагаем, что каждый запрос имеет связанный уникальный номер запроса, что позволяет нам иметь дело с некоторыми сетевыми артефактами. Запрос не содержит никакой другой информации (кроме сервера, на который нужно ответить), и ожидается, что он вернет кортеж, состоящий из счетчика и случайно выбранного узла.

Когда узел-сервер получает запрос с идентификатором q, он делает следующее:

1. Если он ранее ответил на запрос q, немедленно вернитесь <0, null>

2. Задавать count в k а также selected на случайно выбранный объект из k объекты, к которым он имеет прямой доступ.

3. Для каждого дочернего сервера отправьте запрос (с тем же идентификатором запроса)

4. Для каждого возвращенного ответа (не имеет значения, в каком порядке поступают ответы):

   а. добавлять response.count в count

   б. С вероятностью response.count / countзаменить selected с response.selected

5. Когда все дочерние серверы ответили, верните <count, selected>

Answer 2

Если вам известно количество узлов n в дереве, найдите k-й узел в обходе дерева по порядку для некоторого случайно выбранного k в диапазоне от 0 до n-1 включительно. Если вы этого не сделаете, вы можете пройтись по дереву и выяснить его размер, а затем сделать выше.

Если узлы дерева хранятся непрерывно в каком-либо массиве, случайным образом выберите элемент массива и верните его.

Если каждый узел дерева может сообщить вам размер корневого поддерева, выясните, сколько узлов в дереве, сгенерируйте случайное число k вплоть до количества узлов в дереве и выберите k-й элемент дерева.

Во всех вышеперечисленных случаях "древовидная" часть представляет собой красную сельдь.

Существует случайное блуждание на любом нетривиальном связном графе, стационарное распределение которого равномерно. Выберите соседа текущего узла. Если это имеет более низкую или равную степень, иди туда. Если он имеет более высокую степень, идите туда с вероятностью cur_deg / that_deg и оставайтесь на месте в противном случае. Выборка из этого случайного блуждания в разных контекстах называется "выборка Гиббса" и "Метрополис-Гастингс".

Answer 3

Если у вас есть полное (нижний уровень полностью заполнено) двоичное дерево поиска, то можно быстро (сублинейное время) сделать так, как вы просите, потому что вы знаете структуру дерева. Если вы хотите, чтобы я опубликовал ответ, который дает решение для этого случая, дайте мне знать, и я обновлю свой ответ. Однако, если у вас просто есть универсальное бинарное дерево поиска произвольной формы, то невозможно получить единообразную выборку узла, не посещая все дерево, чтобы вы знали форму.