Beginning Algorithms (2006)
.pdf
Chapter 10
|
|
K |
|
|
D |
|
L |
A |
F |
I |
M |
|
H |
|
P |
Figure 10-11: The successor node is deleted.
Deletion can unbalance a binary search tree, leading to a degradation in performance. Just like inserting ordered data into a tree can cause it to become unbalanced, deleting data in order causes it to become unbalanced. For example, Figure 10-12 shows the effect of deleting the values A, D, F, and H from the tree in Figure 10-1.
I
L
K M
P
Figure 10-12: An unbalanced tree resulting from the deletion of ordered data.
Because all of the values listed are on the left-hand side of the tree (starting at the root), you end up with a lopsided tree.
In any event, whichever deletion case is required and regardless of whether, after deletion, the tree remains balanced, most of the time is actually spent finding the node to delete (and possibly finding its successor). Therefore, just like search and insert, the time to delete is still O(h).
234
Binary Search Trees
In-order Traversal
In-order traversal, as the name suggests, visits the values in a binary search tree in sorted order. This can be useful for printing out or otherwise processing the values in order. Again, given our example tree from Figure 10-1, an in-order traversal would visit the values in the following order: A, D, F, I, K, L, M, P.
There are two simple ways to perform in-order traversal: recursively and iteratively. To perform a recursive in-order traversal, starting with the root node:
1.
2.
3.
Traverse the left subtree of the node.
Visit the node itself.
Traverse the right subtree.
To perform an iterative in-order traversal of a binary search tree, start with the minimum of the tree and visit it and each successor node until there are no more.
Pre-order Traversal
Pre-order traversal first visits the root node, then each of the subtrees. A pre-order traversal of the tree in Figure 10-1 would produce the following sequence of values: I, D, A, F, H, L, K, M, P.
Like in-order traversal, pre-order traversal can easily be defined recursively. To perform a pre-order traversal, starting with the root node:
1.
2.
3.
Visit the node itself.
Traverse the left subtree.
Traverse the right subtree.
Unlike in-order traversal however, an iterative form is rather involved and requires the explicit use of a stack (see Chapter 5) in place of the implicit processor stack used when making recursive calls.
Post-order Traversal
Post-order traversal visits the root node after each of the subtrees. A post-order traversal of the tree in Figure 10-1 would visit the nodes in the following order: A, H, F, D, K, P, M, L, I.
To perform a post-order traversal, starting with the root node:
1.
2.
3.
Traverse the left subtree.
Traverse the right subtree.
Visit the node itself.
Like pre-order traversal, an iterative form is rather involved and requires the use of a stack.
235
Chapter 10
Balancing
The order in which data is inserted into and deleted from binary search trees affects the performance. More specifically, inserting and deleting ordered data can cause the tree to become unbalanced and, in the worst case, degenerate into a simple linked list. As mentioned, you can use balancing as a means of restoring the desired characteristics of the tree. Although the implementation is beyond the scope of this book, we still believe it is important to understand at least how the balancing algorithms work, even if we do not provide coded examples. To this end, we will present a short summary of one such tree: AVL.
One of the most difficult tasks in maintaining a balanced tree is detecting an imbalance in the first place. Imagine a tree with hundreds if not thousands of nodes. How, after performing a deletion or insertion, can you detect an imbalance without traversing the entire tree?
Two Russian mathematicians, G. M. Adel’son-Vel’skii and E. M. Landis (hence the name AVL), realized that one very simple way to keep a binary search tree balanced is to track the height of each subtree. If two siblings ever differ in height by more than one, the tree has become unbalanced.
Figure 10-13 shows a tree that needs rebalancing. Notice that the root node’s children differ in height by two.
+2
I
0
L
0 0
K M
Figure 10-13: The difference in height between children of the root node is greater than one.
After an imbalance has been detected, you need to correct it, but how? The solution involves rotating nodes to remove the imbalance. You perform this rebalancing by working up the tree from the inserted/ deleted node to the root, rotating nodes as necessary anytime a node is inserted or deleted from an AVL tree.
There are four different types of rotation depending on the nature of the imbalance: a single rotation and a double rotation, each with a left and right version. Table 10-1 shows you how to determine whether a single or a double rotation is required.
236
|
|
|
|
Binary Search Trees |
|
|
|
|
|
|
|
|
|
|
|
Table 10-1: Determining Rotation Number |
|
||
|
Inbalanced |
Child Is Balanced |
Child Is Left-Heavy |
Child Is Right-Heavy |
|
|
|
|
|
|
Left-Heavy |
Once |
Once |
Twice |
|
Right-Heavy |
Once |
Twice |
Once |
|
|
|
|
|
In Figure 10-13, the root node I is right-heavy, and its right child, L, is also right-heavy. The information in Table 10-1 indicates that you only need to perform one rotation — to the left, to demote the I and promote the L, resulting in the tree shown in Figure 10-14.
-1
L
+1 0
I M
0
K
Figure 10-14: AVL height property restored by rotating the node once to the left.
If the tree looks like that shown in Figure 10-15, two rotations are required — the root node is rightheavy and its right child is left-heavy. This might happen if you had just inserted the K, for example.
+2
I
-1
L
0
K
Figure 10-15: A tree requiring two rotations.
237
Chapter 10
First you rotate L right once and then rotate the L left once, as shown in Figure 10-16.
+2
0
I
+1 |
|
K |
|
|
|
K |
0 |
0 |
|
|
I L
0
L
Figure 10-16: The first rotation moves the child node L to the right; the second rotates the unbalanced node I to the left.
Although AVL trees are not guaranteed to be perfectly balanced, they exhibit excellent performance characteristics. In fact, given a million nodes, a perfectly balanced tree will require around log21000000 = 20 comparisons, whereas the AVL tree requires around 1.44 log21000000 = 28 comparisons. Certainly much better than the 500,000 comparisons required in the worst-case binary search tree!
Although not covered here, one more variation on self-balancing binary trees is the Red-Black tree. For more information on Red-Black trees, see Introduction to Algorithms [Cormen, 2001].
Testing and Implementing a Binar y
Search Tree
It’s finally time to get into some code. As always, you’re going to start by developing some tests. Once that’s done, you write the implementation code. As part of the implementation, you create two main classes: Node and BinarySearchTree. Node, as the name suggests, will model the nodes in the tree, while BinarySearchTree will provide a wrapper around the root node and contain all the search(), delete(), and insert() code.
Because the BinarySearchTree class doesn’t mean much without nodes, in the following Try it Out section you write some node tests. Following that, you’ll write the node class itself.
238
Binary Search Trees
Try It Out |
Testing a Node Class |
Create the node tests as follows:
package com.wrox.algorithms.bstrees;
import junit.framework.TestCase;
public class NodeTest extends TestCase { private Node _a;
private Node _d; private Node _f; private Node _h; private Node _i; private Node _k; private Node _l; private Node _m; private Node _p;
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);
}
public void testMinimum() { assertSame(_a, _a.minimum()); assertSame(_a, _d.minimum()); assertSame(_f, _f.minimum()); assertSame(_h, _h.minimum()); assertSame(_a, _i.minimum()); assertSame(_k, _k.minimum()); assertSame(_k, _l.minimum()); assertSame(_m, _m.minimum()); assertSame(_p, _p.minimum());
}
public void testMaximum() { assertSame(_a, _a.maximum()); assertSame(_h, _d.maximum()); assertSame(_h, _f.maximum()); assertSame(_h, _h.maximum()); assertSame(_p, _i.maximum());
239
Chapter 10
assertSame(_k, _k.maximum()); assertSame(_p, _l.maximum()); assertSame(_p, _m.maximum()); assertSame(_p, _p.maximum());
}
public void testSuccessor() { assertSame(_d, _a.successor()); assertSame(_f, _d.successor()); assertSame(_h, _f.successor()); assertSame(_i, _h.successor()); assertSame(_k, _i.successor()); assertSame(_l, _k.successor()); assertSame(_m, _l.successor()); assertSame(_p, _m.successor()); assertNull(_p.successor());
}
public void testPredecessor() { assertNull(_a.predecessor()); assertSame(_a, _d.predecessor()); assertSame(_d, _f.predecessor()); assertSame(_f, _h.predecessor()); assertSame(_h, _i.predecessor()); assertSame(_i, _k.predecessor()); assertSame(_k, _l.predecessor()); assertSame(_l, _m.predecessor()); assertSame(_m, _p.predecessor());
}
public void testIsSmaller() { assertTrue(_a.isSmaller()); assertTrue(_d.isSmaller()); assertFalse(_f.isSmaller()); assertFalse(_h.isSmaller()); assertFalse(_i.isSmaller()); assertTrue(_k.isSmaller()); assertFalse(_l.isSmaller()); assertFalse(_m.isSmaller()); assertFalse(_p.isSmaller());
}
public void testIsLarger() { assertFalse(_a.isLarger()); assertFalse(_d.isLarger()); assertTrue(_f.isLarger()); assertTrue(_h.isLarger()); assertFalse(_i.isLarger()); assertFalse(_k.isLarger()); assertTrue(_l.isLarger()); assertTrue(_m.isLarger()); assertTrue(_p.isLarger());
}
240
Binary Search Trees
public void testSize() { assertEquals(1, _a.size()); assertEquals(4, _d.size()); assertEquals(2, _f.size()); assertEquals(1, _h.size()); assertEquals(9, _i.size()); assertEquals(1, _k.size()); assertEquals(4, _l.size()); assertEquals(2, _m.size()); assertEquals(1, _p.size());
}
public void testEquals() { Node a = new Node(“A”); Node h = new Node(“H”); Node k = new Node(“K”); Node p = new Node(“P”);
Node f = new Node(“F”, null, h);
Node m = new Node(“M”, null, p);
Node d = new Node(“D”, a, f);
Node l = new Node(“L”, k, m);
Node i = new Node(“I”, d, l);
assertEquals(a, _a); assertEquals(d, _d); assertEquals(f, _f); assertEquals(h, _h); assertEquals(i, _i); assertEquals(k, _k); assertEquals(l, _l); assertEquals(m, _m); assertEquals(p, _p);
assertFalse(_i.equals(null)); assertFalse(_f.equals(_d));
}
}
How It Works
All the tests start with a node structure identical to the one shown in Figure 10-1. (Now might be a good time to refresh your memory.)
The NodeTest class defines some instance variables — one for each node shown in Figure 10-1 — and initializes them in setUp() for use by the test cases. The first four nodes are all leaf nodes (as in the examples) and as such need only the value. The remaining nodes all have left and/or right children, which are passed in as the second and third constructor parameters, respectively:
package com.wrox.algorithms.bstrees;
import junit.framework.TestCase;
public class NodeTest extends TestCase { private Node _a;
private Node _d;
241
