1

I don't think that it is possible to balance a tree in logarithmic time: An algorithm has to determine somehow, when it is finished In this case, establishing that the tree is balanced is necessary This operation alone is $\mathcal O(n)$ (count the height of left/right subtree) Therefore, $\mathcal O(n)$ will be a lower bound for your algorithm and there ...


1

Do an inorder traversal of the BST...and store it in an array the array will be sorted. next construct a balanced binary search tree from this array. 1) Get the Middle of the array and make it root. 2) Recursively do same for left half and right half. a) Get the middle of left half and make it left child of the root created in step 1. b) ...


1

This was first solved by Jacob and Brodal in 2002; there is a recent arXiv submission of that work, "Dynamic Planar Convex Hull".


Only top voted, non community-wiki answers of a minimum length are eligible