Beginning Algorithms (2006)

Chapter 10

private Node _f; private Node _h; private Node _i; private Node _k; private Node _l; private Node _m; private Node _p; private Node _root;

private BinarySearchTree _tree;

protected void setUp() throws Exception { super.setUp();

_a = new Node(“a”); _h = new Node(“h”); _k = new Node(“k”); _p = new Node(“p”);

_f = new Node(“f”, null, _h); _m = new Node(“m”, null, _p); _d = new Node(“d”, _a, _f); _l = new Node(“l”, _k, _m); _i = new Node(“i”, _d, _l); _root = _i;

_tree = new BinarySearchTree(NaturalComparator.INSTANCE); _tree.insert(_i.getValue()); _tree.insert(_d.getValue()); _tree.insert(_l.getValue()); _tree.insert(_a.getValue()); _tree.insert(_f.getValue()); _tree.insert(_k.getValue()); _tree.insert(_m.getValue()); _tree.insert(_h.getValue()); _tree.insert(_p.getValue());

}

Having set up your initial state, the next thing you do is ensure that the tree you built looks exactly like the one you’re going to use for comparison.

In testInsert(), you assume there is a method getRoot() on BinarySearchTree that enables you to get at the root node. You then take advantage of the equals() method on Node to check them for structural equality:

public void testInsert() { assertEquals(_root, _tree.getRoot());

}

Now that you have a tree in a known state (and have tested insert() in the process), you test the remaining behavior of the BinarySearchTree class, starting with search().

254

Binary Search Trees

You expect search() to return the node corresponding to a specified value if found; or null if not. Therefore, in testSearch(), you perform a lookup for each of the known values, comparing the resulting node with the appropriate node in your handmade tree. Notice the check to ensure that an unknown value results in null:

public void testSearch() {

assertEquals(_a, _tree.search(_a.getValue())); assertEquals(_d, _tree.search(_d.getValue())); assertEquals(_f, _tree.search(_f.getValue())); assertEquals(_h, _tree.search(_h.getValue())); assertEquals(_i, _tree.search(_i.getValue())); assertEquals(_k, _tree.search(_k.getValue())); assertEquals(_l, _tree.search(_l.getValue())); assertEquals(_m, _tree.search(_m.getValue())); assertEquals(_p, _tree.search(_p.getValue()));

assertNull(_tree.search(“UNKNOWN”));

}

The only method you tested was delete(). As you know, there are a number of different scenarios to test: leaf nodes, nodes with one child, and those with two children.

Starting with the simple deletion of a leaf node, you see what happens when you delete the value H, as shown in Figure 10-8. The method testDeleteLeafNode() first deletes the value from the tree and records the deleted node. You then ensure that a node was actually returned after the call and that the value of the deleted node was indeed H. Finally, the test node structure is modified so that the parent of M — the F — no longer has a larger child, just as you expect the delete algorithm to have done. You can then compare the test node structure with the root of the tree; both should be equal:

public void testDeleteLeafNode() {

Node deleted = _tree.delete(_h.getValue()); assertNotNull(deleted); assertEquals(_h.getValue(), deleted.getValue());

_f.setLarger(null); assertEquals(_root, _tree.getRoot());

}

Next, you deleted a node with one child — the ‘M’, as shown in Figure 10-9. This time, testDeleteNodeWithOneChild() deletes the value ‘M’ from the tree; and, after verifying the return value, you again modify the test node structure so that it resembles the expected structure of the tree. The two are then compared for equality. Note that you have made ‘P’ the larger child of ‘L’, thereby splicing out the ‘M’, just as the tree should have done:

public void testDeleteNodeWithOneChild() { Node deleted = _tree.delete(_m.getValue()); assertNotNull(deleted);

assertEquals(_m.getValue(), deleted.getValue());

_l.setLarger(_p); assertEquals(_root, _tree.getRoot());

}

255

Chapter 10

