Added RB tree tests

williamfiset · williamfiset · commit b15b6e273305 · 2017-10-29T16:18:29.000-07:00
diff --git a/RedBlackTree/RedBlackTree.java b/RedBlackTree/RedBlackTree.java
@@ -210,7 +210,7 @@ private void insertionRelabel(Node node) {
       }
 
     }
-    display();
+    // display();
     insertionRelabel(grandParent);
     
   }
diff --git a/RedBlackTree/tests/RedBlackTreeTest.java b/RedBlackTree/tests/RedBlackTreeTest.java
@@ -26,7 +26,7 @@ public void testNullInsertion() {
   public void testTreeContainsNull() {
     assertFalse(tree.contains(null));
   }
-/*
+
   @Test
   public void testLeftLeftRotation() {
 
@@ -118,11 +118,12 @@ public void testRightRightRotation() {
     assertCorrectParentLinks(tree.root, null);
 
   }
-  */
 
   @Test
-  public void testLeftRedUncleCase() {
+  public void testLeftUncleCase() {
     
+    /* Red left uncle case. */
+
     tree.insert(1);
     tree.insert(2);
     tree.insert(3);
@@ -141,7 +142,9 @@ public void testLeftRedUncleCase() {
     assertNull(tree.root.right.left);
     assertNullChildren(tree.root.left, tree.root.right.right);
     assertCorrectParentLinks(tree.root, null);
-    // System.out.println("====================================");
+    
+    /* Black left uncle case. */
+
     tree.insert(5);
 
     assertEquals(2, tree.root.value.intValue());
@@ -159,6 +162,49 @@ public void testLeftRedUncleCase() {
 
   }
 
+  @Test
+  public void testRightUncleCase() {
+    
+    /* Red right uncle case. */
+
+    tree.insert(2);
+    tree.insert(3);
+    tree.insert(4);
+    tree.insert(1);
+
+    assertEquals(3, tree.root.value.intValue());
+    assertEquals(2, tree.root.left.value.intValue());
+    assertEquals(4, tree.root.right.value.intValue());
+    assertEquals(1, tree.root.left.left.value.intValue());
+
+    assertEquals(RedBlackTree.BLACK, tree.root.color);
+    assertEquals(RedBlackTree.BLACK, tree.root.left.color);
+    assertEquals(RedBlackTree.BLACK, tree.root.right.color);
+    assertEquals(RedBlackTree.RED, tree.root.left.left.color);
+
+    assertNull(tree.root.left.right);
+    assertNullChildren(tree.root.right, tree.root.left.left);
+    assertCorrectParentLinks(tree.root, null);
+
+    /* Black right uncle case. */
+
+    tree.insert(0);
+
+    assertEquals(3, tree.root.value.intValue());
+    assertEquals(1, tree.root.left.value.intValue());
+    assertEquals(4, tree.root.right.value.intValue());
+    assertEquals(0, tree.root.left.left.value.intValue());
+    assertEquals(2, tree.root.left.right.value.intValue());
+
+    assertEquals(RedBlackTree.BLACK, tree.root.color);
+    assertEquals(RedBlackTree.BLACK, tree.root.left.color);
+    assertEquals(RedBlackTree.BLACK, tree.root.right.color);
+    assertEquals(RedBlackTree.RED, tree.root.left.left.color);
+    assertEquals(RedBlackTree.RED, tree.root.left.right.color);
+    assertCorrectParentLinks(tree.root, null);
+
+  }
+
   static void assertNullChildren(RedBlackTree.Node... nodes) {
     for (RedBlackTree.Node node : nodes) {
       assertNull(node.left);

Original file line number	Diff line number	Diff line change
`@@ -210,7 +210,7 @@ private void insertionRelabel(Node node) {`
`210`	`210`	`}`
`211`	`211`
`212`	`212`	`}`
`213`		`- display();`
	`213`	`+ // display();`
`214`	`214`	`insertionRelabel(grandParent);`
`215`	`215`
`216`	`216`	`}`