Untitled
unknown
java
2 months ago
5.7 kB
7
Indexable
@Test public void testRoot() { RedBlackTree<Integer> rbt = new RedBlackTree<>(); rbt.insert(1); Assertions.assertTrue(!rbt.getRoot().isRed()); } @Test public void testSimple() { RedBlackTree<Integer> rbt = new RedBlackTree<>(); rbt.insert(2); rbt.insert(1); rbt.insert(3); Assertions.assertTrue(!rbt.getRoot().isRed()); Assertions.assertTrue(rbt.getRoot().childLeft().isRed()); Assertions.assertTrue(rbt.getRoot().childRight().isRed()); } @Test public void testRedUncle() { // CASE 1: uncle is red // setup RedBlackTree<Integer> rbt = new RedBlackTree<>(); rbt.insert(2); rbt.insert(1); rbt.insert(3); // check initial state Assertions.assertEquals("[ 2(b), 1(r), 3(r) ]", rbt.getRoot().toLevelOrderString()); // insert -5 rbt.insert(-5); // nonsolution: two consecutive red nodes Assertions.assertNotEquals("[ 2(b), 1(r), 3(r), -5(r) ]", rbt.getRoot().toLevelOrderString()); // solution: recoloring Assertions.assertEquals("[ 2(b), 1(b), 3(b), -5(r) ]", rbt.getRoot().toLevelOrderString()); } @Test public void testBlackUncleAndLeftLeft() { // CASE 2a: uncle is black, and parent and newNode are aligned // left-left // setup RedBlackTree<Integer> rbt = new RedBlackTree<>(); rbt.insert(100); rbt.insert(50); rbt.insert(150); rbt.insert(10); // check initial state Assertions.assertEquals("[ 100(b), 50(b), 150(b), 10(r) ]", rbt.getRoot().toLevelOrderString()); // insert 0 rbt.insert(0); // nonsolution: two consecutive red nodes Assertions.assertNotEquals("[ 100(b), 50(b), 150(b), 10(r), 0(r) ]", rbt.getRoot().toLevelOrderString()); // solution: rotation and recoloring Assertions.assertEquals("[ 100(b), 10(b), 150(b), 0(r), 50(r) ]", rbt.getRoot().toLevelOrderString()); } @Test public void testBlackUncleAndRightRight() { // CASE 2a: uncle is black, and parent and newNode are aligned // right-right // setup RedBlackTree<Integer> rbt = new RedBlackTree<>(); rbt.insert(100); rbt.insert(50); rbt.insert(150); rbt.insert(200); // check initial state Assertions.assertEquals("[ 100(b), 50(b), 150(b), 200(r) ]", rbt.getRoot().toLevelOrderString()); // insert 250 rbt.insert(250); // nonsolution: two consecutive red nodes Assertions.assertNotEquals("[ 100(b), 50(b), 150(b), 200(r), 250(r) ]", rbt.getRoot().toLevelOrderString()); // solution: rotation and recoloring Assertions.assertEquals("[ 100(b), 50(b), 200(b), 150(r), 250(r) ]", rbt.getRoot().toLevelOrderString()); } @Test public void testBlackUncleAndLeftRight() { // CASE 2b: uncle is black, and parent and newNode are aligned // left-right // setup RedBlackTree<Integer> rbt = new RedBlackTree<>(); rbt.insert(50); rbt.insert(0); // check initial state Assertions.assertEquals("[ 50(b), 0(r) ]", rbt.getRoot().toLevelOrderString()); // insert 25 rbt.insert(25); // nonsolution: two red nodes Assertions.assertNotEquals("[ 50(b), 0(r), 25(r) ]", rbt.getRoot().toLevelOrderString()); // solution: rotation and recoloring Assertions.assertEquals("[ 25(b), 0(r), 50(r) ]", rbt.getRoot().toLevelOrderString()); } @Test public void testBlackUncleAndRightLeft() { // CASE 2b: uncle is black, and parent and newNode are aligned // right-left // setup RedBlackTree<Integer> rbt = new RedBlackTree<>(); rbt.insert(50); rbt.insert(100); // check initial state Assertions.assertEquals("[ 50(b), 100(r) ]", rbt.getRoot().toLevelOrderString()); // insert 75 rbt.insert(75); // nonsolution: two red nodes Assertions.assertNotEquals("[ 50(b), 100(r), 75(r) ]", rbt.getRoot().toLevelOrderString()); // solution: rotation and recoloring Assertions.assertEquals("[ 75(b), 50(r), 100(r) ]", rbt.getRoot().toLevelOrderString()); } @Test public void testComplex() { // example from PraireLearn quiz RedBlackTree<Character> rbt = new RedBlackTree<>(); for (char c : "QIUDLSYVZ".toCharArray()) { rbt.insert(c); } // check initial state Assertions.assertEquals("[ Q(b), I(b), U(r), D(r), L(r), S(b), Y(b), V(r), Z(r) ]", rbt.getRoot().toLevelOrderString()); // insert P rbt.insert('P'); Assertions.assertEquals("[ Q(b), I(r), U(r), D(b), L(b), S(b), Y(b), P(r), V(r), Z(r) ]", rbt.getRoot().toLevelOrderString()); } @Test public void testGrandparentRecurse() { // tests that, when the uncle is red, the algorithm recurses on the grandparent // aswell // if not, this test will fail // setup RedBlackTree<Integer> rbt = new RedBlackTree<>(); for (int i : new int[] { 50, 25, 75, 9, 35, 0, 10 }) { rbt.insert(i); } // check initial state Assertions.assertEquals("[ 50(b), 25(r), 75(b), 9(b), 35(b), 0(r), 10(r) ]", rbt.getRoot().toLevelOrderString()); // insert 5 rbt.insert(5); Assertions.assertEquals("[ 25(b), 9(r), 50(r), 0(b), 10(b), 35(b), 75(b), 5(r) ]", rbt.getRoot().toLevelOrderString()); }
Editor is loading...
Leave a Comment