Balancing weight-balanced trees
- 27 May 2011
- journal article
- research article
- Published by Cambridge University Press (CUP) in Journal of Functional Programming
- Vol. 21 (3) , 287-307
Abstract
A weight-balanced tree (WBT) is a binary search tree, whose balance is based on the sizes of the subtrees in each node. Although purely functional implementations on a variant WBT algorithm are widely used in functional programming languages, many existing implementations do not maintain balance after deletion in some cases. The difficulty lies in choosing a valid pair of rotation parameters: one for standard balance and the other for choosing single or double rotation. This paper identifies the exact valid range of the rotation parameters for insertion and deletion in the original WBT algorithm where one and only one integer solution exists. Soundness of the range is proved using a proof assistant Coq. Completeness is proved using effective algorithms generating counterexample trees. For two specific parameter pairs, we also proved in Coq that set operations also maintain balance. Since the difference between the original WBT and the variant WBT is small, it is easy to change the existing buggy implementations based on the variant WBT to the certified original WBT with a rational solution.Keywords
This publication has 8 references indexed in Scilit:
- Functional Pearls Efficient sets—a balancing actJournal of Functional Programming, 2008
- Functors for Proofs and Programs2004
- Interactive Theorem Proving and Program Development2004
- A New Method for Balancing Binary Search TreesLecture Notes in Computer Science, 2001
- CSDP, A C library for semidefinite programmingOptimization Methods and Software, 1999
- Purely Functional Data Structures1998
- A dichromatic framework for balanced trees1978
- Binary search trees of bounded balance1972