# 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.

• "better than O(n)" -- that does not make any sense. I assume they mean $o(n)$.
– Raphael
Aug 27 '17 at 7:51

Basic Idea: If the root of the tree is equal to $x$ then we just split the tree into two parts $root.left$ and $root.right$, and add $x$ to the $root.left$. This case is trivial and takes $O(\log{n})$ time.
Initialize $T_l = T_\emptyset$ (empty tree). We start from root and move in the leftmost direction down the left subtree until we find an element $y$ less than $x$ (see the figure below). At this point we detach $y$ from $w$ and add $y$ to its left subtree $T_1$ (its elements are less than $x$), but make $T_2$ $w$'s left child. Since the initial subtree is AVL there is a chance $|height(T_2) - height(T_3)| = 2$ in which case we left-rotate at $w$ to balance the new subtree with root at $w$. This updates the height of the node $w$ and we ascend along the leftmost path up to the root by updating nodes' height and rotating if necessary to balance the subtrees (by single left rotations).