bslalg_rbtreeutil

Detailed Description

Outline

• Purpose
• Classes
• Description
  • Summary
    • Navigation
    • Modification
    • Utility
    • Testing
  • Well-Formed RbTreeAnchor Objects
    • The Sentinel Node
  • Usage
    • Example 1: Creating and Using a Tree with RbTreeUtil
    • Example 2: Implementing a Set of Integers

Purpose

Provide a suite of primitive algorithms on red-black trees.

Classes

• bslalg::RbTreeUtil: namespace for red-black tree functions
• bslalg::RbTreeUtilTreeProctor: proctor to manage all nodes in a tree

See also

bslalg_rbtreenode

Description

This component provides a variety of algorithms that operate on nodes forming a red-black binary search tree.

This implementation is adapted from Cormen, Leiserson, Rivest, "Introduction to Algorithms" [MIT Press, 1997].

Summary

The following section provides a short synopsis describing observable behavior of functions supplied in this component. See the full function-level contract for detailed description.

Navigation

The following algorithms search a tree for a value, or iterate over the nodes in a tree:

leftmost            Return the leftmost node.
 
rightmost           Return the rightmost node.
 
next                Return the next node in an in-order traversal.
 
previous            Return the previous node in an in-order traversal.
 
find                Find the node with the supplied value.
 
lowerBound          Find the first node not less-than the supplied value.
 
upperBound          Find the first node greater than the supplied value.

Modification

The following algorithms are used in the process of manipulating the structure of a tree:

copyTree            Return a deep-copy of the supplied tree.
 
deleteTree          Delete all the nodes of the supplied tree.
 
findInsertLocation  Find the location where a value may be inserted.
 
findUniqueInsertLocation
                    Find the location where a unique value may be inserted.
 
insert              Insert the supplied node into the tree.
 
insertAt            Insert the supplied node at the indicated position.
 
remove              Remove the supplied node from the tree.
 
swap                Swap the contents of two trees.

Utility

The following algorithms are typically used when implementing higher-level algorithms (and are not generally used by clients):

isLeftChild         Return 'true' if the supplied node is a left child.
 
isRightChild        Return 'true' if the supplied node is a right child.
 
rotateLeft          Perform a counter-clockwise rotation on a node.
 
rotateRight         Perform a clockwise rotation on a node.

Testing

The following algorithms are used for testing and debugging, and generally should not be used in production code:

printTreeStructure  Print, to a file, the structure of the supplied tree.
 
validateRbTree      Indicate if a tree is a valid red-black tree.
 
isWellFormed        Indicate if the 'RbTreeAnchor' object is well-formed.

Well-Formed RbTreeAnchor Objects

Many of the algorithms defined in this component operate over a complete tree of nodes, rather than a (possible) subtree referred to through a pointer to a node. These operations refer to a complete tree through a RbTreeAnchor object, which maintains references to the first, root, and sentinel nodes for the tree, as well as a count of the number of nodes in the tree. RbTreeAnchor objects supplied to RbTreeUtil are frequently required to meet a series of constraints that are not enforced by the RbTreeAnchor type itself. An RbTreeAnchor object meeting these constraints is said to be "well-formed", and RbTreeUtil::isWellFormed will return true for such an object. A RbTreeAnchor object is considered well-formed if all of the following are true:

1. The root node refers to a valid red-black tree (see validateRbTree).
2. The first node refers to the leftmost node in the tree, or the sentinel node if the tree is empty.
3. The node count is the number of nodes in the tree (not counting the sentinel node).
4. The sentinel node refers to the root node as its left child, and the root node refers to the sentinel as its parent.
5. The root node is either 0 or is colored black.

The manipulation functions of RbTreeUtil guarantee that these properties are maintained for any supplied tree. Note that RbTreeUtil::isWellFormed has linear complexity with respect to the number of nodes in the tree, and is typically used for debugging and testing purposes only. Note also that the final condition, that the root node be either 0 or colored black, is not a canonical requirement of a red-black tree but an additional invariant enforced by the methods of RbTreeUtil to simplify the implementations.

The Sentinel Node

