Recursive Java Red-Black Tree

Question

I've made an attempt at a recursive Red-Black tree in Java. I realise that some of my code could be condensed but I tried to favour readability with this code as Red-Black trees can be somewhat confusing. The tree is implemented as per the method in Lafore (Data Structures and Algorithms in Java), this implementation produces the same colour and rotation results and also maintains a maximum depth of O(log n)

I'm not sure about some functions (e.g. the isRed() method) and whether this can be done more efficiently or my flow could be more elegant? Any other comments/feedback would be very welcome, thanks.

RBTree.java

/******************************************************************************\
 * Class Name:    RBTree                                                       \
 *                                                                             \
 * @author Thomas McKeesick                                                    \
 * Creation Date: Monday, July 14 2014, 21:27                                  \
 * Last Modified:     Tuesday, January 13 2015, 16:34
 *                                                                             \
 * Class Description: A recursive implementation of a Red-Black Tree,          \
 * fully javadoc'd                                                             \
 ******************************************************************************/

import java.io.PrintWriter;

public class RBTree<T extends Comparable<T>> {

/** Character representing the colour BLACK as 'B' */
private static final char BLACK = 'B';

/** Character representing the colour RED as 'R' */
private static final char RED = 'R';

/** The root node of this tree */
private RBNode<T> root;

/** Public constructor for the tree, initialises the root as null */
public RBTree() {
    root = null;
}

/**
 * Public method to return the root node of the tree
 * @return The root node of the tree
 */
public RBNode<T> getRoot(){
    return root;
}

/**
 * Public method to call the recursive put method to insert data into the tree
 * @param data The data to insert
 */
//TODO change general exception throw to a specific exception
public void insert(T data) throws IllegalArgumentException {
    try {
        root = put( root, data );
        root.setColour( BLACK );
    } catch(IllegalArgumentException e) {
        throw e;
    }
}

/**
 * Private recursive insertion method, searches down the tree until it
 * reaches the insertion point, then recursively rebalances the tree going
 * back up.
 * @param node The root node of the tree initially, then the node that the
 * recursive method is at
 * @param data The data to insert
 * @return The node that has been inserted
 */
//TODO throw better exception
private RBNode<T> put( RBNode<T> node, T data ) throws IllegalArgumentException {
    if( node == null ) {
        RBNode<T> newNode = new RBNode<T>(data);
        return newNode;
    }
    int cmp = data.compareTo( node.getData() );

    if( cmp < 0 ) {
        node.setLeftChild( put( node.getLeftChild(), data ) );
    } else if( cmp > 0 ) {
        node.setRightChild( put( node.getRightChild(), data ) );
    } else {
        throw new IllegalArgumentException("Data already exists in tree: "
                + data.toString());
    }

    //Red-red conflict with outside grandchild
    if( isRed( node.getLeftChild() ) && isRed( node.getLeftChild().getLeftChild() ) ) {
        node.setColour( RED );
        node.getLeftChild().setColour( BLACK );
        node = rightRotation(node);
    }

    //Red-red conflict with right-outside grandchild
    if( isRed( node.getRightChild() ) && isRed( node.getRightChild().getRightChild() ) ) {
        node.setColour( RED );
        node.getRightChild().setColour( BLACK );
        node = leftRotation(node);
    }

    //Red-red conflict with left-right inside grandchild
    if( isRed( node.getLeftChild() ) && isRed( node.getLeftChild().getRightChild() ) ) {
        node.setColour( RED );
        node.getLeftChild().getRightChild().setColour( BLACK );
        node.setLeftChild( leftRotation(node.getLeftChild() ) );
        node = rightRotation( node );
    }

    //Red-red conflict with right-left inside grandchild
    if( isRed( node.getRightChild() ) && isRed( node.getRightChild().getLeftChild() ) ) {
        node.setColour( RED );
        node.getRightChild().getLeftChild().setColour( BLACK );
        node.setRightChild( rightRotation( node.getRightChild() ) );
        node = leftRotation( node );
    }

    colourFlip(node);
    return node;
}

/**
 * Searches for the supplied data by in-order traversal
 * @param data The data to search for
 * @return The node that contains the data if it is found (and not marked as
 * deleted), null otherwise
 */
public RBNode<T> contains(T data) {
    RBNode<T> current = root;
    while( data.compareTo(current.getData()) != 0 ) {
        if( data.compareTo(current.getData()) < 0 ) {
            current = current.getLeftChild();
        } else {
            current = current.getRightChild();
        }
        if( current == null || current.isDeleted() ) {
            return null;
        }
    }
    return current;
}

/**
 * Public method to remove a node from the tree. Calls the delete method
 * from the node which changes its deleted boolean to true, does not actually
 * perform a deletion
 * @param data The data to remove from the tree
 * @return True if the delete was successful (the element exits in the tree),
 * and false otherwise
 */
//TODO throw better exception
public boolean removeElement( T data ) throws Exception {
    RBNode<T> node = contains( data );

    if( node != null ) {
        node.delete();
        return true;
    } else {
        throw new Exception("Data does not exist: " + data.toString());
    }
}

/***************************************\
 *         COLOUR METHODS               |
 ***************************************/

/**
 * Public method to determine whether or not a node is red
 * @param node The node to colour-check
 * @return false if BLACK, true if RED
 */
public boolean isRed( RBNode<T> node ) {
    if( node == null ) {
        return false;
    }
    return node.getColour() == RED;
}

/**
 * Private method to perform colour flip on a parent node and
 * its two children. Only called if the parent is black
 * and both children are red. If the parent node is the root node,
 * then it stays as black
 * @param parent The parent node to colour flip
 */
private void colourFlip( RBNode<T> parent ) {
    if( parent.getRightChild() == null ||
            parent.getLeftChild() == null ) {
        return;
    }

    if( !isRed(parent) && isRed(parent.getRightChild())
    && isRed(parent.getLeftChild()) ) {
        if( parent != root ) {
            parent.setColour( RED );
        }
        parent.getRightChild().setColour( BLACK );
        parent.getLeftChild().setColour( BLACK );
    }
}

/***************************************\
 *      ROTATION METHODS                |
 ***************************************/

/**
 * Private method to perform a right rotation around a supplied grandparent node
 * @param grandparent The node to rotate around
 * @return The node now in place of the original grandparent
 */
private RBNode<T> rightRotation( RBNode<T> grandparent ) {
    RBNode<T> parent = grandparent.getLeftChild();
    RBNode<T> rightChildOfParent = parent.getRightChild();
    parent.setRightChild( grandparent );
    grandparent.setLeftChild( rightChildOfParent );
    return parent;
}

/**
 * Private method to perform a left rotation around a supplied grandparent
 * node
 * @param grandparent The node to rotate around
 * @return The node now in place of the original grandparent
 */
private RBNode<T> leftRotation( RBNode<T> grandparent ) {
    RBNode<T> parent = grandparent.getRightChild();
    RBNode<T> leftChildOfParent = parent.getLeftChild();
    parent.setLeftChild( grandparent );
    grandparent.setRightChild( leftChildOfParent );
    return parent;
}

/***************************************\
 *      TRAVERSAL METHODS               |
 ***************************************/

/**
 * Public method called to display the tree, currently in-order traversal
 * @param p The PrintWriter object to write to
 */
public void displayElements(PrintWriter p) {
    displaySubtreeInOrder(root, p);
}

/**
 * Private in-order traversal method called by the displayElements()
 * method.
 * @param current The current node to print
 * @param p The PrintWriter to write to
 */
private void displaySubtreeInOrder(RBNode<T> current, PrintWriter p) {
    if( current != null ) {
        displaySubtreeInOrder( current.getLeftChild(), p );
        p.println( "Data is " + current.getData()
                + "Node colour: " + current.getColour() );
        displaySubtreeInOrder( current.getRightChild(), p );
    }
}

/**
 * Public method to print the tree in human-readable form. Calls the display
 * method within the RBNode class and prints output to the console
 */
public void printStructure() {
    if(root == null) {
        System.out.println("null");
    } else {
        System.out.println("*****************************************");
        root.display(0);
        System.out.println("*****************************************");
    }
    System.out.println();
}
}

