Complexity of balancing an unbalanced/partially balanced BST?

Question

In an AVL tree, it takes a constant number of single and double rotations every time we rebalance on insertion and deletion since we only have to check the path from point of insertion or deletion to the root.

If we had an unbalanced tree, we would have to check if every possible node is balanced, so it would cost O(n) to rebalance an unbalanced tree. Is this correct?

Answer 1

It does take time O(n) to rebalamce an unbalanced tree, but not for the reason you mentioned. In an AVL tree, insertions and deletions may require Θ(log n) rotations if the tree was maximally imbalanced before the element was inserted. This could potentially require O(n log n) time to rebalance the tree, since you might do O(log n) work per each of the n nodes.

However, using other algorithms, you can rebalance a tree in O(n) time. One simple option is to do an inorder traversal of the tree to get the elements in sorted order, then reconstruct an optimal BST from those elements by recursively building the tree bottom-up. Alternatively, you can use the Day-Stout-Warren algorithm, which balances any tree in O(n) time and O(1) space.

Hope this helps!