Lastly, you tried deleting a node with two children — the root node ‘I’ — as shown Figure 10-10 and Figure 10-11. Having deleted the ‘I’ from the tree, testDeleteNodeWithTwoChildren() updates the expected structure as appropriate and compares this to the root of the tree:

public void testDeleteNodeWithTwoChildren() { Node deleted = _tree.delete(_i.getValue()); assertNotNull(deleted);

assertEquals(_i.getValue(), deleted.getValue());

_i.setValue(_k.getValue()); _l.setSmaller(null); assertEquals(_root, _tree.getRoot());

}

Confident that you have the behavior of your tree tested, you implement the binary search tree class itself in the next Try It Out section.

Create the BinarySearchTree class as follows:

package com.wrox.algorithms.bstrees;

import com.wrox.algorithms.sorting.Comparator;

public class BinarySearchTree {

private final Comparator _comparator; private Node _root;

public BinarySearchTree(Comparator comparator) {

assert comparator != null : “comparator can’t be null”; _comparator = comparator;

}

public Node search(Object value) {

assert value != null : “value can’t be null”;

Node node = _root;

while (node != null) {

int cmp = _comparator.compare(value, node.getValue()); if (cmp == 0) {

break;

}

node = cmp < 0 ? node.getSmaller() : node.getLarger();

}

return node;

}

256

Binary Search Trees

public Node insert(Object value) { Node parent = null;

Node node = _root; int cmp = 0;

while (node != null) { parent = node;

cmp = _comparator.compare(value, node.getValue()); node = cmp <= 0 ? node.getSmaller() : node.getLarger();

}

Node inserted = new Node(value); inserted.setParent(parent);

if (parent == null) { _root = inserted;

}else if (cmp < 0) { parent.setSmaller(inserted);

}else { parent.setLarger(inserted);

}

return inserted;

}

public Node delete(Object value) { Node node = search(value);

if (node == null) { return null;

}

Node deleted = node.getSmaller() != null && node.getLarger() != null ? node.successor() : node;

assert deleted != null : “deleted can’t be null”;

Node replacement = deleted.getSmaller() != null ? deleted.getSmaller() : deleted.getLarger();

if (replacement != null) { replacement.setParent(deleted.getParent());

}

if (deleted == _root) { _root = replacement;

}else if (deleted.isSmaller()) { deleted.getParent().setSmaller(replacement);

}else {

deleted.getParent().setLarger(replacement);

}

if (deleted != node) {

Object deletedValue = node.getValue(); node.setValue(deleted.getValue()); deleted.setValue(deletedValue);

}

257

Chapter 10

return deleted;

}

public Node getRoot() { return _root;

}

}

How It Works

The BinarySearchTree class holds a comparator to use for comparing values; the root node, which may be null if the tree is empty; and a method for providing access to the root node that you used in your tests. Notice that you haven’t implemented any interface, nor have you extended any base class. This binary search tree implementation is not really intended for use in its present form (Chapters 12 and 13 will attend to that):

package com.wrox.algorithms.bstrees;

import com.wrox.algorithms.sorting.Comparator;

public class BinarySearchTree {

private final Comparator _comparator; private Node _root;

public BinarySearchTree(Comparator comparator) {

assert comparator != null : “comparator can’t be null”; _comparator = comparator;

}

public Node getRoot() { return _root;

}

...

}

The simplest method you implemented was search(). This method looks for a value in the tree and returns the corresponding node, or null if the value wasn’t found. It starts at the root node and continues until it either finds a match or runs out of nodes. At each pass through the while loop, the search value is compared with the value held in the current node. If the values are equal, you’ve found the node you’re looking for and can exit the loop; otherwise, you follow the smaller or larger link as appropriate:

public Node search(Object value) {

assert value != null : “value can’t be null”;

Node node = _root;

while (node != null) {

int cmp = _comparator.compare(value, node.getValue()); if (cmp == 0) {

break;

}

258

Binary Search Trees

node = cmp < 0 ? node.getSmaller() : node.getLarger();

}

return node;

}

