Perfect Binary Tree : DSW and RB balanced trees

Question

I know we can preprocess and turn any binary search tree into a perfect binary tree using DSW algorithm or red black balanced trees.

How do these two methods differ time-complexity wise?

Can you provide some examples/applications for each that shows the benefit of using one method instead of the other.

Answer 1

DSW is static algorithm - you use it once and you expect the tree never to change. It takes O(N) time to make a tree perfectly balanced and then you may use it but are expected not to modify it. You can still do that, but the property of being perfectly balanced will be lost. The more modifying operations you do the worse the tree will perform.

Red-black tree is a dynamic data structure. It performs its basic operations in O(log(N)), but of course will not perform as good as a perfectly balanced tree. What is most important is Red-Black trees may be modified on the flied and will still require O(log(N)) for their operations.

So the two approaches differ in their use-case. Hope this helps.

Answer 2

DSW is useful when you want to create an entire BST (unbalanced) and then perform a large number of lookups (on the post-balanced BST). A RB Tree is useful when you have adds/removes/look-ups all happening interweaved.

The RB tree is mostly balance but the DSW is a complete binary tree (except maybe the last level).

Both offer O(log n) but DSW is a one time operation that can be amortized.