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

CreateRightVine()

Then, count the nodes:

countNodes

At last, balance the right vine:

leftBalanceVine()

Hope it helps.

🙂

Advertisements

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 )

Google photo

You are commenting using your Google 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