Recursive Java Red-Black Tree

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> {

/** 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 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 getRoot(){
return root;
}

/**
* Public method to call the recursive

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).

StackExchange Code Review Q#78131, answer score: 4