Fibonacci BSTs: A new balancing method for binary search trees

This paper presents a new method to balance binary search trees, which has the following properties. (i) The only information stored for the balance is the size of every subtree. (ii) Inserting or deleting an element can be done in the most traditional way: first, the element is recursively inserted (deleted) in (from) the appropriate subtree; afterwards, a single or double rotation takes place if necessary. (iii) Checking whether or not those rotations are required is computable in constant time per visited node. (iv) The worst-case height of these trees is never worse than approximately 1.44042log2n, where n is the number of elements.