Weight-Balanced Trees

Tobias Nipkow 🌐 and Stefan Dirix

March 13, 2018

This is a development version of this entry. It might change over time and is not stable. Please refer to release versions for citations.

Abstract

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.

License

BSD License

Topics

Related publications

  • HIRAI, Y., & YAMAMOTO, K. (2011). Balancing weight-balanced trees. Journal of Functional Programming, 21(3), 287–307. https://doi.org/10.1017/s0956796811000104
  • Wikipedia

Session Weight_Balanced_Trees