Weight-balanced trees (WB-trees) were the subject of a 1992 paper by Stephen Adams [&&& ref]. The details of the balancing strategy are not important here; what matters is that these are ordered binary trees. FSet’s implementation of them is heterogeneous, in the sense that the leaves of the tree, instead of holding a single element or key/value pair each, are vectors holding several of these. The length of these vectors is bounded by a constant. The result is that the lowest two or three levels of the tree are gathered into these vectors, saving the space that would otherwise be taken by their tree nodes, with little or no impact on time performance.
FSet has WB-tree implementations of sets, maps, bags, and seqs, named wb-set, wb-map,
wb-bag, and wb-seq respectively. Point updates — inserting an element or pair,
removing one, updating the value associated with a map key, etc. — take O(log n) time. On
seqs, subsequence and concatenation also take O(log n) time. Operatiions that combine two trees
in some way — union, intersection, etc. — take O(n) time in general,
though under certain specific circumstances this can be reduced to O(log n).
For sets, maps, and bags — the setlike types — FSet explicitly provides for the case where two elements or keys are incomparable, meaning that they’re not equal, but the comparison function does not place them in an order. (This situation arises rarely, but it does occur, so FSet provides for it.) As long as the sets of incomparable values remain small, the performance impact is minor; though if they were to grow unboundedly, operations that normally take logarithmic time would take linear time, and those that normally take linear time would take quadratic time. The time complexities given in this book assume that these sets remain of bounded size.