RBNode.java

/*
 * Class Name:    RBNode
 *
 * @author Thomas McKeesick
 * Creation Date: Monday, July 14 2014, 20:37
 * Last Modified: Thursday, January 08 2015, 08:00
 *
 * Class Description: The Red-Black Node class file,
 *                    all functionality javadoc'd
 */

public class RBNode<T extends Comparable< T >> {

/** Final char variable declaring RED as 'R' */
private final static char RED = 'R';

/** Final char variable declaring BLACK as 'B' */
private final static char BLACK = 'B';

/** The data contained in this node must extend the java Comparable interface */
private T data;

/** The colour of this node, either RED or BLACK */
private char colour;

/** The right child of this node */
private RBNode<T> rightChild;

/** The left child of this node */
private RBNode<T> leftChild;

/** Boolean that is true if the node has been deleted, false otherwise */
private boolean deleted;

/**
 * Public constructor that creates a new RBNode, initiates the colour as red
 * @param data The data to be stored in the node
 */
public RBNode(T data) {
    this.data = data;
    colour = RED;
    rightChild = null;
    leftChild = null;
    deleted = false;
}

/************************************\
 *          SETTER METHODS           |
 ************************************/

/**
 * Replaces the current node data with new data
 * @param data The new data to replace the old
 */
public void setData(T data){
    this.data = data;
}

/**
 * Performs a colour switch
 * @param c The new colour to switch to
 * @return True if the switch is successful, false if c is invalid
 * or is the same as the current colour
 */
public boolean setColour( char c ) {
    //If the colour is black or red (a legal input), and it is also
    //not the same as the current colour, change the colour
    if( ( c == RED || c == BLACK ) && c != colour ) {
        colour = c;
        return true;
    }
    return false;
}

/**
 * Public method to set a node as the left child of this node
 * @param node The node to insert as the left child
 */
public void setLeftChild( RBNode<T> node ) {
    leftChild = node;
}

/**
 * Public method to set a node as the right child of this node
 * @param node The node to insert as the right child
 */
public void setRightChild( RBNode<T> node ) {
    rightChild = node;
}

/**
 * Public method to delete a node. Does not actually remove the
 * node, rather sets the 'deleted' boolean to true. If a deleted
 * node is discovered by the RBTree contains method, null is returned
 */
public void delete() {
    deleted = true;
}

/************************************\
 *          GETTER METHODS           |
 ************************************/

/**
 * Public method to return the data stored in the node
 * @return The data stored in the node
 */
public T getData() {
    return data;
}

/**
 * Public method to return the colour of the node
 * @return The colour of the node
 */
public char getColour() {
    return colour;
}

/**
 * Public method to return the left child of the node
 * @return The left child of the node
 */
public RBNode<T> getLeftChild() {
    return leftChild;
}

/**
 * Public method to return the right child of the node
 * @return The right child of the node
 */
public RBNode<T> getRightChild() {
    return rightChild;
}

/**
 * Public method to return whether or not this node has been deleted.
 * Used by the RBTree contains method.
 * @return True if the node has been deleted, false otherwise
 */
public boolean isDeleted() {
    return deleted;
}

/**
 * Public method to display the node and its subtree.
 * @param n The level of the node and used for the indentation
 */
public void display(int n) {
    String indent = "- ";

    //Print the indents for this level
    for(int i = 1; i <= n; i++) {
        System.out.print(indent);
    }
    //Print the node contents
    System.out.println("ROOT: " + data + ", colour: " + colour);
    //Indent
    for(int i = 1; i <= n; i++) {
        System.out.print(indent);
    }
    //Print the left child of the node
    System.out.println("LEFT");
    if( leftChild == null) {
        for(int i = 1; i <= n+1; i++) {
            System.out.print(indent);
        }
        System.out.println("null");
    } else {
        leftChild.display(n+1);
    }
    //Indent
    for(int i = 1; i <= n; i++) {
        System.out.print(indent);
    }

    //Print the right child of the node
    System.out.println("RIGHT");
    if( rightChild == null) {
        for(int i = 1; i <= n+1; i++) {
            System.out.print(indent);
         }
        System.out.println("null");
    } else {
        rightChild.display(n+1);
    }
}
}

