saba_tavdgiridze's blog

By saba_tavdgiridze, 6 years ago, In English

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 :

   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;


    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.

  • Vote: I like it
  • -1
  • Vote: I do not like it