Suppose we are given a balanced binary search tree $T$, AVL tree, now we want split $T$ at a arbitrary node. Can it be done in $O(\log n)$?

First i read following links:

  1. Split in AVL tree with complexity $O(\log n)$

  2. Trying to understand a way to split an AVL tree in O(log n)

Now i think, because of height of our tree $T$ is $O(\log n)$ then after splitting at a arbitrary node, it is sufficient to re-balance our tree $T$ start from one of leaf node, in this manner we do rotation and because of each level want constant number of rotation to be balanced, after $O(\log n)$ will be in root of $T$ and our tree $T$ is balanced. Are my argument is true?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.