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

### Case 1 (trivial, root.data = x) ### Case 2 (root.data > x)

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).
Then we again repeat these steps until we find $x$ (which is handled like in the case 1) or there is no element less than or equal to $x$, and so we stop. At each step we join new $T_l$ and new subtree whose elements is less than $x$. (Note: computing a length of a node takes $O(\log{n})$ time$). ### Case 3 (root.data < x) In this case we should add$root.data$to$root.left$, join$T_l$and$root.left$($T_l = Join(T_l, root.left)$) and set$root = root.right$. If$root.data$is still less than$x$then repeat these steps above again until$root.data \geq x$.  Tl = {} Tr = T #original AVL tree while (root.data < x) # O(\log{n}) add root.data to root.left # O(log(n)) T_l = Join(Tl, root.left) # O(log(n)) root = root.right end loop node = root go to left until node.data <= x if no node with node.data <= x found return Tl, Tr else T_temp = add node.data to node.left node.parent.left = node.right compute height(node.right) and height(node.parent.right) left-rotate at node.parent if these heights differ by two backtrack to the root by updating heights of nodes and left-rotating if necessary end Tl = Join(Tl, T_temp) end  Analysis: The outer loop runs at most$\log{n}$times since at each step we the length of the leftmost path decreases by$1$. Computing heights of two nodes is$O(\log{n})$. Joining$T_l$and$T_{temp}$also$O(\log{n})$. Thus we have$O(\log^2{n})$running time which is better than$O(n)\$.

• I do not immediately see why, after cutting a large subtree, the remaining tree can be re-balanced in a log-number of steps. Of course the height of the tree is logarithmic in the (total) number of nodes, but how many rotations do we need say at the root to get a left-right balance? Aug 25 '17 at 21:30
• @HendrikJan updated. Aug 27 '17 at 2:12