1
$\begingroup$

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
$\endgroup$

2 Answers 2

0
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Extremely interesting thank you for your help! $\endgroup$
    – Thornside
    May 15, 2022 at 18:38
0
$\begingroup$

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)$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.