Answer 1

Some of your commenting is a bit excessive. JavaDoc comments in particular are aimed at generating automatic API documentation and shouldn't be necessary for private functions unless they're very complex and you need to keep a maintainer educated. Generally JavaDocs should be documenting specific behaviour. Same goes for private fields- try to self-document with good variable names, rather than relying on comments.

In particular, the duplication of the R/B definition between the two classes is a code smell and you should be scoping it so that it's accessible from both classes. More fundamentally, the choice of a char to store this data is rather misleading as it suggests that more colours may be arbitrarily introduced! In some cases of a limited set of valid values, an enum is both appropriate and descriptive, but for a case as simple as this, a boolean would work.

For readability, using constants like public static final boolean RED = true; and public static final boolean BLACK = false; would allow you to do away with isRed(...) and do stuff like node.getColor() == RED. However, the most OO appropriate way would be to just have the methods isRed() and isBlack() on the node object. setRed() and setBlack() wouldn't go amiss, you could make a case for toggleColor() if there are occasions you're not assigning the colour but switching it.

Your exceptions are incredibly strange and I suspect you're using it to subvert the recursive nature of your function. This can become an anti-pattern, such as using exceptions for flow control. Inserting into a tree that already contains an item of data should be treated as an idempotent operation and therefore a success; hardly an illegal argument. removeElement(...) is worse as it promises to return a boolean, but it returns true if successful and throws an Exception if not (generally speaking, you should never throw the Exception class- always find a suitable subclass or, if one doesn't exist, make your own), so the docs are lying! A fantastic improvement to this class would be to actually implement the Set interface and use that contract to guide at what sort of behaviour would be 'nice'.

