# Given an AVL tree of size n, is it possible to split the tree into 'k' equal sized search-trees in less than O(n) time?

The question first asked to split the AVL tree of size n into k equal sized search trees(k devides n) in O(n) time, and I solved this by moving all the AVL tree values into an array, and from there splitting the array into k different parts and constructing each part to be an AVL tree. In total this takes O(n) time. However now the question asks if it is possible to improve the O(n) time if we are allowed to add another field into the tree. If it is, it asks for which values of k can you get this improvement for, and what the new time complexity be. If it isn't, explain why. The way the question is written makes it look like there likely should be a way to do this, and explaining why it is impossible seems really difficult. I have tried adding a field that stores the size of the subtree in every cell, but I still couldn't find a way of solving this. If this is not solveable, I would like an explaination that really shows why it is impossible. Also incase it wasn't clear, I just need an algorithm, not actual programming.

• Do you need just any search-tree (even unbalanced) or all the sub-trees have to be AVL as well? Commented May 28 at 13:45
• Honestly the question was not clear about that, Im assuming it means AVL trees. If you notice it is possible by splitting to search trees that aren't AVL trees, then I would like to see that. Preferably though it should be AVL trees Commented May 28 at 13:49
• Instead of "less than $\mathrm O(n)$" I suggest using $o(n)$ if you mean "less by a factor which tends to infinity as $n$ goes to infinity" Commented May 28 at 14:55

Convert your AVL tree to an order statistics tree . Now, you can search for the $$n/k$$ element, the $$2n/k$$, and so on in $$O(\log n)$$ time each or $$O(k\log n)$$ in total. After each search, you can split the AVL tree with respect to each element you searched. A split also cost $$O(\log n)$$, so in total you still get $$O(k \log n)$$
• I think I misinterpreted $k$. I will edit my answer for this. Commented May 28 at 15:56
If you are given an AVL-tree, or any other search tree then I would say that it is not possible to split it into $$k > 1$$ equal parts without counting which vertices are maximums for each new tree. Such counting requires $$\Omega(n)$$ time. (And the case $$k = 1$$ trivially takes $$\mathrm O(1)$$ time. :-)
On the other side if you build a tree on your own, it is possible to add extra information to make such operation significantly faster. Namely if each vertex has order of its subtree, then you can find $$i$$-th key in $$\mathrm O(\log n)$$ time for every $$i = \frac nk, \frac {2n}k, \ldots, \frac {(k - 1)n}k$$, i. e., $$O(k\log n)$$ in total. Having knowledge about these vertices it is possible to make $$k - 1$$ split operations after every such vertex in $$\mathrm O(k\log n)$$ total time. Such fast split operation exists for AVL-trees, red-black trees, splay trees, Cartesian trees and maybe some other. Maintaining information about subtree order in every vertex is pretty easy and takes $$\mathrm O(1)$$ extra time for every rotation.
Note that approximating $$i$$-th key relying on properties of AVL-tree is a bad idea in the worst case. If the tree has height $$h$$ then its subtree can have order at least $$2^h - 1$$ and at most $$\frac{\varphi^{h + 2} - \varphi^{-h - 2}}{\sqrt 5}$$ for $$\varphi = \frac{\sqrt 5 + 1}2$$. So the relation between left and right subtree orderes can be exponential.