Red-Black trees are an attempt to create balanced binary trees. The shape of a standard binary tree is determined by the order in which data is inserted. If the data is encountered in random order, the resulting tree will have a fairly uniform path length (distance from the root to a leaf) for each leaf. When a data set that is already ordered is inserted into a binary tree, the resulting tree is actually a list (all of the items either are found by right branchs or left data branches.
Many of the structures created to maintain a balanced tree are not binary trees. Red-Black trees are binary trees which are relatively balanced. The main difference between the standard tree and the Red-Black tree is the insert algorithm. We would hope to implement these trees with the following interface.
template < class Type>
class RedBlackTree :public Tree< Type>
{
public:
void insert (const Type &t);
};
The nodes in a binary tree are binary nodes, so might have the interface given below.
template <class Type>
class RedBlackNode :public Node< Type>
{
friend class RedBlackTree;
public:
enum Color {RED, BLACK};
...
private:
Color _color;
};
While this looks like a reasonable solution to the problem from a theoretical and implementation standpoint, one look at the internally used insert function shows us a problem.
template < class Type>
int RedBlackTree< Type>::insert(const Type &key,
TreeNode< Type>* &parent,
TreeNode< Type>* & current)
{
// The insert section of doInsert
Side pDirect; //branch taken from parent
// determine which direction this insert comes from
if (!parent) //no parent no direction
pDirect = none;
else if (left(parent)==current) //current left branch from parent
pDirect = Left;
else //current right branch from parent
pDirect = Right;
Side direct; //branch taken from current
TreeNode *child;
if (!current) //no current then insert here
{
current = new RedBlackNode(key);
if (!parent)// found root node, it must be black
RBPointer(current)->color = black;
}
else if (current->_data > key) //should you insert in left subtree?
{
if (insert(key,current,current->_left)) // if so - do it
{
direct = Left; //record that you branched left
child = current->_left; //record child as left branch (may be new)
}
else // insert failed
return 0;
}
else if (current->_data < key) //should you insert in right subtree?
{
if (insert(key,current,current->_right))// if so - do it
{
direct = Right; //record that you branched right
child = current->_right; //record the child as right branch (may be new)
}
else
return 0; //insert failed
}
else //must have found the item you are trying to insert
return 0; //don't insert and insert fails
// time to balance the tree
balance(current,parent,child,direct,pDirect);
if (!parent) //current is the root therefore is black
RBPointer(current)->color = black;
return 1;
}
While the details of this function may be a bit complicated, the problem is simple to understand - the compiler will give you errors. Recall that _data, _left and _right are private members of Node. We can refer to them in Tree because it is a friend of Node. RedBlackTree is not a friend of Node, so it cannot access _data, _left or _right.
There is no need to give access to the data, since we could have provided virtual functions goLeft and goRight in Node that do comparisons with the data
virtual int goRight(Type item){return _dataitem;}
One solution that will maintain some protection, but can be critized for allowing access to private data members by non-friends is to provide protected functions in Tree to the branches.
protected: static TreeNode*& left(TreeNode *p){return p->_left;} static TreeNode *& right(TreeNode *p){return p->_right;} TreeNode *_root; };
With this solution the insert function is converted to the following.
template < class Type>
int RedBlackTree< Type>::insert( const Type &key,
TreeNode< Type>* &parent,
TreeNode< Type>* & current)
{
// The insert section of doInsert
Side pDirect; //branch taken from parent
// determine which direction this insert comes from
if (!parent) //no parent no direction
pDirect = none;
else if (left(parent)==current) //current left branch from parent
pDirect = Left;
else //current right branch from parent
pDirect = Right;
Side direct; //branch taken from current
TreeNode *child;
if (!current) //no current then insert here
{
current = new RedBlackNode< Type>(key);
if (!parent) // found root node, it must be black
RBPointer(current)->color = black;
}
else if (current->goLeft(key)) //should you insert in left subtree?
{
if (doInsert(key,current,left(current))) // if so - do it
{
direct = Left; //record that you branched left
child = left(current); //record child as left branch (may be new)
}
else // insert failed
return 0;
}
else if (current->goRight(key)) //should you insert in right subtree?
{
if (doInsert(key,current,right(current))) // if so - do it
{
direct = Right; //record that you branched right
child = right(current); //record the child as right branch (may be new)
}
else
return 0; //insert failed
}
else //must have found the item you are trying to insert
return 0; //don't insert and insert fails
// time to balance the tree
balance(current,parent,child,direct,pDirect);
if (!parent) //current is the root therefore is black
RBPointer(current)->color = black;
return 1;
}
While this solution works and has been suggested in many of the books covering this subject, the best solution would be to nest the class Node in the class Tree as a protected class. You have seen some nested classes in the RcPointer, Array and RcList classes. The problem with implementing the Tree with the node class nested is that current compilers will not compile functions that use nested template classes.