4 ms·
Red-black trees are far too complex for this simple task : just use any binary balanced tree so that the maximum height is O(log n). (red-black trees will work
by loicfevrier 18y ago
Red-black trees are far too complex for this simple task :
just use any binary balanced tree so that the maximum height is O(log n). (red-black trees will work but take any one you want, red-black tree are slow)
On each node you store two numbers :
- sum of the weights at the left
- sum of the weights at the right
Want you want to choose an item just explore the tree and for each node choose left or right according to the two weights.
==> O(log n)
If you update an item you'll need to update all the weight up to the root of the tree.
==> O(log n) for each update
- bravura 18y agoThe more I think about your solution, the more correct and elegant it seems. Cheers!
- nkurz 18y agoI don't think I'm quite understanding your algorithm. When you say "choose left or right", do you mean to choose randomly between the branches with probability equal to the ratio of the weights of the trees? So that each sample requires log(n) random numbers before you reach a leaf? Or do you mean something else?
- bravura 18y agoYou know the sum of the weights. Sample a random number between 0 and sum. Then, use this value to guide your search in the tree. For example, if the left branch has weight 30 and the right branch has weight 50, the total weight is 80. If I pick 40, then I am going down the right branch. At the next child, if the left branch has weight 12 and the right branch has weight 38, the left branch spans 30-42 and the right branch spans 42-80. So you follow the left branch, because you want 40.
- praptak 18y agoBasically, yes - branches are chosen with probabilities proportional to their weights, but you can achieve that with just one random float. Just pick a random x from [0, sum of weights in the tree], then find a node n, such that sum of weights S to the left of n is no more than x and S+weight(n)>=x.
- deleted 18y ago[deleted]