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():

LeftRotate() RightRotate()

And then, the createRightVine():


Then, count the nodes:


At last, balance the right vine:


Hope it helps.



Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s