This theory provides a verified implementation of weight-balanced trees following the work of Hirai and Yamamoto who proved that all parameters in a certain range are valid, i.e. guarantee that insertion and deletion preserve weight-balance. Instead of a general theorem we provide parameterized proofs of preservation of the invariant that work for many (all?) valid parameters.
- HIRAI, Y., & YAMAMOTO, K. (2011). Balancing weight-balanced trees. Journal of Functional Programming, 21(3), 287–307. https://doi.org/10.1017/s0956796811000104