BDE 4.14.0 Production release
|
#include <bslalg_rbtreeutil.h>
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) |
This struct
provides a namespace for auxiliary functions used to validate a red-black binary search 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:
tree.firstNode()
must refer to tree.sentinel()
if tree.rootNode()
is 0, and leftmost(tree.rootNode())' otherwise.tree.nodeCount()
must be the count of nodes in tree
(not including the sentinel node).tree.sentinel()->leftchild()
is tree.rootNode()
, and (if tree.rootNode()
is not 0), tree.rootNode()->parent()
is 'tree.sentinel().tree.rootNode()
is 0 or tree.rootNode().isBlack()
is true
The behavior is undefined unless tree.rootNode()
is 0, or refers to a valid binary tree. 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
).
|
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. The behavior is undefined unless rootNode
is 0, or refers to a valid binary tree.