3
$\begingroup$

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.

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

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

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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