View difference between Paste ID: <a href="/w1gWYYqV">w1gWYYqV</a> and <a href="/0b8w1ksF">0b8w1ksF</a>

package lab9;
1		package lab9;
2		import java.util.*;
3		/**
4		* Implements a Map as a binary search tree of (key,value) pairs.
5		* CSE131 Lab 9
6		* @author
7		* @version 1.0
8		* Date:
9		*/
10		public class TreeMap<K extends Comparable<K>,V> implements Map<K,V> {
11
12		TreeNode<K, V> root;
13
14		public TreeMap() {
15		root = new TreeNode<K,V>(null, null);
16		}
17
18		public void put(K key, V value) {
19		TreeNode<K, V> newItem = new TreeNode<K, V>(key, value);
20		TreeNode<K, V> pointer = root.left;
21
22		if(root.left == null) {
23		root.left = newItem;
24		return;
25		}
26
27		while(true) {
28		if(pointer.key.compareTo(key) == 0) {
29		pointer.value = value;
30		return;
31		}
32
33		else if(pointer.key.compareTo(key) < 0) {
34		if(pointer.right == null) {
35		pointer.right = newItem;
36		return;
37		}
38		else
39		pointer = pointer.right;
40		}
41
42		else {
43		if(pointer.left == null) {
44		pointer.left = newItem;
45		return;
46		}
47		else
48		pointer = pointer.left;
49		}
50		}
51		}
52
53		public V get(K key) {
54		TreeNode<K, V> pointer = root.left;
55
56		while(pointer != null) {
57		if(pointer.key.compareTo(key) == 0) {
58		if(pointer.deleted == false)
59		return pointer.value;
60		else
61		throw new NoSuchElementException();
62		}
63
64		else if(pointer.key.compareTo(key) < 0)
65		pointer = pointer.right;
66
67		else
68		pointer = pointer.left;
69		}
70
71		throw new NoSuchElementException();
72		}
73
74		public boolean contains(K key) {
75		TreeNode<K, V> pointer = root.left;
76
77		while(pointer != null) {
78		if(pointer.key.compareTo(key) == 0) {
79		if(pointer.deleted == true)
80		return false;
81		else
82		return true;
83		}
84
85		else if(pointer.key.compareTo(key) < 0)
86		pointer = pointer.right;
87
88		else
89		pointer = pointer.left;
90		}
91
92		return false;
93		}
94
95		public boolean remove(K key) {
96		TreeNode<K, V> pointer = root;
97
98		if(!contains(key))
99		return false;
100
101		while(pointer != null) {
102		if(pointer.left.key.compareTo(key) == 0) {
103		if(pointer.left.left == null && pointer.left.right == null) {
104		pointer.left = null;
105		return true;
106		}
107		else if(pointer.left.left == null ^ pointer.left.right == null) {
108		if(pointer.left.left == null) {
109		pointer.left = pointer.left.right;
110		}
111		else {
112		pointer.left = pointer.left.left;
113		}
114		return true;
115		}
116		else {
117		TreeNode<K, V> newPointer = pointer.left.left;
118		while(newPointer.left.right != null) {
119		newPointer = newPointer.right;
120		}
121		remove(newPointer.key);
122		pointer.left.key = newPointer.key;
123		pointer.left.value = newPointer.value;
124		return true;
125		}
126		}
127
128		else if(pointer != root && pointer.right.key.compareTo(key) == 0) {
129		if(pointer.right.left == null && pointer.right.right == null) {
130		pointer.right = null;
131		return true;
132		}
133		else if(pointer.right.left == null ^ pointer.right.right == null) {
134		if(pointer.right.left == null) {
135		pointer.right = pointer.right.right;
136		}
137		else {
138		pointer.right = pointer.right.left;
139		}
140		return true;
141		}
142		else {
143		TreeNode<K, V> newPointer = pointer.left.right;
144		while(newPointer.right.left != null) {
145		newPointer = newPointer.left;
146		}
147		remove(newPointer.key);
148		pointer.right.key = newPointer.key;
149		pointer.right.value = newPointer.value;
150		return true;
151		}
152		}
153
154		else if(pointer != root && pointer.key.compareTo(key) < 0)
155		pointer = pointer.right;
156
157		else
158		pointer = pointer.left;
159		}
160
161		return false;
162		}
163
164		public String toString() {
165		return toStringHelper(root.left, "", "");
166		}
167
168		public String toStringHelper(TreeNode<K, V> node, String tabs, String helper) {
169		if (node.right != null) {
170		helper = helper + toStringHelper(node.right, tabs + "\t", "");
171		}
172		helper += tabs + "(" + node.key + ", " + node.value + ")\n";
173		if (node.left != null) {
174		helper = helper + toStringHelper(node.left, tabs + "\t", "");
175		}
176		return helper;
177		}
178
179		}