What is the time complexity of adding to a BST if we are to maintain balance

Question

If we have a BST but want to keep it balanced, how much more expensive does adding an element to it become? Clearly adding an element (without maintaining balance) is of time complexity O(log(n)), as we traverse the tree down to the point where we should add the element, but if we want to maintain a balanced tree such that our worse case search time remains O(log(n)), how much more expensive are the operations of

1. Checking if our tree is balanced after we have added an element
2. Balancing the tree through left or right rotations if it is now unbalanced. Thanks

Answer 1

Checking if a tree is balanced is clearly in time linear in the size of the tree.

However, balancing when inserting or deleting nodes can indeed be done in $\mathcal{O}(\log n)$, using AVL trees or red-black trees for example.

Answer 2

The cost of inserting into a height-balanced binary search tree (i.e. an AVL tree) is $O(\log n)$. You would first augment the BST’s data structure so that a height value is stored for each node.

For an insert operation, finding the insertion point takes $O(\log n)$ time. Then, rebalancing the tree requires retracing the path upwards from the insertion point towards the root, which takes $O(\log n)$ time. More specifically, as you go upwards, the height values are updated and you check for height imbalance, performing rotations if necessary. Each rotation takes $O(1)$ time. So the total cost of insertion - of both finding the insertion point and rebalancing - is $O(\log n)$.