I was trying to understand the dsw algorithm for balancing a binary search tree in-place using this virgina tech page.
The wikipedia page and vt page are more or less similar. I am having a hard time trying to understand the underlying logic and also the functioning of the vine-to-tree method.
Correct me if am wrong.I am going by the vt page.
Initially in the vine-to-tree method , n = 9 , M=7
, so we make n - M = 2 rotations.( They just say to make 2 rotations , but are actually making rotations on alternate 2 nodes ).
The tricky part around which I am not able to wrap my head around:
While ( M > 1 )
M = M/2;
Make M rotations starting from the top of the backbone;
Since M is initially 7 , we would make (7/2) 3 rotations first time in the loop , and (3/2) 1 more rotation in the second iteration of the loop. However from the pictures below , the tree got balanced after just 2 rotations. Is some end condition missing in the page. Also nowhere is it mentioned to balance only alternate nodes , but they seem to be doing that.