saba_tavdgiridze's blog

By saba_tavdgiridze, 6 years ago,

DSW algorithm is used to balance binary tree.There are two phases:
2)transform backbone into a balanced tree;
There are Pseudocodes for both phase :
1)

createBeckbone(root,n)
tmp = root;
while( tmp!=0 )
if tmp has a left child
set tmp to the child that just became parent;
else set tmp to its right child;


2)

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.

• -1