Weight-Balanced Trees

Tobias Nipkow 🌐 and Stefan Dirix

March 13, 2018

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

Session Weight_Balanced_Trees