| | |
Apart from the restrictions related to keeping perfect black balance, keeping no more than two nodes "glued together", etc., the only real structural difference between a left-leaning red-black tree and a binary search tree is the presence of "red links".
As such, we cannibalize much of the structure and methods of our binary search tree class in the implementation of a class to represent red-black trees.
Note however, our binary search tree class did not use a separate object for its links -- these were just references to other nodes. As such, we don't have a link object to which we might add some color instance variable, that can then take on the values "red" and "black".
Instead, realize that every such reference (as long as it is not null) refers to some node. Fortunately, these nodes are objects to which we can add instance variables. Given this, let us store the color information for the link in the node so referenced.
To do this, we alter the inner class Node used by our binary search tree class in the following way:
private static final boolean RED = true; private static final boolean BLACK = false; private class Node { private Key key; private Value val; private Node left; private Node right; boolean color; // color of parent link private int count; public Node(Key key, Value val) { this.key = key; this.val = val; } }
Adding the following method will be convenient as well, mostly for the sake of readability of later methods -- but it also establishes that null links should be considered black.
private boolean isRed(Node n) {
if (n == null) return false;
return n.color == RED;
}
One consequence of this approach is that the root node must always be black. Think about what would be implied otherwise: If we stored the color red in the root node, that would say that the root is "glued" to the node immediately above it -- but there is no node above the root!
Given that the edge color information for our red-black trees is actually stored in the nodes, perhaps the below image would be a more accurate representation for our red black trees -- although they are rarely drawn in this way:
