0
$\begingroup$

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?

$\endgroup$
0

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.