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. Optionally specify errorNode and errorDescription in which to load 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.
Synopsis
Declared in <bslalg_rbtreeutil.h>
template<class NODE_COMPARATOR>
static
int
validateRbTree(
RbTreeNode const* rootNode,
NODE_COMPARATOR const& comparator);Description
Each node of a red‐black tree is colored either red or black; null nodes are considered black. Four requirements must be satisfied for rootNode to refer to a valid red‐black binary search tree:
1. For each node in the tree, no descendents to the left of that node would order after that node (according to the comparator), and no descendents to the right of that node would order before it. 2. For each node in the tree, each non‐null child of that node refers to that node as its parent. 3. If a node in the tree is colored red, all its children are colored black or are null (which is considered black). 4. For each node in the tree, every path from that node to a leaf contains the same number of black nodes, where null children are considered black leaf nodes.
The behavior is undefined unless rootNode is 0, or refers to a valid binary tree. Note that the implementation of this function is recursive and has linear complexity with respect to the number of nodes in tree, it is intended for debugging purposes only.
Created with MrDocs