As per the Set interface, looking to indicate whether or not the data previously existed (say, we modify insert(T data) to return a boolean to that effect), you're now running against an issue with recursive algorithms: the return pathway of information is very narrow as you only get one return type. None of the options are all that pleasant- you could make a custom object that gets passed around from invocation to invocation and has fields for all the information you wish to pass around, but that could lead to thrashing lots of objects in accordance with how much recursion you've done. In this case, a simple flag field will suffice, but that in turn highlights the thread-safety of an RBTree instance.

As it turns out, the operations on your tree could cause some very strange results if invoked in a multi-threaded environment. This is not the end of the world, but definitely something that should be documented in your JavaDocs; the core Java Collection data types typically do not provide thread-safe implementations, but are documented as doing so (synchronization can be achieved using wrapper classes).

Answer 2

Node can be a private nested class of RBTree. There is no need to access the nodes of the tree and allow the user of the code to invalidate the RB invariants.

Color can be just a boolean with true being RED and false being BLACK.

If you delete a node then you also delete all its children.

Answer 3

}
}

This is always a bad sign: something is off with your indentation.

 Class Description: A recursive implementation of a Red-Black Tree, fully javadoc'd

Great, we love JavaDoc! It's very nice that you're documenting all public members. Private members don't (shouldn't) need them though.

Comments (//) however, are problematic. They're everywhere, and are for the most part useless redundant clutter that distract the reader/maintainer from the actual code.

Avoid comments that say "what", let the code speak for itself, and use comments when the code isn't clear about "why".

Answer 4

You should use enum for storing RED and BLACK Node Colors.

enum NodeColor {RED, BLACK;}

There is no need of comments such as below if you use good variable names and method names.

/** Character representing the colour BLACK as 'B' */
private static final char BLACK = 'B';

/** Character representing the colour RED as 'R' */
private static final char RED = 'R';

/** The root node of this tree */
private RBNode<T> root;

/** Public constructor for the tree, initialises the root as null */
public RBTree() {
    root = null;
}

deleted variable in RBNode can be names as isDeleted.

Instead of using constructors you could initialize variables inline. It's much more readable.

private T data;
private NodeColor colour = NodeColor.RED;
private RBNode<T> rightChild = null;
private RBNode<T> leftChild = null;
private boolean isDeleted = false;

public RBNode(T data) {
    this.data = data;
}