Split a binary tree

I am trying to split a binary search tree开发者_开发技巧 at the root in Java. I have no idea how to go about this. The recursive call is what is mostly confusing me. Below is the pseudocode that I was given. When x is greater than T (the tree to be split), am I going to call split(R.key, R.right, L, R)? Am I on the right track? This is the only function in the project that is confusing me. Thanks in advance.

 void split( int x, bst T, bst L, bst R) /* assuming x is not in T */
 {
    if T is null, make L and R null
    else if x < T.key
      set R = T /* all keys at the root and in right subtree are greater than x */
      recursively split T's left subtree into L and R’s left subtree
         /* some keys in T's left subtree are greater than x, other may be less than x */

    else /* x is greater than T.key */
      set L = T
      recursively split T's right subtree into L's right subtree and R
 }

It is important that you must have a binary ordered tree, such that Left < Root < Right for every subtree. Also, there is no node in the left subtree such that node > Root, and no node in the right subtree such that node < Root. Balancing (that all subtrees are same depth +- 1) is not needed.

It is like a dicomotical search; if the value to split by is greater than your current root, you are sure that it is greater than all nodes in the left subtree (because of the previous restriction). So, in order to search which of the nodes of the tree are bigger, you only need to check the nodes to the right. Likewise, if the value to split by is less than the value of root, it is also less than the values of all the nodes of the right subtree, and you must check more finely in the left tree.

In order to see it clearly, I suggest you to draw this tree (no spacing here)

8

4 12

3 6 10 14

1 2 5 7 9 11 13 15

, set several sample split values, and mark which nodes would remain in the new tree.