The first half of insert() simply searches through the tree looking for the appropriate leaf node to which the new value will be attached, following the smaller or larger link as appropriate. When the while loop terminates, the variable parent will either be null, in which case the tree was empty and you can set the new node as the root node, or it will hold the parent for the new node. Then, once you have determined the parent for the new node, you set it as either the smaller or larger child as appropriate — the variable cmp still has the result from the last value comparison.

Do you notice anything different in the while loop between the insert() and search() code? In search(), you exit the loop if you find a matching value (cmp == 0). In insert(), however, you treat an equal value as if it was smaller (though you could just as easily have treated it as if it was larger). What do you think would happen if you added the same value twice? You end up with an unbalanced tree.

public Node insert(Object value) { Node parent = null;

Node node = _root; int cmp = 0;

while (node != null) { parent = node;

cmp = _comparator.compare(value, node.getValue()); node = cmp <= 0 ? node.getSmaller() : node.getLarger();

}

Node inserted = new Node(value); inserted.setParent(parent);

if (parent == null) { _root = inserted;

}else if (cmp < 0) { parent.setSmaller(inserted);

}else { parent.setLarger(inserted);

}

return inserted;

}

Last but not least, use delete(). As you can imagine, deleting a value from a binary search tree is rather more complicated than either searching or insertion, as you need to consider a number of different situations. Having said that, it’s actually not too difficult to combine the cases into a fairly straightforward piece of code.

The delete() method starts out with a search to find the node to be removed. If the value isn’t found (node == null), there is clearly nothing to do and you can return immediately. If you do find one, however, there is still a bit of work to be done.

259

Chapter 10

Once you have a node to delete, you need to determine whether the node itself can be removed or if you need to find its successor. Remember that if a node has zero or one child, it can be removed straightaway. If, conversely, a node has both its children, you need to swap it with its successor and remove that node instead.

Having decided which node to actually remove, the next step is to find its replacement. At this point, you know that, given the previous step, the node to be removed will have at most one child, or possibly none. Therefore, you simply get the child (if one exists) and make its parent the same as that of the deleted node.

Having chosen a replacement, you now need to fix up the link from the parent. If the deleted node was the root node, you make the replacement the new root. Otherwise, you set the replacement as the smaller or larger child as appropriate.

Finally, a bit of cleanup. If the node you removed from the tree is not the one you originally found — due to swapping with its successor — you need to also swap the values before returning the deleted node to the caller:

public Node delete(Object value) { Node node = search(value);

if (node == null) { return null;

}

Node deleted = node.getSmaller() != null && node.getLarger() != null ? node.successor() : node;

assert deleted != null : “deleted can’t be null”;

Node replacement = deleted.getSmaller() != null ? deleted.getSmaller() : deleted.getLarger();

if (replacement != null) { replacement.setParent(deleted.getParent());

}

if (deleted == _root) { _root = replacement;

}else if (deleted.isSmaller()) { deleted.getParent().setSmaller(replacement);

}else {

deleted.getParent().setLarger(replacement);

}

if (deleted != node) {

Object deletedValue = node.getValue(); node.setValue(deleted.getValue()); deleted.setValue(deletedValue);

}

return deleted;

}

260

Binary Search Trees

Assessing Binar y Search Tree Performance

Up until now, we’ve only talked about the performance of binary search trees, so in the next Try it Out section, you write some code that actually demonstrates the characteristics of binary search trees. For this you create some tests that measure the number of comparisons performed when inserting data. You can then compare the results of inserting randomly generated data with those of inserting ordered data.

Create the performance test class as follows:

package com.wrox.algorithms.bstrees;

import com.wrox.algorithms.lists.ArrayList; import com.wrox.algorithms.lists.List;

import com.wrox.algorithms.sorting.CallCountingComparator; import com.wrox.algorithms.sorting.NaturalComparator; import junit.framework.TestCase;

