Rebalancing an arbitrary BST?
The DSW algorithm can solve this is O(n) time. The algorithm goes as follows:
1] Using right-rotation operations, turn the tree into a linked list
(a.k.a. backbone or vine)
2] Rotate every second node of the backbone about its parent to turn
the backbone into a perfectly balanced BST.
Reference
"Balanced as possible" = complete (or full) binary tree1. You cannot get more balanced that it.
The solution is simple - build an "empty" complete binary tree, and iterate the new tree and the input tree (simultaneously) in inorder-traversal to fill the complete tree.
When you are done, you have the most balanced tree you can get, and time complexity of this approach is O(n)
.
EDIT:
This should be done following these steps:
- Build a dummy complete tree with
n
nodes. All the values to each node will be initialized to some garbage value. - Create two iterators: (1)
originalIter
for the original tree, (2)newIter
for the new (initialized with garbage) tree. Both iterators will return elements in in-order traversal. Do the following to fill the tree with the values from the original:
while (originalIter.hasNext()): newIter.next().value = originalIter.next().value
(1) (From Wikipedia): A complete binary tree is a binary tree in which every level, except possibly the last, is completely filled, and all nodes are as far left as possible
You might want to look into the Day-Stout-Warren algorithm, which is an O(n)-time, O(1)-space algorithm for reshaping an arbitrary binary search tree into a complete binary tree. Intuitively, the algorithm works as follows:
- Using tree rotations, convert the tree into a degenerate linked list.
- By applying selective rotations to the linked list, convert the list back into a completely balanced tree.
The beauty of this algorithm is that it runs in linear time and requires only constant memory overhead; in fact, it just reshapes the underlying tree, rather than creating a new tree and copying over the old data. It is also relatively simple to code up.
Hope this helps!