Один из способов решить эту проблему - переосмыслить, как строится ваше двоичное дерево поиска, содержащее совокупные итоги. Вместо того чтобы строить двоичное дерево поиска, подумайте о том, чтобы каждый узел интерпретировался следующим образом:
- Каждый узел хранит диапазон значений, которые выделены для самого узла.
- Узлы в левом поддереве представляют выборку из распределения вероятностей слева от этого диапазона.
- Узлы в правом поддереве представляют выборку из распределения вероятностей справа от этого диапазона.
Например, предположим, что наши веса равны 3, 2, 2, 2, 2, 1 и 1 для событий A, B, C, D, E, F и G. Мы строим это двоичное дерево, содержащее A, B , C, D, E, F и G:
D
/ \
B F
/ \ / \
A C E G
Теперь мы аннотируем дерево с вероятностями. Поскольку A, C, E и G - все листья, мы даем каждому из них вероятность, равную единице:
D
/ \
B F
/ \ / \
A C E G
1 1 1 1
Теперь взгляните на дерево, так как B имеет вес 2 для выбора, A имеет вес 3 для выбора и C имеет вероятность 2 для выбора. Если мы нормализуем их до диапазона [0, 1), то на А приходится 3/7 вероятности, а на В и С - 2/7 с. Таким образом, у нас есть узел для B, который говорит, что все в диапазоне [0, 3/7) переходит в левое поддерево, что-либо в диапазоне [3/7, 5/7) отображается в B, и все в диапазоне [5 / 7, 1) отображается на правильное поддерево:
D
/ \
B F
[0, 3/7) / \ [5/7, 1) / \
A C E G
1 1 1 1
Аналогично, давайте обработаем F. E имеет вес 2, выбранный, в то время как F и G каждый имеет вес вероятности 1, который будет выбран. Таким образом, поддерево для E составляет здесь 1/2 массы вероятности, узел F - 1/4, а поддерево для G - 1/4. Это означает, что мы можем назначить вероятности как
D
/ \
B F
[0, 3/7) / \ [5/7, 1) [0, 1/2) / \ [3/4, 1)
A C E G
1 1 1 1
Наконец, давайте посмотрим на корень. Общий вес левого поддерева равен 3 + 2 + 2 = 7. Общий вес правого поддерева равен 2 + 1 + 1 = 4. Вес самого D равен 2. Таким образом, левое поддерево имеет вероятность 7/13 из будучи выбранным, D имеет вероятность 2/13 выбора, а правильное поддерево имеет вероятность 4/13 выбора. Таким образом, мы можем завершить вероятности как
D
[0, 7/13) / \ [9/13, 1)
B F
[0, 3/7) / \ [5/7, 1) [0, 1/2) / \ [3/4, 1)
A C E G
1 1 1 1
Чтобы сгенерировать случайное значение, вы должны повторить следующее:
- Начиная с корня:
- Выберите равномерно-случайное значение в диапазоне [0, 1).
- Если он находится в диапазоне для левого поддерева, спускайтесь в него.
- Если оно находится в диапазоне правого поддерева, спускайтесь в него.
- В противном случае вернуть значение, соответствующее текущему узлу.
Сами вероятности могут быть определены рекурсивно при построении дерева:
- Левая и правая вероятности равны 0 для любого конечного узла.
- Если внутренний узел сам имеет вес W, его левое дерево имеет общий вес W L , а его правое дерево имеет общий вес W R , то левая вероятность равна (W L ) / (Ш + Ш Л + Ш Р ) и правильная вероятность равна (Ш Р ) / (Ш + Ш L + W R ).
Причина, по которой эта переформулировка полезна, заключается в том, что она дает нам возможность обновлять вероятности за O (log n) времени на каждую обновленную вероятность. В частности, давайте подумаем о том, какие инварианты изменятся, если мы обновим вес определенного узла. Для простоты, давайте предположим, что узел на данный момент является листом. Когда мы обновляем вес конечного узла, вероятности все еще правильны для конечного узла, но они неправильны для узла чуть выше него, потому что вес одного из поддеревьев этого узла изменился. Таким образом, мы можем (за O (1) раз) пересчитать вероятности для родительского узла, просто используя ту же формулу, что и выше. Но тогда родительский узел этого узла больше не имеет правильных значений, потому что один из его весов поддерева изменился, поэтому мы также можем пересчитать вероятность там. Этот процесс повторяется вплоть до корня дерева, при этом мы выполняем O (1) вычисление для уровня, чтобы исправить веса, назначенные каждому ребру. Предполагая, что дерево сбалансировано, мы должны сделать O (log n) общей работы, чтобы обновить одну вероятность. Логика идентична, если узел не является листовым узлом; мы просто начинаем где-нибудь на дереве.
Короче, это дает
- O (n) время для построения дерева (используя подход снизу вверх),
- O (log n) время для генерации случайного значения и
- O (log n) время для обновления любого одного значения.
Надеюсь, это поможет!