The sentinel node is RbTreeNode object (unique to an RbTreeAnchor instance) which does not have a value, and provides a fixed end-point for navigation over the tree (which is distinct from the rightmost node of that tree). The sentinel node will be returned by next if the supplied node is the rightmost node in the tree, as well as by search operations when no nodes meet the supplied search-criteria. In addition, the sentinel node may be supplied as a hint to findInsertLocation and findUniqueInsertLocation, as well as supplied to previous to obtain the rightmost node of a (non-empty) tree.

Usage

This section illustrates intended use of this component.

Example 1: Creating and Using a Tree with RbTreeUtil

This example demonstrates how to create a tree of integers using RbTreeUtil.

First, we define a type SimpleIntNode that will represent a nodes in our tree of integer values. SimpleIntNode contains an int payload, and inherits from RbTreeNode, allowing it to be operated on by RbTreeUtil.

struct SimpleIntNode : public RbTreeNode {
    int d_value;
};

Then, we define a comparison function for SimpleIntNode objects (note that we static-cast RBTreeNode objects to the actual node type, SimpleIntNode, for comparison purposes):

struct SimpleIntNodeValueComparator {
    // This class defines a comparator providing comparison operations
    // between 'SimpleIntNode' objects, and 'int' values.
 
    bool operator()(const RbTreeNode& lhs, int rhs) const
    {
        return static_cast<const SimpleIntNode&>(lhs).d_value < rhs;
    }
 
    bool operator()(int lhs, const RbTreeNode& rhs) const
    {
        return lhs < static_cast<const SimpleIntNode&>(rhs).d_value;
    }
};

Next, we begin to define the example function that will build a tree of nodes holding integer values:

void createTestTreeExample()
{

Then, within this function, we define a RbTreeAnchor object that will hold the root, first, last, and sentinel nodes of tree, as well a count of the number of nodes in the tree:

    RbTreeAnchor tree;

Next, we define an array of 5 SimpleIntNode objects that we will insert into the tree; in practice, nodes are more often allocated on the heap (see example 2):

    const int NUM_NODES = 5;
    SimpleIntNode nodes[NUM_NODES];

Then, we assign unique values to each of the nodes:

    for (int i = 0; i < NUM_NODES; ++i) {
        nodes[i].d_value = i;
    }

Now, for each node in the tree, we use RbTreeUtil to first find the location at which the node should be inserted, and then insert that node into the tree:

    for (int i = 0; i < NUM_NODES; ++i) {
        int comparisonResult;
        SimpleIntNodeValueComparator comparator;
        RbTreeNode *insertLocation = RbTreeUtil::findUniqueInsertLocation(
                                            &comparisonResult,
                                            &tree,
                                            comparator,
                                            nodes[i].d_value);
        BSLS_ASSERT(comparisonResult);
        RbTreeUtil::insertAt(&tree,
                             insertLocation,
                             comparisonResult < 0,
                             &nodes[i]);
    }

And verify the resulting tree holds 5 nodes, and the first node has the value 0:

    assert(5 == tree.numNodes());
    assert(0 == static_cast<SimpleIntNode *>(tree.firstNode())->d_value);

Finally, we use RbTreeUtil to iterate through the nodes of tree, and write the value of each node to the console:

    const RbTreeNode *nodeIterator = tree.firstNode();
    while (tree.sentinel() != nodeIterator) {
        printf("Node value: %d\n",
               static_cast<const SimpleIntNode *>(nodeIterator)->d_value);
        nodeIterator = RbTreeUtil::next(nodeIterator);
    }
}

Notice that each of the RbTreeNode objects must be static_cast to the derived type, SimpleIntNode, in order to access their values.

The resulting output is displayed on the console:

Node value: 0
Node value: 1
Node value: 2
Node value: 3
Node value: 4

Example 2: Implementing a Set of Integers

This example demonstrates how to use RbTreeUtil to implement a simple container holding a set of (unique) integer values as a red-black binary search tree.

Before defining the IntSet class, we need to define a series of associated helper types:

1. The node-type, for the nodes in the tree.
2. An iterator, for iterating over nodes in the tree.
3. A comparison functor for comparing nodes and values.
4. A factory for creating and destroying nodes.

First, we define a type, IntSet_Node, that will represent the nodes in our tree of integer values; it contains an int payload, and inherits from RbTreeNode, allowing it to be operated on by RbTreeUtil (note that the underscore "_" indicates that this type is a private implementation type of IntSet, and not for use by clients of IntSet):

