Binary search trees - Data Structures and Problem Solving Using Java - page 724

1 /**
2 * Insert into the tree.
3 * @param item the item to insert.
4 * @throws DuplicateItemException if item is already present.
5 */
6 public void insert( AnyType item )
7 {
8 current = parent = grand = header;
9 nullNode.element = item;
10
11 while( compare( item, current ) != 0 )
12 {
13 great = grand; grand = parent; parent = current;
14 current = compare( item, current ) < 0 ?
15 current.left : current.right;
16
17 // Check if two red children; fix if so
18 if( current.left.color == RED && current.right.color == RED )
19 handleReorient( item );
20 }
21
22 // Insertion fails if already present
23 if( current != nullNode )
24 throw new DuplicateItemException( item.toString( ) );
25 current = new RedBlackNode<AnyType>( item, nullNode, nullNode );
26
27 // Attach to parent
28 if( compare( item, parent ) < 0 )
29 parent.left = current;
30 else
31 parent.right = current;
32 handleReorient( item );
33 }
34
35 /**
36 * Compare item and t.element, using compareTo, with
37 * caveat that if t is header, then item is always larger.
38 * This routine is called if it is possible that t is a header.
39 * If it is not possible for t to be a header, use compareTo directly.
40 */
41 private final int compare( AnyType item, RedBlackNode<AnyType> t )
42 {
43 if( t == header )
44 return 1;
45 else
46 return item.compareTo( t.element );
47 }
figure 19.47
The insert and compare routines for the RedBlackTree class