DSW algorithm (balancing binary search tree)

Well, Day–Stout–Warren (DSW) algorithm is used to balance a binary search tree. Here is the wiki link. The idea of DSW is, first of all, turning an unbalanced binary search tree to a single vine (either right or left) and use left rotation or right rotation to make it balanced again.

First of all, here are the leftRotate() and rightRotate():

And then, the createRightVine():

Then, count the nodes:

At last, balance the right vine:

Hope it helps.

🙂

Advertisements