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.

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

1 Answer 1


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)

enter image description here

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$).

enter image description here

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

    node = root
    go to left until node.data <= x
    if no node with node.data <= x found 
      return Tl, Tr
      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

    Tl = Join(Tl, T_temp)

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)$.

  • $\begingroup$ 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? $\endgroup$ Aug 25, 2017 at 21:30
  • $\begingroup$ @HendrikJan updated. $\endgroup$
    – fade2black
    Aug 27, 2017 at 2:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.