Added RB tree tests

williamfiset · williamfiset · commit dcfa1f2978f7 · 2017-10-29T16:08:45.000-07:00
diff --git a/RedBlackTree/RedBlackTree.java b/RedBlackTree/RedBlackTree.java
@@ -153,6 +153,7 @@ private void insertionRelabel(Node node) {
     // Root node case.
     if (parent == null) {
       node.color = BLACK;
+      root = node;
       return;
     }
 
@@ -208,12 +209,8 @@ private void insertionRelabel(Node node) {
         grandParent = rightRightCase(grandParent);
       }
 
-      if (grandParent.parent == null) {
-        root = grandParent;
-      }
-
     }
-
+    display();
     insertionRelabel(grandParent);
     
   }
@@ -250,6 +247,8 @@ private Node rightRotate(Node parent) {
     child.parent = grandParent;
     parent.parent = child;
 
+    updateParentChildLink(grandParent, parent, child);
+
     return child;
   }
 
@@ -262,22 +261,24 @@ private Node leftRotate(Node parent) {
     child.left = parent;
     child.parent = grandParent;
     parent.parent = child;
+
+    updateParentChildLink(grandParent, parent, child);
     
     return child;
   }
 
   // Sometimes the left or right child node of a parent changes and the
   // parent's reference needs to be updated to point to the new child. 
   // This is a helper method to do just that.
-  // private void updateParentChildLink(Node parent, Node oldChild, Node newChild) {
-  //   if (parent != null) {
-  //     if (parent.left == oldChild) {
-  //       parent.left = newChild;
-  //     } else {
-  //       parent.right = newChild;
-  //     }
-  //   }
-  // }
+  private void updateParentChildLink(Node parent, Node oldChild, Node newChild) {
+    if (parent != null) {
+      if (parent.left == oldChild) {
+        parent.left = newChild;
+      } else {
+        parent.right = newChild;
+      }
+    }
+  }
 
   // Helper method to find the leftmost node (which has the smallest value)
   private Node findMin(Node node) {
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,6 +118,7 @@ public void testRightRightRotation() {
     assertCorrectParentLinks(tree.root, null);
 
   }
+  */
 
   @Test
   public void testLeftRedUncleCase() {
@@ -140,7 +141,7 @@ public void testLeftRedUncleCase() {
     assertNull(tree.root.right.left);
     assertNullChildren(tree.root.left, tree.root.right.right);
     assertCorrectParentLinks(tree.root, null);
-
+    // System.out.println("====================================");
     tree.insert(5);
 
     assertEquals(2, tree.root.value.intValue());
