Rebalancing Height Balanced Trees
Luccio, Linda Pagli · IEEE Transactions on Computers · 1978
A new balancing technique for binary search trees is presented, based on the repositioning of k + 1 nodes (k-rotation) Some properties of k-rotation are shown, and bounds to k are derived. The performance of such a technique is discussed on the basis of the length of node search and the frequency of tree rebalancing.