public class BinarySearchTreeCallCountingTest extends TestCase { private static final int TEST_SIZE = 1000;

private CallCountingComparator _comparator; private BinarySearchTree _tree;

protected void setUp() throws Exception { super.setUp();

_comparator = new CallCountingComparator(NaturalComparator.INSTANCE); _tree = new BinarySearchTree(_comparator);

}

public void testRandomInsertion() {

for (int i = 0; i < TEST_SIZE; ++i) {

_tree.insert(new Integer((int) (Math.random() * TEST_SIZE)));

}

reportCalls();

}

public void testInOrderInsertion() {

for (int i = 0; i < TEST_SIZE; ++i) { _tree.insert(new Integer(i));

}

reportCalls();

}

public void testPreOrderInsertion() { List list = new ArrayList(TEST_SIZE);

for (int i = 0; i < TEST_SIZE; ++i) { list.add(new Integer(i));

}

261

Chapter 10

preOrderInsert(list, 0, list.size() - 1);

reportCalls();

}

private void preOrderInsert(List list, int lowerIndex, int upperIndex) { if (lowerIndex > upperIndex) {

return;

}

int index = lowerIndex + (upperIndex - lowerIndex) / 2;

_tree.insert(list.get(index)); preOrderInsert(list, lowerIndex, index - 1); preOrderInsert(list, index + 1, upperIndex);

}

private void reportCalls() {

System.out.println(getName() + “: “ + _comparator.getCallCount() + “ calls”);

}

}

How It Works

For convenience, you wrapped the BinarySearchTreeCallCountingTest class up as a standard JUnit test class. Like the performance tests from Chapter 9 on binary searching, these tests aren’t actually “real” tests — they make no assertions — but your familiarity with JUnit is a compelling enough reason to take this approach.

The class defines a binary tree into which you insert some values, a comparator to use for comparing values, and a constant that defines the number of values — TEST_SIZE — to insert. You have also added a method, reportCalls(), that will be used to print the number of calls made to the comparator, in the form test-name: #### calls.

package com.wrox.algorithms.bstrees;

import com.wrox.algorithms.sorting.CallCountingComparator; import com.wrox.algorithms.sorting.NaturalComparator; import junit.framework.TestCase;

public class BinarySearchTreeCallCountingTest extends TestCase { private static final int TEST_SIZE = 1000;

private CallCountingComparator _comparator; private BinarySearchTree _tree;

protected void setUp() throws Exception { super.setUp();

_comparator = new CallCountingComparator(NaturalComparator.INSTANCE); _tree = new BinarySearchTree(_comparator);

}

262

Binary Search Trees

private void reportCalls() { System.out.println(getName() + “: “

+ _comparator.getCallCount() + “ calls”);

}

...

}

In testRandomInsert(), you insert TEST_SIZE randomly generated numbers, building what you imagine will be a relatively balanced tree:

public void testRandomInsertion() {

for (int i = 0; i < TEST_SIZE; ++i) {

_tree.insert(new Integer((int) (Math.random() * TEST_SIZE)));

}

reportCalls();

}

Then, in testInOrderInsertion(), you insert (in order) the values between 0 and TEST_SIZE to produce what you think will be a seriously unbalanced tree:

public void testInOrderInsertion() {

for (int i = 0; i < TEST_SIZE; ++i) { _tree.insert(new Integer(i));

}

reportCalls();

}

If you run these tests, depending on your environment, you should see some output similar to the following:

testRandomInsertion: 11624 calls testInOrderInsertion: 499500 calls

Table 10-2 summarizes what’s going on.

Table 10-2: Performance Comparison for 1,000 Inserts into a Binary Search Tree

* Actual results will vary due to the random nature of the test data.

As you can see, insertion performs best when the data is unordered — in fact, as Table 10-2 quite clearly shows, significantly better: The average time to perform the random insertion was 11,624 / 1000 = 11 comparisons, or O(log N); for in-order, it was 499,500 / 1000 = 499, or O(N).

263