***************
Red-Black Trees
***************



*  In this lab we continue implementing our own data structure library.
*  You will implement the following UML in Java:

.. figure:: ./uml_rbt.drawio.png
    :align: center

Red-Black Trees - Start
=======================

*  Finish the class :code:`BinarySearchTreeWithRotate` witht the following methods:

   *  :code:`rotateRight(E)`
   *  :code:`rotateLeft(E)`

.. literalinclude:: ../../topics/trees/BinarySearchTreeWithRotate.java
    :language: java
    :linenos:
    :lines: 1-21, 26-38, 43-45


Red-Black Trees - class
=======================

1. Create the structure of the **generic** class :code:`RedBlackTree`.
   
   *  It should inherit from :code:`BinarySearchTreeWithRotate`.

.. literalinclude:: ../../topics/trees/RedBlackTree.java
    :language: java
    :linenos:
    :lines: 1-8, 168

2. Create the generic and static class :code:`RedBlackNode`.

   *  It should inherit from :code:`Node`.
   *  It contains only three constant data field.
   *  Implement the constructor.

.. literalinclude:: ../../topics/trees/RedBlackTree.java
    :language: java
    :linenos:
    :lines: 14-18, 24-28, 31-39, 45-47

3. Now finish the class :code:`RedBlackTree`.

.. literalinclude:: ../../topics/trees/RedBlackTree.java
    :language: java
    :linenos:
    :lines: 1-8, 52-59, 69-77, 150-157,166-168

Red-Black Trees - Test
======================

You can use the following function to test your code:

.. code-block:: java
    :linenos:

    public static void rbt_tree(){
        RedBlackTree<String> testOne = new RedBlackTree<String>();
        testOne.add("The");
        testOne.add("quick");
        testOne.add("brown");
        testOne.add("fox");
        testOne.add("apple");
        testOne.add("cat");
        testOne.add("hat");
        System.out.println(testOne.toString());

        RedBlackTree<Integer> testTwo = new RedBlackTree<Integer>();
        testTwo.add(30);
        testTwo.add(40);
        testTwo.add(15);
        testTwo.add(25);
        testTwo.add(90);
        testTwo.add(80);
        testTwo.add(70);
        testTwo.add(85);
        testTwo.add(15);
        testTwo.add(72);
        System.out.println(testTwo.toString());

        RedBlackTree<String> testThree = new RedBlackTree<String>();
        testThree.add("Now");
        testThree.add("is");
        testThree.add("time");
        testThree.add("for");
        testThree.add("all");
        testThree.add("good");
        testThree.add("men");
        testThree.add("to");
        testThree.add("come");
        testThree.add("to");
        testThree.add("the");
        testThree.add("aid");
        testThree.add("of");
        testThree.add("the");
        testThree.add("party");
        System.out.println(testThree.toString());


**ENSURE WE HAVE RECORDED YOUR COMPLETION. FAILURE TO DO SO WILL RESULT IN A GRADE OF 0!**