bslalg_rbtreeanchor

Detailed Description

Outline

• Purpose
• Classes
• Description
  • Sentinel Node
  • Usage
    • Example 1: Creating a Simple Tree
    • Example 2: Creating an Insert Function for a Binary Tree

Purpose

Encapsulate root, first, and last nodes of a tree with a count.

Classes

• bslalg::RbTreeAnchor: (in-core) node-addresses and node count

See also

bslalg_rbtreenode, bslalg_rbtreeutil

Description

This component defines a single class, RbTreeAnchor, providing access to the addresses of the root, first, and sentinel nodes of a tree, as well as the count of the number of nodes. A sentinel node is a value-less node, owned by the RbTreeAnchor for the tree, that is used as the end-point for iteration over the nodes in a tree. RbTreeAnchor provides modifiers for the firstNode, rootNode, and numNodes properties, however the sentinel node for a tree is located at a fixed address and cannot be modified. An RbTreeAnchor is similar to an in-core unconstrained attribute class, except that it does not supply equality-comparison, copy-construction, and copy-assignment operations.

Sentinel Node

The sentinel node is an RbTreeNode object that does not have a value, and provides a fixed end-point for navigation over the tree. However, a sentinel node's attributes have different interpretations than those of other RbTreeNode objects. Specifically, a sentinel node's leftChild refers to the root of the tree, and its rightChild refers to the first node of the tree. The following diagram shows the composition of a tree with RbTreeAnchor and RbTreeNode:

                      .------------------------.
               .------|      RbTreeAnchor      |-------.
               |      |                        |       |
     firstNode |      |    .--------------.    |       | rootNode
               |      |    |  RbTreeNode  |    |       |
               |      |    |  (sentinel)  |    |       |
               |      |    `--------------'    |       |
               |      |      /    ^      \     |       |
               |      `-----/-----|-------\----'       |
               V           /      |        \           V
                __________/       |         \__________
               |                  |                    |
               |                  |                    |
      sentinel |             root |                    | sentinel
 *right*-child |       parentNode |                    | *left*-child
               |                  |                    |
               |           .--------------.            |
               |           |  RbTreeNode  | <----------'
               |           |    (root)    |
               |           `--------------'
               |                /   \.
               |     .------------. .------------.
               |     | RbTreeNode | | RbTreeNode |
               |     `------------' `------------'
               |         /                \.
               |    .-----------------------------.
               |    |                             |
               |    |    [Tree of RbTreeNodes]    |
               |    |                             |
               |    |_____________________________|
               V   /                               \.
      .------------.                                .------------.
      | RbTreeNode |                                | RbTreeNode |
      |   (first)  |                                |   (last)   |
      `------------'                                `------------'

Notice that, counter-intuitively, the sentinel's right-child refers to the left-most (first) node of the tree. Also notice that RbTreeAnchor doesn't hold a direct reference to the last (i.e., the right-most) node of the tree.

Usage

This section illustrates intended usage of this component.

Example 1: Creating a Simple Tree

This example demonstrates creating a simple tree of integer values using RbTreeAnchor. Note that, in practice, clients should use associated utilities to manage such a tree (see bslalg_rbtreeutil ).

First, we define a node-type, IntTreeNode, that inherits from RbTreeNode:

struct IntTreeNode : public RbTreeNode {
    // A red-black tree node containing an integer data-value.
 
    int d_value;  // "payload" value represented by the node
};

Then, we define main for our example, and create three nodes that we'll use to construct a tree:

