Advanced Data Structures - Java Concepts - page 992

The standard Java library uses red-black trees, a special form of balanced binary
trees, to implement sets and maps. You will see in Section 16.7 what you need to do
to use the TreeSet and TreeMap classes. For information on how to implement a
red-black tree yourself, see [ 1 ].

ch16/tree/BinarySearchTree.java

1 /**
2 This class implements a binary search tree whose
3 nodes hold objects that implement the Comparable
4 interface.
5 */
6 public class BinarySearchTree
7 {
8 /**
9 Constructs an empty tree.
10 */
11 public BinarySearchTree()
12 {
13 root = null ;
14 }
15
16 /**
17 Inserts a new node into the tree.
18 @param obj the object to insert
19 */
20 public void add(Comparable obj)
21 {
22 Node newNode = new Node();
23 newNode.data = obj;
24 newNode.left = null ;
25 newNode.right = null ;
26 if (root == null ) root = newNode;
27 else root.addNode(newNode);
28 }
29
30 /**
31 Tries to find an object in the tree.
32 @param obj the object to find

727
728