You can make a binary tree where each node counts the total (recursive) number of children. Updating these counts is log(N). To insert a node, generate a rando

You can make a binary tree where each node counts the total (recursive) number of children. Updating these counts is log(N). To insert a node, generate a random bit string: descend the tree and when the counts are equal then take the branch corresponding to that position in the bit string. When the counts are unequal, take the branch with the smallest count. To remove a node just remove it from the tree and update the counts up along its path to the root. This assumes that articles are added as often as they are removed. To sample, just generate another random bit string and traverse the tree according to it. But I agree with the sibling comment that the current non-uniform algorithm is fine for a cute “Random article” button.