1
$\begingroup$

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.

Improve this question
$\endgroup$
  • $\begingroup$ Tree is not (left) balanced after two iterations as should be. Using page 8 picture from pdf: you start at node 5, the right child is 10, but after making rotation the right child (from current node perspective) is 15, so it may seem alternating looking at vine, but looking at it step by step it is consecutive. It is in compress method at wikipedia. I do not know if this answers your doubts, but the question itself should be self contained, including pseudocode and image if you reffer to it. $\endgroup$ – Evil Jul 11 '17 at 1:07
  • $\begingroup$ Yeah .. the picture itself was self-contained. My bad. The picture c has those 3 rotations and picture d has 1 rotation. $\endgroup$ – Rpant Jul 11 '17 at 16:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.