001: package U2.T2.examples;
002:
003: /**
004: * A class implementing unbalanced binary search tree. Note that all
005: * "matching" is based on the compareTo method.
006: *
007: * <p>Adapted from original code by Mark Weiss.
008: *
009: * <p>Is this class correct....?
010: *
011: * @author Mark Allen Weiss
012: *
013: */
014:
015: // ******************PUBLIC OPERATIONS*********************
016: // void insert( x ) --> Insert x
017: // void remove( x ) --> Remove x
018: // Comparable find( x ) --> Return item that matches x
019: // Comparable findMin( ) --> Return smallest item
020: // Comparable findMax( ) --> Return largest item
021: // boolean isEmpty( ) --> Return true if empty; else false
022: // void makeEmpty( ) --> Remove all items
023: // void printTree( ) --> Print tree in sorted order
024: public class BinarySearchTree {
025:
026: /**
027: * Construct the tree.
028: */
029: public BinarySearchTree() {
030: root = null;
031: }
032:
033: /**
034: * Insert x into the tree; duplicates are ignored.
035: * @param x the item to insert.
036: */
037: public void insert(Comparable x) {
038: // System.out.println(".") ;
039: root = insert(x, root);
040: }
041:
042: /**
043: * A specification for insert, saying that after insert(x) x
044: * should be in the tree.
045: */
046: public void insert_spec(Comparable x) {
047: insert(x);
048: assert (find(x) != null) : "POST";
049: }
050:
051: /**
052: * Remove from the tree. Nothing is done if x is not found.
053: * @param x the item to remove.
054: */
055: public void remove(Comparable x) {
056: root = remove(x, root);
057: }
058:
059: /**
060: * a specification for remove, saying that after the remove x
061: * should no longer be in the tree.
062: */
063: public void remove_spec(Comparable x) {
064: remove(x);
065: assert (find(x) == null) : "POST";
066: }
067:
068: /**
069: * Find the smallest item in the tree.
070: * @return smallest item or null if empty.
071: */
072: public Comparable findMin() {
073: return elementAt(findMin(root));
074: }
075:
076: /**
077: * The spec of findMin. It says that the returned value, if not
078: * null, should be an element of the tree.
079: */
080: public void findMin_spec() {
081: boolean wasEmpty = isEmpty();
082: Comparable x = findMin();
083: assert (wasEmpty || find(x) == x) : "POST";
084: }
085:
086: /**
087: * Find the largest item in the tree.
088: * @return the largest item of null if empty.
089: */
090: public Comparable findMax() {
091: return elementAt(findMax(root));
092: }
093:
094: /**
095: * Find an item in the tree.
096: * @param x the item to search for.
097: * @return the matching item or null if not found.
098: */
099: public Comparable find(Comparable x) {
100: return elementAt(find(x, root));
101: }
102:
103: /**
104: * Make the tree logically empty.
105: */
106: public void makeEmpty() {
107: root = null;
108: }
109:
110: /**
111: * Test if the tree is logically empty.
112: * @return true if empty, false otherwise.
113: */
114: public boolean isEmpty() {
115: return root == null;
116: }
117:
118: /**
119: * Print the tree contents in sorted order.
120: */
121: private void printTree() {
122: if (isEmpty())
123: System.out.println("Empty tree");
124: else
125: printTree(root);
126: }
127:
128: /**
129: * Internal method to get element field.
130: * @param t the node.
131: * @return the element field or null if t is null.
132: */
133: private Comparable elementAt(BinaryNode t) {
134: return t == null ? null : t.element;
135: }
136:
137: /**
138: * Internal method to insert into a subtree.
139: * @param x the item to insert.
140: * @param t the node that roots the tree.
141: * @return the new root.
142: */
143: private BinaryNode insert(Comparable x, BinaryNode t) {
144: /* 1*/if (t == null)
145: /* 2*/t = new BinaryNode(x, null, null);
146: /* 3*/else if (x.compareTo(t.element) < 0)
147: /* 4*/t.left = insert(x, t.left);
148: /* 5*/else if (x.compareTo(t.element) > 0)
149: /* 6*/t.right = insert(x, t.right);
150: /* 7*/else
151: /* 8*/; // Duplicate; do nothing
152: /* 9*/return t;
153: }
154:
155: class BinaryNode {
156:
157: Comparable element;
158: BinaryNode left;
159: BinaryNode right;
160:
161: BinaryNode(Comparable x, BinaryNode u, BinaryNode v) {
162: element = x;
163: left = u;
164: right = v;
165: }
166:
167: }
168:
169: /**
170: * Internal method to remove from a subtree.
171: * @param x the item to remove.
172: * @param t the node that roots the tree.
173: * @return the new root.
174: */
175: private BinaryNode remove(Comparable x, BinaryNode t) {
176: if (t == null)
177: return t; // Item not found; do nothing
178: if (x.compareTo(t.element) < 0)
179: t.left = remove(x, t.left);
180: else if (x.compareTo(t.element) > 0)
181: t.right = remove(x, t.right);
182: else if (t.left != null && t.right != null) // Two children
183: {
184: t.element = findMin(t.right).element;
185: t.right = remove(t.element, t.right);
186: } else
187: t = (t.left != null) ? t.left : t.right;
188: return t;
189: }
190:
191: /**
192: * Internal method to find the smallest item in a subtree.
193: * @param t the node that roots the tree.
194: * @return node containing the smallest item.
195: */
196: private BinaryNode findMin(BinaryNode t) {
197: if (t == null)
198: return null;
199: else if (t.left == null)
200: return t;
201: return findMin(t.left);
202: }
203:
204: /**
205: * Internal method to find the largest item in a subtree.
206: * @param t the node that roots the tree.
207: * @return node containing the largest item.
208: */
209: private BinaryNode findMax(BinaryNode t) {
210: if (t != null)
211: while (t.right != null)
212: t = t.right;
213:
214: return t;
215: }
216:
217: /**
218: * Internal method to find an item in a subtree.
219: * @param x is item to search for.
220: * @param t the node that roots the tree.
221: * @return node containing the matched item.
222: */
223: private BinaryNode find(Comparable x, BinaryNode t) {
224: if (t == null)
225: return null;
226: if (x.compareTo(t.element) < 0)
227: return find(x, t.left);
228: else if (x.compareTo(t.element) > 0)
229: return find(x, t.right);
230: else
231: return t;// Match
232: }
233:
234: /**
235: * Internal method to print a subtree in sorted order.
236: * @param t the node that roots the tree.
237: */
238: private void printTree(BinaryNode t) {
239: if (t != null) {
240: printTree(t.left);
241: System.out.println(t.element);
242: printTree(t.right);
243: }
244: }
245:
246: /** The tree root. */
247: private BinaryNode root;
248:
249: }
|