class IntSet_Node : public RbTreeNode {
    // A red-black tree node containing an integer data-value.
 
    // DATA
    int d_value;  // actual value represented by the node
 
  public:
    // MANIPULATORS
    int& value() { return d_value; }
        // Return a reference providing modifiable access to the 'value' of
        // this object.
 
    // ACCESSORS
    const int& value() const { return d_value; }
        // Return a reference providing non-modifiable access to the
        // 'value' of this object.
};

Then, we define a iterator over IntSet_Node objects. We use the next function of RbTreeUtil to increment the iterator (note that, for simplicity, this iterator is not a fully STL compliant iterator implementation):

class IntSetConstIterator {
    // This class defines an STL-style iterator over a non-modifiable tree
    // of 'IntSet_Node' objects.
 
    // DATA
    const RbTreeNode *d_node_p;  // current location of this iterator
 
  public:
    IntSetConstIterator() : d_node_p(0) {}
        // Create an iterator that does not refer to a node.
 
    IntSetConstIterator(const RbTreeNode *node) : d_node_p(node) {}
        // Create an iterator referring to the specified 'node'.
 
//  IntSetConstIterator(const IntSetConstIterator&) = default;
 
    // MANIPULATOR
//  IntSetConstIterator& operator=(const IntSetConstIterator&) = default;

Here, we implement the prefix-increment operator using the next function of 'RbTreeUtil:

    IntSetConstIterator& operator++()
       // Advance this iterator to the subsequent value it the 'IntSet',
       // and return a reference providing modifiable access to this
       // iterator.   The behavior is undefined unless this iterator
       // refers to a element in an 'IntSet'.
    {
        d_node_p = RbTreeUtil::next(d_node_p);
        return *this;
    }
 
    // ACCESSORS
    const int& operator*() const
        // Return a reference providing non-modifiable access to the value
        // referred to by this iterator.
    {
        return static_cast<const IntSet_Node *>(d_node_p)->value();
    }
 
    const int *operator->() const
        // Return an address providing non-modifiable access to the value
        // referred to by this iterator.
    {
        return &(static_cast<const IntSet_Node *>(d_node_p)->value());
    }
 
    const IntSet_Node *nodePtr() const
        // Return the address of the non-modifiable int-set node referred
        // to by this iterator
    {
        return static_cast<const IntSet_Node *>(d_node_p);
    }
};
 
// FREE OPERATORS
bool operator==(const IntSetConstIterator &lhs,
                const IntSetConstIterator &rhs)
    // Return 'true' if the 'lhs' and 'rhs' objects have the same value,
    // and 'false' otherwise.  Two 'IntSetConstIterator' objects have the
    // same value if they refer to the same node.
{
    return lhs.nodePtr() == rhs.nodePtr();
}
 
bool operator!=(const IntSetConstIterator &lhs,
                const IntSetConstIterator &rhs)
    // Return 'true' if the specified 'lhs' and 'rhs' objects do not have
    // the same value, and 'false' otherwise.  Two 'IntSetConstIterator'
    // objects do not have the same value if they refer to different nodes.
{
    return lhs.nodePtr() != rhs.nodePtr();
}

Next, we define a comparison functor for IntSet_Node objects, which will be supplied to RbTreeUtil functions that must compare nodes with values – i.e., those with a NODE_VALUE_COMPARATOR template parameter (e.g., find and findInsertLocation):

struct IntSet_NodeValueComparator {
    // This class defines a comparator providing comparison operations
    // between 'IntSet_Node' objects, and 'int' values.
 
    bool operator()(const RbTreeNode& lhs, int rhs) const
    {
        return static_cast<const IntSet_Node&>(lhs).value() < rhs;
    }
 
    bool operator()(int lhs, const RbTreeNode& rhs) const
    {
        return lhs < static_cast<const IntSet_Node&>(rhs).value();
    }
};

Notice that we static-cast RbTreeNode objects to the actual node type, IntSet_Node for comparison.

Next, we define a factory for creating and destroying IntSet_Node objects. This factory provides the operations createNode and deleteNode. These operations will be used directly by our container implementation, and they are also required by RbTreeUtil functions taking a FACTORY template parameter (e.g., copyTree and deleteTree):

class IntSet_NodeFactory {
    // This class defines a creator object, that when invoked, creates a
    // new 'IntSet_Node' (either from a int value, or an existing
    // 'IntSet_Node' object) using the allocator supplied at construction.
 
