Data Structures, Algorithms, & Applications in Java
Chapter 15, Exercise 12
We provide both a recursive and a nonrecursive solution. First, here is the
recursive solution.
The private recursive method spends O(1) at
any level of the tree that is to be split. So its complexity is
O(h), where
h is the tree height.
public class BinarySearchTreeWithRecursiveSplit extends BinarySearchTree
{
/** split the binary search tree around the key theKey
* all elements > theKey end up in greaterThan
* all elements < theKey end up in lessThan
* return the element (if any) with key theKey */
private static BinaryTreeNode smallTreeRoot, // root of tree with
// elements smaller than theKey
bigTreeRoot;
private static Object splitElement;
private static Comparable splitKey;
public Object split(Comparable theKey, BinarySearchTree lessThan,
BinarySearchTree greaterThan)
{
splitElement = null;
splitKey = theKey;
split(root); // do the split recursively;
lessThan.root = smallTreeRoot;
greaterThan.root = bigTreeRoot;
return splitElement;
}
/** split the binary tree whose root is theRoot */
private static void split(BinaryTreeNode theRoot)
{
if (theRoot == null)
{// split an empty tree
smallTreeRoot = null;
bigTreeRoot = null;
return;
}
// split a non empty tree
if (splitKey.compareTo(((Data) theRoot.element).key) < 0)
{// root, its right subtree and part of its left subtree are in big tree
// part of the left subtree is the small tree
split(theRoot.leftChild);
theRoot.leftChild = bigTreeRoot;
bigTreeRoot = theRoot;
return;
}
if (splitKey.compareTo(((Data) theRoot.element).key) > 0)
{// root, its left subtree and part of its right subtree are in
// the small tree
// part of the right subtree is the big tree
split(theRoot.rightChild);
theRoot.rightChild = smallTreeRoot;
smallTreeRoot = theRoot;
return;
}
// splitKey equals key in root
splitElement = theRoot.element;
smallTreeRoot = theRoot.leftChild;
bigTreeRoot = theRoot.rightChild;
return;
}
// test the split method
public static void main(String [] args)
{
BinarySearchTreeWithRecursiveSplit y =
new BinarySearchTreeWithRecursiveSplit();
int [] splitKey = {1, 2, 6, 12, 15, 18, 20, 30};
for (int i = 0; i < splitKey.length; i++)
{
// insert a few elements
y.put(new Integer(2), new Character('a'));
y.put(new Integer(18), new Character('h'));
y.put(new Integer(10), new Character('e'));
y.put(new Integer(6), new Character('c'));
y.put(new Integer(14), new Character('g'));
y.put(new Integer(12), new Character('f'));
y.put(new Integer(4), new Character('b'));
y.put(new Integer(20), new Character('i'));
y.put(new Integer(8), new Character('d'));
System.out.println("Elements in ascending order are");
y.ascend();
System.out.println();
BinarySearchTree small = new BinarySearchTree();
BinarySearchTree large = new BinarySearchTree();
System.out.println("The split key is " + splitKey[i]);
System.out.println("The split element is " +
y.split(new Integer(splitKey[i]), small, large));
System.out.println("The smaller elements are");
small.ascend();
System.out.println();
System.out.println("The larger elements are");
large.ascend();
System.out.println();
System.out.println();
}
}
}
A nonrecursive solution is just as easy to obtain.
The nonrecursive version is expected to run faster (by a constant factor),
because this version uses a while loop in place of
recursive method invocations.
In the nonrecursive solution that is developed below, we follow
a downward path from the root. As we move down, entire subtrees are moved
into one or the other of the trees we are to create.
We start by initializing the binary search trees lessThan
and greaterThan to consist of a single node which is the
tree root. This node contains no element and will eventually be removed from the
tree. This node serves the same purpose as does a head node in a chain, that is
it eliminates the case when the tree has no nodes. Consequently, the remaining
code is simplified.
We use the variables lt and rt
to point to the lowest nodes, encountered so far, in the trees
lessThan
and greaterThan. These variables are initialized
to the roots of these trees.
The variable currentNode is used to follow
a path from this.root to the node (if any)
that contains an element with key theKey.
As we follow this path, we will bypass subtrees which contain solely
elements that are greater than theKey
as well as subtrees which contain solely elements
that are less than theKey.
Subtrees in the first category may be attached as the
left subtree of gt and those in the
second category may be attached as the
right subtree of lt. When a
subtree is attached to gt or lt,
the variable
gt or lt is updated to become
the root of the attached subtree.
The code is given below. In each iteration of the while
loop, currentNode moves down the tree
this by one level. Further, the complexity
of each iteration
of this loop is O(1). Therefore, the
overall complexity of the split method is O(h).
public class BinarySearchTreeWithSplit extends BinarySearchTree
{
/** split the binary search tree around the key theKey
* all elements > theKey end up in greaterThan
* all elements < theKey end up in lessThan
* @return the element (if any) with key theKey */
public Object split(Comparable theKey, BinarySearchTree lessThan,
BinarySearchTree greaterThan)
{
// initialize lessThan and greaterThan to have just a root
// node which will later be removed
lessThan.root = new BinaryTreeNode();
greaterThan.root = new BinaryTreeNode();
BinaryTreeNode lt = lessThan.root; // lowest node in lessThan
BinaryTreeNode gt = greaterThan.root; // lowest node in greaterThan
BinaryTreeNode currentNode = root; // current node in this
root = null; // tree will be empty following the split
// search for theKey and construct lessThan and greaterThan
// during the search
while (currentNode != null)
if (theKey.compareTo(((Data) currentNode.element).key) > 0)
{// attach currentNode and its left subtree to lt as the right
// subtree and move into the right subtree of currentNode
lt.rightChild = currentNode;
lt = currentNode;
currentNode = currentNode.rightChild;
}
else
if (theKey.compareTo(((Data) currentNode.element).key) < 0)
{// attach currentNode and its right subtree to gt as the left
// subtree and move into the left subtree of currentNode
gt.leftChild = currentNode;
gt = currentNode;
currentNode = currentNode.leftChild;
}
else
{// found a match
// take care of left and right subtrees of currentNode
lt.rightChild = currentNode.leftChild;
gt.leftChild = currentNode.rightChild;
// eliminate fictitious root nodes
lessThan.root = lessThan.root.rightChild;
greaterThan.root = greaterThan.root.leftChild;
return currentNode.element;
}
// no matching element
// set null pointers in lt and gt
lt.rightChild = null;
gt.leftChild = null;
// eliminate fictitious root nodes
lessThan.root = lessThan.root.rightChild;
greaterThan.root = greaterThan.root.leftChild;
return null;
}
}