# Split in AVL tree with complexity $O(\log n)$

Can the split operation be implemented for AVL trees with complexity $O(\log n)$? I'm interested in links to articles or any specific information about this subject.

The split operation divides the AVL tree into two derived AVL trees, based on key. One of the derived trees should contain all the vertices in which all keys less than the original key, and the second the rest.

I know this can be done in $O(\log^2 n)$ time. Here's a link to implementation with complexity $O(\log^2 n)$: https://code.google.com/p/self-balancing-avl-tree/

I also know how to merge two AVL trees, such that the keys of one tree are all smaller than the keys of the other, in $O(\log n)$ time. Here's an implementation with complexity $O(\log n)$:

def Merge(l, r) {
if (!l || !r)
return l ? l : r;
if (l->h <= r->h)
r->l = Merge(l, r->l), Rebalance(r);
else
l->r = Merge(l->r, r), Rebalance(l);
}


Yes, this is possible.

One of the key insights is that the merge function you mention is, with more careful accounting, $O(h_1 - h_2)$, where $h_1$ is the height of the taller tree and $h_2$ is the height of the shorter tree. As such, merging a list of trees that have descending or ascending heights costs only $O(h_{\max} - h_{\min})$, since the sum telescopes.

Let us define a function split(T,v) that takes in a tree, T and a value to split at, v. Suppose that each node of the tree stores its left child and right child in addition to the value at that node. Use the following algorithm:

1. First we check to see if the input tree is simply a leaf or not.

2. If T is not a leaf, compare the value of its root node, v' with v.

3. If v' < v then recursively call split on the left subtree. Store the values of the recursive call as L' (returned left tree), R' (returned right tree), and r (option type indicated if the value v was found or not). Construct the new right tree, newR = Node(R',v',R), and return (L',r,newR).

4. Else if v' > v then recursively call split on the right subtree. Store the values of the recursive call as L' (returned left tree), R' (returned right tree), and r (option type indicated if the value v was found or not). Construct the new left tree, newL = Node(L',v',L), and return (newL,r,R').

5. Else if v' = v, return L, SOME(v), R.

6. If T is a leaf, we must have reached the root of the tree without finding the input value v to split at. Return that you couldn't find the leaf by passing back NONE.

Why is this logarithmic? Well, you only ever traverse one root-to-leaf path of the tree, at most. We can easily reconstruct nodes in constant time since we're just re-assigning $O(\log n)$ references (in an imperative language) or reassigning $O(\log n)$ values that take a constant time to generate (in a functional language).

Here's the corresponding code for the algorithm. It's written in SML, but I'd be willing to clarify what anything means in the comments.

fun split(T,v) = case T of Leaf => (Leaf, NONE, Leaf) | Node(L,v,R) => case compare(v, v') of LESS => let val (L',r,R') = split(L,k) in (L',r,Node(R',r,R)) end | GREATER => let val (L',r,R') = split(R,k) in (Node(L',v',L),r,R') end | EQUAL => (L, SOME(v), R)

See this document for more details. It provides a more thorough explanation of the above.

• This does not address the AVL balance conditions. Jun 7 '15 at 6:46