int main(int argc, const char *argv[])
{
    IntTreeNode A, B, C;

Next, we create an RbTreeAnchor, myTree, which will hold the addresses of the root node and the first node of our tree along with a count of nodes, and then verify the attribute values of the default constructed object:

    RbTreeAnchor myTree;
    assert(0                 == myTree.rootNode());
    assert(myTree.sentinel() == myTree.firstNode());
    assert(0                 == myTree.numNodes());

Then, we describe the structure of the tree we wish to construct.

          A (value: 2, BLACK)
              /       \.
             /         \.
  B (value: 1, RED)   C ( value: 5, RED )

Next, we set the properties for the nodes A, B, and C to form a valid tree whose structure matches that description:

    A.d_value = 2;
    A.makeBlack();
    A.setParent(myTree.sentinel());
    A.setLeftChild(&B);
    A.setRightChild(&C);
 
    B.d_value = 1;
    B.makeRed();
    B.setParent(&A);
    B.setLeftChild(0);
    B.setRightChild(0);
 
    C.d_value = 3;
    C.makeRed();
    C.setParent(&A);
    C.setLeftChild(0);
    C.setRightChild(0);

Now, we assign the address of A and B as the root node and the first node of myTree respectively and set the number of nodes to 3:

    myTree.reset(&A, &B, 3);

Finally, we verify the attributes of myTree:

    assert(&A == myTree.rootNode());
    assert(&B == myTree.firstNode());
    assert(3  == myTree.numNodes());

Example 2: Creating an Insert Function for a Binary Tree

This example demonstrates creating a function that inserts elements into a binary search tree. Note that, for simplicity, this function does not create a balanced red-black tree (see bslalg_rbtreeutil ).

First, we define a comparison functor for IntTreeNode objects used by the insertion function:

struct IntTreeNodeComparator {
    // This class defines a comparator providing a comparison operation
    // between two 'IntTreeNode' objects.
 
    bool operator()(const RbTreeNode& lhs, const RbTreeNode& rhs)  const
    {
        return static_cast<const IntTreeNode&>(lhs).d_value <
               static_cast<const IntTreeNode&>(rhs).d_value;
    }
};

Then, we declare the signature of a function insertNode, which takes three arguments: (1) the anchor of the tree in which to insert the node (2) the new node to insert into the tree, and (3) a comparator, which is used to compare the payload values of the tree nodes. Note that the parameterized comparator is needed because a node's value is not accessible through the supplied RbTreeNode.

template <class NODE_COMPARATOR>
void insertNode(RbTreeAnchor           *searchTree,
                RbTreeNode             *newNode,
                const NODE_COMPARATOR&  comparator)
    // Insert into the specified 'searchTree', ordered according to the
    // specified 'comparator', the specified 'newNode'.  If there are
    // multiple nodes having the same value as 'newNode', insert 'newNode'
    // in the last position according to an infix traversal of the tree.
    // The behavior is undefined unless the 'comparator' provides a
    // strict weak ordering on the nodes in the tree.
{

Next, we find the location where newNode can be inserted into searchTree without violating the ordering imposed by comparator, and then updates searchTree with a potentially updated root node and first node.

    RbTreeNode *parent = searchTree->sentinel();
    RbTreeNode *node   = searchTree->rootNode();
    bool        isLeftChild;
 
    newNode->setLeftChild(0);
    newNode->setRightChild(0);
 
    if (!node) {

If the root node of searchTree is 0, we use the reset function set the root node and the first node of searchTree to newNode and set the number of nodes to 1:

        searchTree->reset(newNode, newNode, 1);
        newNode->setParent(parent);
        return;                                                   // RETURN
    }
 
    // Find the leaf node that would be a valid parent of 'newNode'.
 
    do {
        parent = node;
        isLeftChild = comparator(*newNode, *node);
        if (isLeftChild) {
            node = parent->leftChild();
        }
        else {
            node = parent->rightChild();
        }
    } while (node);
 
    // Insert 'newNode' into 'searchTree' and the location that's been
    // found.

Then, we insert newNode into the appropriate position by setting it as a child of parent:

    if (isLeftChild) {
        // If 'newNode' is a left-child, it may be the new first node, but
        // cannot be the new last node.
 
        parent->setLeftChild(newNode);
        newNode->setParent(parent);
        if (parent == searchTree->firstNode()) {
            searchTree->setFirstNode(newNode);
        }
    }
    else {
        parent->setRightChild(newNode);
        newNode->setParent(parent);
    }

Next, we complete the insert function by incrementing the number of nodes in the tree:

    searchTree->incrementNumNodes();
}

Now, we create 5 IntTreeNode objects and insert them into a tree using the insertNode function.

IntTreeNode nodes[5];
 
nodes[0].d_value = 3;
nodes[1].d_value = 1;
nodes[2].d_value = 5;
nodes[3].d_value = 2;
nodes[4].d_value = 0;
 
IntTreeNodeComparator comparator;
 
RbTreeAnchor anchor;
for (int i = 0; i < 5; ++i) {
    insertNode(&anchor, nodes + i, comparator);
}

Finally, we verify that the RbTreeAnchor refers to the correct TreeNode with its firstNode and rootNode attributes.

assert(0 == static_cast<IntTreeNode *>(anchor.firstNode())->d_value);
assert(3 == static_cast<IntTreeNode *>(anchor.rootNode())->d_value);