1 import java.util.ArrayList;
2 import java.util.List;
3
4 /**
5 This program tests the red-black tree class.
6 */
7 public class RedBlackTreeTester
8 {
9 public static void main(String[] args)
10 {
11 testFromBook();
12 insertionTest("ABCDEFGHIJ");
13 removalTest(removalTestTemplate());
14 System.out.println("All tests passed.");
15 }
16
17 /**
18 Runs the simple test from the textbook.
19 */
20 public static void testFromBook()
21 {
22 RedBlackTree t = new RedBlackTree();
23 t.add("D");
24 t.add("B");
25 t.add("A");
26 t.add("C");
27 t.add("F");
28 t.add("E");
29 t.add("I");
30 t.add("G");
31 t.add("H");
32 t.add("J");
33 t.remove("A"); // Removing leaf
34 t.remove("B"); // Removing element with one child
35 t.remove("F"); // Removing element with two children
36 t.remove("D"); // Removing root
37 assertEquals("C E G H I J ", t.toString());
38 }
39
40 /**
41 Inserts all permutations of a string into a red-black tree and checks that
42 it contains the strings afterwards.
43 @param letters a string of letters without repetition
44 */
45 public static void insertionTest(String letters)
46 {
47 PermutationGenerator gen = new PermutationGenerator(letters);
48 for (String perm : gen.getPermutations())
49 {
50 RedBlackTree t = new RedBlackTree();
51 for (int i = 0; i < perm.length(); i++)
52 {
53 String s = perm.substring(i, i + 1);
54 t.add(s);
55 }
56 assertEquals(letters, t.toString().replace(" ", ""));
57 }
58 }
59
60 /**
61 Tests removal, given a template for a tree with a black node that
62 is to be deleted. All other nodes should be given all possible combinations
63 of red and black.
64 @param t the template for the test cases
65 */
66 public static void removalTest(RedBlackTree t)
67 {
68 for (int m = 0; m <= 1; m++)
69 {
70 int nodesToColor = count(t.root) - 2; // We don't recolor the root or toDelete
71 for (int k = 0; k < Math.pow(2, nodesToColor); k++)
72 {
73 RedBlackTree rb = new RedBlackTree();
74 if (m == 0) { rb.root = copy(t.root); }
75 else { rb.root = mirror(t.root); }
76
77 RedBlackTree.Node[] nodes = getNodes(rb);
78 RedBlackTree.Node toDelete = null;
79
80 // Color with the bit pattern of k
81 int bits = k;
82 for (RedBlackTree.Node n : nodes)
83 {
84 if (n == rb.root)
85 {
86 n.color = RedBlackTree.BLACK;
87 }
88 else if (n.color == RedBlackTree.BLACK)
89 {
90 toDelete = n;
91 }
92 else
93 {
94 n.color = bits % 2;
95 bits = bits / 2;
96 }
97 }
98
99 // Add children to make equal costs to null
100 int targetCost = costToRoot(toDelete);
101 for (RedBlackTree.Node n : nodes)
102 {
103 int cost = targetCost - costToRoot(n);
104 if (n.left == null) { n.setLeftChild(fullTree(cost)); }
105 if (n.right == null) { n.setRightChild(fullTree(cost)); }
106 }
107
108 int filledSize = populate(rb);
109 boolean good = true;
110 try { checkRedBlack(rb); }
111 catch (IllegalStateException ex) { good = false; }
112 if (good)
113 {
114 Comparable d = toDelete.data;
115 rb.remove(d);
116 checkRedBlack(rb);
117 for (Integer j = 0; j < filledSize; j++)
118 {
119 if (!rb.find(j) && !d.equals(j))
120 {
121 throw new IllegalStateException(j + " deleted");
122 }
123 if (rb.find(d))
124 {
125 throw new IllegalStateException(d + " not deleted");
126 }
127 }
128 }
129 }
130 }
131 }
132
133 /**
134 Makes a template for testing removal.
135 @return a partially complete red-black tree for the test.
136 The node to be removed is black.
137 */
138 private static RedBlackTree removalTestTemplate()
139 {
140 RedBlackTree template = new RedBlackTree();
141
142 /*
143 n7
144 / \
145 n1 n8
146 / \
147 n0 n3
148 / \
149 n2* n5
150 /\
151 n4 n6
152 */
153
154 RedBlackTree.Node[] n = new RedBlackTree.Node[9];
155 for (int i = 0; i < n.length; i++) { n[i] = new RedBlackTree.Node(); }
156 template.root = n[7];
157 n[7].setLeftChild(n[1]);
158 n[7].setRightChild(n[8]);
159 n[1].setLeftChild(n[0]);
160 n[1].setRightChild(n[3]);
161 n[3].setLeftChild(n[2]);
162 n[3].setRightChild(n[5]);
163 n[5].setLeftChild(n[4]);
164 n[5].setRightChild(n[6]);
165
166 n[2].color = RedBlackTree.BLACK;
167
168 return template;
169 }
170
171 /**
172 Gets all nodes of this tree in sorted order.
173 @param t a red-black tree
174 @return an array of all nodes in t
175 */
176 private static RedBlackTree.Node[] getNodes(RedBlackTree t)
177 {
178 RedBlackTree.Node[] nodes = new RedBlackTree.Node[count(t.root)];
179 getNodes(t.root, nodes, 0);
180 return nodes;
181 }
182
183 /**
184 Gets all nodes of a subtree and fills them into an array.
185 @param n the root of the subtree
186 @param nodes the array into which to place the nodes
187 @param start the offset at which to start placing the nodes
188 @return the number of nodes placed
189 */
190 private static int getNodes(RedBlackTree.Node n, RedBlackTree.Node[] nodes, int start)
191 {
192 if (n == null) { return 0; }
193 int leftFilled = getNodes(n.left, nodes, start);
194 nodes[start + leftFilled] = n;
195 int rightFilled = getNodes(n.right, nodes, start + leftFilled + 1);
196 return leftFilled + 1 + rightFilled;
197 }
198
199 /**
200 Computes the cost from a node to a root.
201 @param n a node of a red-black tree
202 @return the number of black nodes between n and the root
203 */
204 private static int costToRoot(RedBlackTree.Node n)
205 {
206 int c = 0;
207 while (n != null) { c = c + n.color; n = n.parent; }
208 return c;
209 }
210
211 /**
212 Copies all nodes of a red-black tree.
213 @param n the root of a red-black tree
214 @return the root node of a copy of the tree
215 */
216 private static RedBlackTree.Node copy(RedBlackTree.Node n)
217 {
218 if (n == null) { return null; }
219 RedBlackTree.Node newNode = new RedBlackTree.Node();
220 newNode.setLeftChild(copy(n.left));
221 newNode.setRightChild(copy(n.right));
222 newNode.data = n.data;
223 newNode.color = n.color;
224 return newNode;
225 }
226
227 /**
228 Generates the mirror image of a red-black tree
229 @param n the root of the tree to reflect
230 @return the root of the mirror image of the tree
231 */
232 private static RedBlackTree.Node mirror(RedBlackTree.Node n)
233 {
234 if (n == null) { return null; }
235 RedBlackTree.Node newNode = new RedBlackTree.Node();
236 newNode.setLeftChild(mirror(n.right));
237 newNode.setRightChild(mirror(n.left));
238 newNode.data = n.data;
239 newNode.color = n.color;
240 return newNode;
241 }
242
243 /**
244 Makes a full tree of black nodes of a given depth.
245 @param depth the desired depth
246 @return the root node of a full black tree
247 */
248 private static RedBlackTree.Node fullTree(int depth)
249 {
250 if (depth <= 0) { return null; }
251 RedBlackTree.Node r = new RedBlackTree.Node();
252 r.color = RedBlackTree.BLACK;
253 r.setLeftChild(fullTree(depth - 1));
254 r.setRightChild(fullTree(depth - 1));
255 return r;
256 }
257
258 /**
259 Counts the nodes in a tree
260 @param n the root of a red-black tree
261 @return the number of nodes in the tree
262 */
263 private static int count(RedBlackTree.Node n)
264 {
265 if (n == null) { return 0; }
266 else { return 1 + count(n.left) + count(n.right); }
267 }
268
269 /**
270 Populates this tree with the values 0, 1, 2, ... .
271 @param t a red-black tree
272 @return the number of nodes in t
273 */
274 private static int populate(RedBlackTree t)
275 {
276 RedBlackTree.Node[] nodes = getNodes(t);
277 for (int i = 0; i < nodes.length; i++)
278 {
279 nodes[i].data = new Integer(i);
280 }
281 return nodes.length;
282 }
283
284 /**
285 Checks whether a red-black tree is valid and throws an exception if not.
286 @param t the tree to test
287 */
288 public static void checkRedBlack(RedBlackTree t)
289 {
290 checkRedBlack(t.root, true);
291
292 // Check that it's a BST
293 RedBlackTree.Node[] nodes = getNodes(t);
294 for (int i = 0; i < nodes.length - 1; i++)
295 {
296 if (nodes[i].data.compareTo(nodes[i + 1].data) > 0)
297 {
298 throw new IllegalStateException(
299 nodes[i].data + " is larger than " + nodes[i + 1].data);
300 }
301 }
302 }
303
304 /**
305 Checks that the tree with the given node is a red-black tree, and throws an
306 exception if a structural error is found.
307 @param n the root of the subtree to check
308 @param isRoot true if this is the root of the tree
309 @return the black depth of this subtree
310 */
311 private static int checkRedBlack(RedBlackTree.Node n, boolean isRoot)
312 {
313 if (n == null) { return 0; }
314 int nleft = checkRedBlack(n.left, false);
315 int nright = checkRedBlack(n.right, false);
316 if (nleft != nright)
317 {
318 throw new IllegalStateException(
319 "Left and right children of " + n.data
320 + " have different black depths");
321 }
322 if (n.parent == null)
323 {
324 if (!isRoot)
325 {
326 throw new IllegalStateException(
327 n.data + " is not root and has no parent");
328 }
329 if (n.color != RedBlackTree.BLACK)
330 {
331 throw new IllegalStateException("Root "
332 + n.data + " is not black");
333 }
334 }
335 else
336 {
337 if (isRoot)
338 {
339 throw new IllegalStateException(
340 n.data + " is root and has a parent");
341 }
342 if (n.color == RedBlackTree.RED
343 && n.parent.color == RedBlackTree.RED)
344 {
345 throw new IllegalStateException(
346 "Parent of red " + n.data + " is red");
347 }
348 }
349 if (n.left != null && n.left.parent != n)
350 {
351 throw new IllegalStateException(
352 "Left child of " + n.data + " has bad parent link");
353 }
354 if (n.right != null && n.right.parent != n)
355 {
356 throw new IllegalStateException(
357 "Right child of " + n.data + " has bad parent link");
358 }
359 if (n.color != RedBlackTree.RED && n.color != RedBlackTree.BLACK)
360 {
361 throw new IllegalStateException(
362 n.data + " has color " + n.color);
363 }
364 return n.color + nleft;
365 }
366
367 public static void assertEquals(Object expected, Object actual)
368 {
369 if (expected == null && actual != null ||
370 !expected.equals(actual))
371 {
372 throw new AssertionError("Expected " + expected + " but found " + actual);
373 }
374 }
375 }
376
377 /**
378 This class generates permutations of a word.
379 */
380 class PermutationGenerator
381 {
382 private String word;
383
384 /**
385 Constructs a permutation generator.
386 @param aWord the word to permute
387 */
388 public PermutationGenerator(String aWord)
389 {
390 word = aWord;
391 }
392
393 /**
394 Gets all permutations of a given word.
395 */
396 public ArrayList<String> getPermutations()
397 {
398 ArrayList<String> permutations = new ArrayList<String>();
399
400 // The empty string has a single permutation: itself
401 if (word.length() == 0)
402 {
403 permutations.add(word);
404 return permutations;
405 }
406
407 // Loop through all character positions
408 for (int i = 0; i < word.length(); i++)
409 {
410 // Form a simpler word by removing the ith character
411 String shorterWord = word.substring(0, i)
412 + word.substring(i + 1);
413
414 // Generate all permutations of the simpler word
415 PermutationGenerator shorterPermutationGenerator
416 = new PermutationGenerator(shorterWord);
417 ArrayList<String> shorterWordPermutations
418 = shorterPermutationGenerator.getPermutations();
419
420 // Add the removed character to the front of
421 // each permutation of the simpler word,
422 for (String s : shorterWordPermutations)
423 {
424 permutations.add(word.charAt(i) + s);
425 }
426 }
427 // Return all permutations
428 return permutations;
429 }
430 }