DSW algorithm is used to balance binary tree.There are two phases:
1)Create backbone(linked list-like tree);
2)transform backbone into a balanced tree;
There are Pseudocodes for both phase :
createBeckbone(root,n) tmp = root; while( tmp!=0 ) if tmp has a left child rotate this child about tmp; set tmp to the child that just became parent; else set tmp to its right child;
createPerfectTree(n) m=2^( floor(lg(n+1)))-1; make n-m rotations starting from the top of backbone; while (m > 1) m= m/2; make m rotations starting from the top of backbone;
I understood first phase,but I can't figure how second algorithm can guarantee perfectly balanced tree.If you know this algorithm please help.