Dr. Dobb's Journal October 1998
Procedure Rebalance(t : pointer to leaf) {
while (t is not the root)
{
t's weight = t's right child's weight +
t's left child's weight ;
if ( (t's weight > t's sibling's weight+1) &&
(t's weight > t's uncle's weight))
then {
q = parent of parent of t ;
exchange t with t's uncle ;
exchange q's right and left child ;
Update t's ancient parent's weight ;
}
t = t's parent ;
}
}