|
|
|---|
|
|
|
|---|
Implementation details of sets.
Here we describe the internal representation of sets. Users of the library should not depend on these details, opting instead to use the "primitive" operators abstractly.
Sets are represented internally as treaps (= "tree" + "heap"). Treaps are binary search trees with an additional max heap constraint (see bst-p and heapp, respectively). Crucially, the max heap property is maintained with respect to a different order than that which is used for the binary search tree property.
The binary search tree property uses the bst< order, which is just a wrapper around <<. The binary search tree property is what delivers logarithmic average-case complexity of our basic operations.
The max heap property uses the new heap< total order. This ensures that the tree has a canonical structure and that the tree is practically balanced. Treaps are only expected to be balanced in practice if the heap order and the binary search tree order are largely uncorrelated. That is, the heap order appears "random" with respect to the binary search tree order. To accomplish this, the heap< order is based on a non-cryptographic hash of its arguments.