public class BinarySearchTree
2: import java.util.Comparator;
4: /**
5: * A binary search tree implementation.In a BST, all nodes to the left of the
6: * root are smaller than the root, and all nodes to the right of the root are
7: * larger than the root. Also, every sub-tree is a BST.
8: *
9: * @author Mark Young (A00000000)
10: * @param <E> the base type for this BST
11: */
12: public class BinarySearchTree<E extends Comparable<? super E>> {
14: private BSTNode root;
15: private Comparator<? super E> comp;
16: private int numInTree;
18: /**
19: * Create a BST using the natural ordering of the base class.
20: */
21: public BinarySearchTree() {
22: this((o1, o2) -> o1.compareTo(o2));
23: }
25: /**
26: * Create a BST using a custom Comparator.
27: *
28: * @param reqComp the comparator to order this tree with.
29: */
30: public BinarySearchTree(Comparator<? super E> reqComp) {
31: root = null;
32: numInTree = 0;
33: comp = reqComp;
34: }
36: /**
37: * Returns whether this BST contains the given item.
38: *
39: * @param item the item to test for.
40: * @return true if {@code item} is in this BST; false otherwise.
41: */
42: public boolean contains(E item) {
43: BSTNode cur = root;
44: while (cur != null) {
45: int diff = comp.compare(item, cur.data);
46: if (diff < 0) { // item < root
47: cur = cur.left;
48: } else if (diff > 0) { // item > root
49: cur = cur.right;
50: } else { // item == root
51: return true;
52: }
53: }
55: // item not found
56: return false;
57: }
59: /**
60: * Adds the given item to this BST.
61: *
62: * @param anItem the item to add.
63: * @return true if the item was added; false otherwise.
64: */
65: public boolean insert(E anItem) {
66: int oldCount = numInTree;
67: root = insertNode(anItem, root);
68: return numInTree > oldCount;
69: }
71: /**
72: * Remove the given item from this BST.
73: *
74: * @param anItem the item to remove.
75: * @return true if {@code anItem} was deleted; false otherwise.
76: */
77: public boolean delete(E anItem) {
78: int oldCount = numInTree;
79: root = deleteNode(anItem, root);
80: return numInTree < oldCount;
81: }
83: /**
84: * Creates a String representation of this BST. The string is a diagram of
85: * the tree, rotated 90 degrees counter-clockwise.
86: *
87: * @return a String diagram of this BST.
88: */
89: @Override
90: public String toString() {
91: return nodeToString(2, root);
92: }
94: /**
95: * Inserts a new Node containing anItem in the BST rooted at cur, unless
96: * there's already one there.
97: *
98: * @param anItem the value being inserted into this BST.
99: * @param cur the root of the sub-tree anItem must be in.
100: * @return the root of the sub-tree resulting from the insertion.
101: */
102: private BSTNode insertNode(E anItem, BSTNode cur) {
103: // current subtree is empty
104: if (cur == null) {
105: // this item is new to the tree
106: ++numInTree;
107: // create a new node and return it
108: return new BSTNode(anItem);
109: }
111: // find which subtree (if either) this item belongs in
112: int diff = comp.compare(anItem, cur.data);
113: if (diff < 0) { // anItem < cur.data
114: // insert to the left
115: cur.left = insertNode(anItem, cur.left);
116: } else if (diff > 0) { // anItem > cur.data
117: // insert to the right
118: cur.right = insertNode(anItem, cur.right);
119: } // else anItem == cur.data, so item already present (nothing to do)
121: // return the root of this subtree
122: return cur;
123: }
125: /**
126: * Removes the Node containing anItem from the BST rooted at cur, if it's
127: * there.
128: *
129: * @param anItem the value being inserted into this BST.
130: * @param cur the root of the sub-tree anItem must be in.
131: * @return the root of the sub-tree resulting from the insertion.
132: */
133: private BSTNode deleteNode(E anItem, BSTNode cur) {
134: // if cur == null then the item was not in the tree,
135: // so there's nothing to do!
136: if (cur != null) {
137: // find which side of the root the item should be on
138: int diff = comp.compare(anItem, cur.data);
139: if (diff < 0) { // anItem < cur.data
140: // delete from the left subtree
141: cur.left = deleteNode(anItem, cur.left);
142: } else if (diff > 0) { // anItem > cur.data
143: // delete from the right subtree
144: cur.right = deleteNode(anItem, cur.right);
145: } else { // anItem == cur.data
146: // deleting the value at this node
147: if (cur.left == null) { // this node has no smaller children
148: // replace this node with its right child
149: cur = cur.right;
150: --numInTree;
151: } else if (cur.right == null) { // ... has no larger children
152: // replce this node with its left child
153: cur = cur.left;
154: --numInTree;
155: } else { // this node has smaller AND larger children
156: // replace this node's data with smallest value on right
157: cur.data = minRight(cur.right);
158: // delete that value from the tree on the right
159: cur.right = deleteNode(cur.data, cur.right);
160: }
161: }
162: }
164: // return the root of this subtree
165: return cur;
166: }
168: /**
169: * Finds the smallest value on the right (larger) side of the given node.
170: *
171: * @param cur the root of the sub-tree to search.
172: * @return the smallest value in that sub-tree.
173: */
174: private E minRight(BSTNode cur) {
175: // while this node has smaller children...
176: while (cur.left != null) {
177: // go left
178: cur = cur.left;
179: }
181: // return the data in this node with no smaller children
182: return cur.data;
183: }
185: private static final int EXTRA_INDENT = 6;
187: /**
188: * Make a diagram of a rooted part of this BST.
189: *
190: * @param indent how many spaces the root node should be indented.
191: * @param root the root node of this sub-tree.
192: * @return a String representing this sub-tree.
193: */
194: private String nodeToString(int indent, BSTNode root) {
195: if (root == null) { // subtree is empty
196: // end recursion, return indented String representing empty tree
197: return String.format("%" + indent + "s%s", "", "--");
198: }
200: // non-empty subtree
201: return String.format(
202: // right subtree, new line, spaces, root, new line, left subtree
203: "%s%n%" + indent + "s%s%n%s",
204: // the right subtree, indented another 4 spaces
205: nodeToString(indent + EXTRA_INDENT, root.right),
206: // the root, indented the given number of spaces
207: "",
208: root.data.toString(),
209: // the left subtree, indented another four spaces
210: nodeToString(indent + EXTRA_INDENT, root.left));
211: }
213: /**
214: * A class to hold the data plus links for left and right children/subtrees.
215: */
216: private class BSTNode {
218: E data;
219: BSTNode right, left;
221: /**
222: * Create a new Node not linked into the structure.
223: *
224: * @param reqData the data for the new node.
225: */
226: public BSTNode(E reqData) {
227: this(reqData, null, null);
228: }
230: /**
231: * Create a new Node linked into the structure.
232: *
233: * @param reqData the data for the new node.
234: * @param reqLeft the root of the left sub-tree.
235: * @param reqRight the root of the right sub-tree.
236: */
237: public BSTNode(E reqData, BSTNode reqLeft, BSTNode reqRight) {
238: data = reqData;
239: left = reqLeft;
240: right = reqRight;
241: }
242: }
244: }