6. Red-Black Trees

• In this lab we continue implementing our own data structure library.

• You will implement the following UML in Java:

6.1. Red-Black Trees - Start

• Finish the class BinarySearchTreeWithRotate witht the following methods:

  • rotateRight(E)

  • rotateLeft(E)

package trees;

/**
 * This class extends the BinarySearchTree by adding the rotate operations.
 * Rotation will change the balance of a search tree while preserving the search tree property.
 * Used as a common base class for self‐balancing trees.
 * @param <E> type of the data contained in the tree
 */
public class BinarySearchTreeWithRotate<E extends Comparable<E>> extends BinarySearchTree<E>{

    /**
     * Method to perform a right rotation.
     * @post root.right is the root of a binary search tree,
     *       root.right.right is raised one level,
     *       root.right.left does not change levels,
     *       root.left is lowered one level,
     *       the new root is returned.
     * @param root is the root of a binary search tree
     * @return The new root of the rotated tree
     */
    protected Node<E> rotateRight(Node<E> root) {
    }

    /**
     * Method to perform a left rotation.
     * @post root.left is the root of a binary search tree,
     *       root.left.left is raised one level,
     *       root.left.right does not change levels,
     *       root.right is lowered one level,
     *       the new root is returned.
     * @param root is the root of a binary search tree
     * @return The new root of the rotated tree
     */
    protected Node<E> rotateLeft(Node<E> root) {
    }

}

6.2. Red-Black Trees - class

1. Create the structure of the generic class RedBlackTree.

   • It should inherit from BinarySearchTreeWithRotate.

package trees;

/**
 * Self-balancing binary search tree using algorithm defined by
 * Leo Guibas and Robert Sedgewick.
 * @param <E> Type contained in the tree.
 */
public class RedBlackTree<E extends Comparable<E>> extends BinarySearchTreeWithRotate<E> {
}

2. Create the generic and static class RedBlackNode.

   • It should inherit from Node.

   • It contains only three constant data field.

   • Implement the constructor.

    /**
     * Class to represent a Red-Black node
     * @param <E> The data type of items stored in the node. Must be Comparable
     */
    private static class RedBlackNode<E> extends Node<E> {
        /**
         * Constructor to create a node with the default color of red with the given data
         * @param data The data item to be stored in the node
         */
        public RedBlackNode(E data) {
        }

        //Methods
        /**
         * Return a String representation of the node
         * @return A String representation of the node
         */
        @Override
        public String toString(){
        }

    }

3. Now finish the class RedBlackTree.

package trees;

/**
 * Self-balancing binary search tree using algorithm defined by
 * Leo Guibas and Robert Sedgewick.
 * @param <E> Type contained in the tree.
 */
public class RedBlackTree<E extends Comparable<E>> extends BinarySearchTreeWithRotate<E> {
    /**
     * Add start method
     * @param item The new element.
     * @return true if the object is inserted;
     *         false if the object already exists in the tree.
     */
    @Override
    public boolean add(E item){
    }

    /**
     * Recursive add method
     * @param localRoot The local root of the Red Black Tree
     * @param item The item to be inserted
     * @return The new local root
     */
    private Node<E> add(RedBlackNode<E> localRoot, E item){
    }

    /**
     * Check to see whether both children of the given node are red.
     * If so, make them black and change the localRoot's color to red.
     * @param localRoot The node to check whether both children are red or not
     */
    private void moveBlackDown(RedBlackNode<E> localRoot){
    }

}

6.3. Red-Black Trees - Test

You can use the following function to test your code:

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!