# AVL tree partition

The statement sais the following

Design a function to partition an AVL tree such that, given an AVL tree and a key $x$, it returns two AVL trees, one containing the keys lower or equal than $x$, and the other containing the remaining keys. The complexity must be better than $\mathcal{O}(n)$ (being $n$ the cardinality of the tree).

My attempt is the following recursive algorithm (in pseudo code, so notation abuse is probable).

split(T x, Node root, Node link, Node lower){ if(root.key <= x){ if(lower.isEmpty()) lower=BinaryTree(root.left,root,null); else link.right = BinaryTree(root.left,root,null); link = root; if (root.key< x) split(x,root.right.root,link,lower); } else split(x,root.left.root,link,lower); }

if I am not mistaken, the algorithm returns a binary search tree (but possibly not balanced) whose keys are the ones in the original tree lower of equal than $x$. An analogous one can be done to build the other tree.

So, the question is how to balance both trees without icreasing the current $\mathcal{O}(\log n)$ complexity.

## 2 Answers

The strategy was wrong. Its better to distinguish cases depending on $x>\text{root}$ or $x\leq \text{root}$. Building the "higher tree" in the first case and the "lower tree" otherwise. For details about balancing take a look here (same question in a more specific stack exchange forum).

An alternate but easy solution is to search for key x and create two sorted lists $S$ and $L$ where $S$ contains all elements les than $x$ and vice-versa for $L$, which can be done in linear time.

Now create a perfect binary search tree on this. If the elements are already sorted, this can be done in linear time. Every perfect binary search tree is a valid AVL tree. Viola :D

• As you say, creating the sorted lists will take linear time, and we want to make an algorithm which is strictly faster. – Álvaro G. Tenorio Sep 2 '18 at 10:27
• It is in linear time. How do expect it to be faster than that? – Vk1 Sep 3 '18 at 7:22
• As you can see here, cs.stackexchange.com/questions/80436/avl-tree-partition it can be done in $\mathcal{O}(\log^2)$ – Álvaro G. Tenorio Oct 21 '18 at 17:20