# Is this probability distribution data structure already discovered?

Problem formulation

I have implemented an interesting probability distribution data structure: having $n$ elements $a_1, a_2, \dots, a_n$ in the data structure with respective positive weights $w_1, w_2, \dots, w_n > 0$, upon request each $a_i$ may be returned with probability $$\frac{w_i}{\sum_{j = 1}^n w_j}.$$

A Java implementation of my data structure can be obtained here, yet I will specify the algorithm here textually:

There are two types of nodes, relay nodes and leaf nodes. The actual elements with their actual weights are stored in leaf nodes. What comes to relay nodes, we allow only those that have both children (the tree is binary). However, each relay node know how many leaves is there in the subtree starting from that very relay node; also each relay node knows the sum of weights of all its leaves.

Whenever adding a new element, we start traversing the tree from its root, and until we reach a leaf node, we choose that relay node, whose node count is smallest; this way it maintains a logarithmic height.

What comes to the removal of an element, the data structure maintains a hashtable mapping each element to its leaf node. So, first we get the leaf node, remove it, after which, we replace the parent relay node with the sibling leaf.

Whenever sampling an element, we start from root, and choose an appropriate relay node until we reach the appropriate leaf node, whose element we return.

All three basic operations seem to run in worst-case $\mathcal{O}(\log n)$, and my benchmarking supports the observation.

A simple visualization:

Question

Is this data structure already discovered? If yes, could you tell me the name of the paper that discusses it?

• These types of data structures where you store additional info on nodes are generally called 'Augmented Data Structures'.They don't have a solid form , but I can say that storing the number of child nodes and their values are being used in many cases. – atayenel Jun 16 '16 at 7:35
• I have seen this factor in the Rational Bézier Curves. This augmented tree reminds me of rank tree / interval tree mixed with scapegoat tree. I know Java, but haven't read your source, I cannot imagine from pure description how it will react for ordered list. – Evil Jun 17 '16 at 17:38
• @EvilJS I had to relax the order criterion: the actual internal order will not match, say, insertion order. – coderodde Jun 17 '16 at 17:40
• Sampling from finite sets/distributions is a well-studied problem; I recommend you check out Knuth's TAOCP. IIRC, he has an algorithm that samples faster than logarithmic time. – Raphael Jun 17 '16 at 17:48
• @Raphael Do you have any recollection of how efficient are adding/removing elements to/from the distribution? – coderodde Jun 17 '16 at 17:54

For something that looks similar, but is more static (no insertions or deletions, just a given number of elements with frequency counts or weights), a very well-known problem is to try to minimize the weighted sum of node depths in the tree. These are known as Huffman Trees, used to generate Huffman Codes for compressing data. The tree can be computed in $\Theta(n \lg n)$ time, or $\Theta(n)$ time if you have the weights in sorted order.