    bslma::Allocator *d_allocator_p;  // allocator, (held, not owned)
 
  public:
 
    IntSet_NodeFactory(bslma::Allocator *allocator)
    : d_allocator_p(allocator)
    {
        BSLS_ASSERT_SAFE(allocator);
    }
 
    RbTreeNode *createNode(int value) const
    {
        IntSet_Node *newNode = new (*d_allocator_p) IntSet_Node;
        newNode->value() = value;
        return newNode;
    }
 
    RbTreeNode *createNode(const RbTreeNode& node) const
    {
        IntSet_Node *newNode = new (*d_allocator_p) IntSet_Node;
        newNode->value() = static_cast<const IntSet_Node&>(node).value();
        return newNode;
    }
    void deleteNode(RbTreeNode *node) const
    {
        d_allocator_p->deleteObject(static_cast<IntSet_Node *>(node));
    }
 
    bslma::Allocator *allocator() const
    {
        return d_allocator_p;
    }
};

Then, having defined the requisite helper types, we define the public interface for our IntSet type. Note that for the purposes of illustrating the use of RbTreeUtil a number of simplifications have been made. For example, this implementation provides only a minimal set of critical operations, and it does not use the empty base-class optimization for the comparator, etc. We define the interface of IntSet as follows:

class IntSet {
    // This class implements a set of (unique) 'int' values.
 
    // DATA
    RbTreeAnchor           d_tree;         // root, first, and last tree
                                           // nodes
 
    IntSet_NodeValueComparator
                           d_comparator;   // comparison functor for ints
 
    IntSet_NodeFactory     d_nodeFactory;  // factory for creating and
                                           // destroying nodes
 
    // FRIENDS
    friend bool operator==(const IntSet& lhs, const IntSet& rhs);
 
  public:
    // PUBLIC TYPES
    typedef IntSetConstIterator const_iterator;
 
    // CREATORS
    IntSet(bslma::Allocator *basicAllocator = 0);
        // Create a empty 'IntSet'.  Optionally specify a 'basicAllocator'
        // used to supply memory.  If 'basicAllocator' is 0, the currently
        // installed default allocator is used.
 
    IntSet(const IntSet& original, bslma::Allocator *basicAllocator = 0);
        // Create a 'IntSet' object having the same value as the specified
        // 'original' object.  If 'basicAllocator' is 0, the currently
        // installed default allocator is used.
 
    ~IntSet();
        // Destroy this object.
 
    // MANIPULATORS
    IntSet& operator=(const IntSet& rhs);
        // Assign to this object the value of the specified 'rhs' object,
        // and return a reference providing modifiable access to this
        // object.
 
    const_iterator insert(int value);
        // If the specified 'value' is not already a member of this set,
        // insert it into this set, returning an iterator referring to the
        // newly added value, and return an iterator referring to the
        // existing instance of 'value' in this set, with no other effect,
        // otherwise.
 
    const_iterator erase(const_iterator iterator);
        // Remove the value referred to by the specified 'iterator' from
        // this set, and return an iterator referring to the value
        // subsequent to 'iterator' (prior to its removal).  The behavior
        // is undefined unless 'iterator' refers to a valid value in this
        // set.
 
    void clear();
        // Remove all the elements from this set.
 
    void swap(IntSet& other);
        // Efficiently exchange the value of this object with the value of
        // the specified 'other' object.
 
    // ACCESSORS
    const_iterator begin() const;
        // Return an iterator referring leftmost node value in this set, or
        // 'end()' if this set is empty.
 
    const_iterator end() const;
        // Return an iterator referring to the value one past the
        // rightmost value in this set.
 
    const_iterator find(int value) const;
        // Return a iterator referring to the specified 'value' in this
        // set, or 'end()' if 'value' is not a member of this set.
 
    int size() const;
        // Return the number of elements in this set.
};
 
// FREE OPERATORS
bool operator==(const IntSet& lhs, const IntSet& rhs);
    // Return 'true' if the 'lhs' and 'rhs' objects have the same value,
    // and 'false' otherwise.  Two 'IntSet' objects have the same value if
    // they contain the same number of elements, and if for each element
    // in 'lhs' there is a corresponding element in 'rhs' with the same
    // value.
 
