Untitled

    @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());
    }