bslalg::RbTreeUtil_Validator Struct Reference

#include <bslalg_rbtreeutil.h>

Detailed Description

This struct provides a namespace for auxiliary functions used to validate a red-black binary search tree.

See bslalg_rbtreeutil

Static Public Member Functions
template<class NODE_COMPARATOR >
static int	validateRbTree (const RbTreeNode **errorNode, const char **errorDescription, const RbTreeNode *rootNode, const RbTreeNode *minNodeValue, const RbTreeNode *maxNodeValue, const NODE_COMPARATOR &comparator)
static bool	isWellFormedAnchor (const RbTreeAnchor &tree)

Member Function Documentation

isWellFormedAnchor()

static bool bslalg::RbTreeUtil_Validator::isWellFormedAnchor ( const RbTreeAnchor &  tree )

static

Return true if the specified tree is well-formed, without confirming that it refers to a valid-red-black tree, and false otherwise. This method will return true if all of the following are true:

1. tree.firstNode() must refer to tree.sentinel() if tree.rootNode() is 0, and leftmost(tree.rootNode())' otherwise.
2. tree.nodeCount() must be the count of nodes in tree (not including the sentinel node).
3. tree.sentinel()->leftchild() is tree.rootNode(), and (if tree.rootNode() is not 0), tree.rootNode()->parent() is 'tree.sentinel().
4. tree.rootNode() is 0 or tree.rootNode().isBlack() is true

Precondition

The behavior is undefined unless tree.rootNode() is 0, or refers to a valid binary tree.

Note

Note that this function provides a non-templatized implementation for several criteria of a well-formed tree (but not the complete set verified by RbTreeUtil::isWellFormed).

validateRbTree()

template<class NODE_COMPARATOR >

int bslalg::RbTreeUtil_Validator::validateRbTree ( const RbTreeNode **  errorNode, const char **  errorDescription, const RbTreeNode *  rootNode, const RbTreeNode *  minNodeValue, const RbTreeNode *  maxNodeValue, const NODE_COMPARATOR &  comparator  )

static

Return the (common) number of black nodes on each path from the specified rootNode to a leaf in the tree, 0 if rootNode is 0, and a negative number if rootNode does not refer to a valid red-black binary search tree (ordered according to the specified comparator) that contains no nodes whose value is less than the specified minNodeValue (if not 0) or greater-than the specified maxNodeValue (if not 0). If rootNode does not refer to a valid red-black tree containing nodes whose values are between the specified minNodeValue and maxNodeValue (inclusively) then load errorNode and errorDescription with the address of a node violating a red-black tree constraint and a description of that violation, respectively.

Precondition

The behavior is undefined unless rootNode is 0, or refers to a valid binary tree.

---

The documentation for this struct was generated from the following file:

• bslalg_rbtreeutil.h