bool operator!=(const IntSet& lhs, const IntSet& rhs);
    // Return 'true' if the specified 'lhs' and 'rhs' objects do not have
    // the same value, and 'false' otherwise.  Two 'IntSet' objects do not
    // have the same value if they differ in the number of elements they
    // contain, or if for any element in 'lhs' there is not a
    // corresponding element in 'rhs' with the same value.

Now, we implement the methods of IntSet using RbTreeUtil and the helper types we defined earlier:

// CREATORS
IntSet::IntSet(bslma::Allocator *basicAllocator)
: d_tree()
, d_comparator()
, d_nodeFactory(bslma::Default::allocator(basicAllocator))
{
}
 
IntSet::IntSet(const IntSet& original, bslma::Allocator *basicAllocator)
: d_tree()
, d_comparator()
, d_nodeFactory(bslma::Default::allocator(basicAllocator))
{
    if (original.d_tree.rootNode()) {
        RbTreeUtil::copyTree(&d_tree, original.d_tree, &d_nodeFactory);
    }
}
 
IntSet::~IntSet()
{
    clear();
}
 
// MANIPULATORS
IntSet& IntSet::operator=(const IntSet& rhs)
{
    IntSet temp(rhs, d_nodeFactory.allocator());
    swap(temp);
    return *this;
}

Here, we implement insert by using the RbTreeUtil algorithms findUniqueInsertLocation and insertAt:

IntSet::const_iterator IntSet::insert(int value)
{
    // To insert a value into the tree, we first find the location where
    // the node would be added, and whether 'value' is unique.  If 'value'
    // is not unique we do not want to incur the expense of allocating
    // memory for a node.
 
    int comparisonResult;
    RbTreeNode *insertLocation =
                  RbTreeUtil::findUniqueInsertLocation(&comparisonResult,
                                                       &d_tree,
                                                       d_comparator,
                                                       value);
    if (0 == comparisonResult) {
        // 'value' already exists in 'd_tree'.
 
        return const_iterator(insertLocation);                    // RETURN
    }
 
    // If 'value' is unique, we create a new node and supply it to
    // 'insertAt', along with the tree location returned by
    // 'findUniqueInsertLocation'.
 
    RbTreeNode *newNode = d_nodeFactory.createNode(value);
    RbTreeUtil::insertAt(&d_tree,
                         insertLocation,
                         comparisonResult < 0,
                         newNode);
    return const_iterator(newNode);
}
 
IntSet::const_iterator IntSet::erase(const_iterator iterator)
{
    BSLS_ASSERT(iterator.nodePtr());
    IntSet_Node *node = const_cast<IntSet_Node *>(iterator.nodePtr());
 
    // Before removing the node, we first find the subsequent node to which
    // we will return an iterator.
 
    RbTreeNode *next = RbTreeUtil::next(node);
    RbTreeUtil::remove(&d_tree, node);
    d_nodeFactory.deleteNode(node);
    return const_iterator(next);
}
 
void IntSet::clear()
{
    if (d_tree.rootNode()) {
        RbTreeUtil::deleteTree(&d_tree, &d_nodeFactory);
    }
}
 
void IntSet::swap(IntSet& other) {
    BSLS_ASSERT(d_nodeFactory.allocator() ==
                other.d_nodeFactory.allocator());
    RbTreeUtil::swap(&d_tree, &other.d_tree);
}
 
// ACCESSORS
IntSet::const_iterator IntSet::begin() const
{
    return const_iterator(d_tree.firstNode());
}
 
IntSet::const_iterator IntSet::end() const
{
    return const_iterator(d_tree.sentinel());
}
 
IntSet::const_iterator IntSet::find(int value) const
{
    return const_iterator(RbTreeUtil::find(d_tree, d_comparator, value));
}
 
int IntSet::size() const
{
    return d_tree.numNodes();
}

Finally, we implement the free operators on IntSet:

// FREE OPERATORS
bool operator==(const IntSet& lhs, const IntSet& rhs)
{
    return bslalg::RangeCompare::equal(lhs.begin(),
                                      lhs.end(),
                                      lhs.size(),
                                      rhs.begin(),
                                      rhs.end(),
                                      rhs.size());
}
 
bool operator!=(const IntSet& lhs, const IntSet& rhs)
{
    return !(lhs == rhs);
}