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

Synopsis

Declared in <bslalg_rbtreeutil.h>

struct RbTreeUtil_Validator;

Static Member Functions

Name

Description

isWellFormedAnchor

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:

validateRbTree

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.

Created with MrDocs