RedBlackTreeTester.java.html

  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  }