Name |
Description |
copyTree
|
Load, into the specified result, a collection of newly created nodes having the same red‐black tree structure as that of the specified original tree, where each node in the returned tree is created by invoking nodeFactory‐>createNode on the corresponding original node; if an exception occurs, use nodeFactory‐>deleteNode to destroy any newly created nodes, and propagate the exception to the caller (i.e., this operation provides the strong exception guarantee). FACTORY shall be a class providing two methods that can be called as if they had the following signatures: ` RbTreeNode *createNode(const RbTreeNode&); void deleteNode(RbTreeNode *); ` The behavior is undefined unless result is an empty tree, original is a well‐formed (see isWellFormed), and nodeFactory‐>deleteNode does not throw. |
deleteTree
|
Call nodeFactory‐>deleteNode on each node in tree and reset tree to an empty state. FACTORY shall be a class providing a method that can be called as if it has the following signature: ` void deleteNode(RbTreeNode *); ` The behavior is undefined unless tree is a valid binary tree, and nodeFactory‐>deleteNode does not throw. |
find
|
find overloads
|
findInsertLocation
|
findInsertLocation overloads
|
findUniqueInsertLocation
|
findUniqueInsertLocation overloads
|
insert
|
Insert the specified newNode into the specified tree, organized according to the specified comparator. The resulting tree will be well‐formed (see isWellFormed). NODE_COMPARATOR shall be a functor providing a method that can be called as if it had the following signatures: ` bool operator()(const RbTreeNode&, const RbTreeNode&) const; ` The behavior is undefined unless comparator provides a strict weak ordering on objects of type VALUE, and tree is well‐formed (see isWellFormed). |
insertAt
|
Insert the specified newNode into the specified tree as either the left or right child of the specified parentNode, as indicated by the specified leftChildFlag, and then rebalance the tree so that it is a valid red‐black tree (see validateRbTree). The behavior is undefined unless tree is well‐formed (see isWellFormed), and, if tree is empty, parentNode is tree‐>sentinel() and leftChildFlag is true, or, if tree is not empty, parentNode is a node in tree whose left or right child (as indicated by leftChildFlag) is 0 where if newNode were attached as that child (without rebalancing) tree would still form an ordered binary tree (though not necessarily a valid red‐black tree). Note that this operation is intended to be used in conjunction with the findInsertLocation or findUniqueInsertLocation methods. |
isLeftChild
|
Return true if the specified node is the left child of its parent, and false otherwise. The behavior is undefined unless 0 != node‐>parent(). |
isRightChild
|
Return true if the specified node is the left child of its parent, and false otherwise. The behavior is undefined unless 0 != node‐>parent(). |
isWellFormed
|
Return true if the specified tree is well‐formed and refers to a valid red‐black tree, and false otherwise. For a RbTreeAnchor to be considered well‐formed all of the following must be true: |
leftmost
|
leftmost overloads
|
lowerBound
|
lowerBound overloads
|
moveTree
|
Load into the specified result, using the specified nodeFactory to create and delete nodes, a collection of newly created nodes with the same (red‐black) tree structure as that of the specified original tree, which uses the specified originalNodeFactory to create and delete nodes, where the value attribute of each node in result is constructed from explicitly moving the value attribute of the corresponding node in original. original is left in a valid but unspecified state. If an exception occurs, both result and original are left in a valid but unspecified state. The behavior is undefined unless result is an empty tree, original is well‐formed (see isWellFormed), and nodeFactory‐>deleteNode and originalNodeFactory‐>deleteNode do not throw. |
next
|
next overloads
|
previous
|
previous overloads
|
printTreeStructure
|
Write a description of the structure of the specified subtree to the specified output file in a human‐readable format, using the specified printValueCallback to render the value of each node. Optionally specify an initial indentation level, whose absolute value is incremented recursively for nested objects. If level is specified, optionally specify spacesPerLevel, whose absolute value indicates the number of spaces per indentation level for this and all of its nested objects. If level is negative, suppress indentation of the first line. If spacesPerLevel is negative, format the entire output on one line, suppressing all but the initial indentation (as governed by level). The behavior is undefined unless node is 0, or the root of a valid binary tree. Note that the implementation of this function is recursive and expensive to perform, it is intended for debugging purposes only. Also note that the format is not fully specified, and can change without notice. |
remove
|
Remove the specified node from the specified tree, and then rebalance tree so that it again forms a valid red‐black tree (see validateRbTree). The behavior is undefined unless tree is well‐formed (see isWellFormed). |
rightmost
|
rightmost overloads
|
rotateLeft
|
Perform counter‐clockwise rotation on the specified node: Rotate the node's right child (the pivot) to be the node's parent, and attach the pivot's left child as the node's right child. ` (node) (pivot) / / . a (pivot) ‐‐‐> (node) c / / . b c a b ` The behavior is undefined unless node‐>rightChild() is not 0, node‐>parent() is not 0, and node's parent refers to node as one of its children. Note that this operation maintains the ordering of the subtree rooted at node. Also note this operation will successfully rotate the root node of an unbalanced, but otherwise well‐formed, tree referred to by a RbTreeAnchor object (see isWellFormed) because the parent of the root node is the tree's sentinel node (i.e., not 0), which refers to the root node as its left child, and an RbTreeAnchor object returns the left child of the sentinel node as the root of the tree. |
rotateRight
|
Perform clockwise rotation on the specified node: Rotate the node's left child (the pivot) to be the node's parent, and attach the pivot's right child as the node's left child. ` (node) (pivot) / / . (pivot) c ‐‐‐> a (node) / / . a b b c ` The behavior is undefined unless node‐>leftChild() is not 0, node‐>parent() is not 0, and node's parent refers to node as one of its children. Note that this operation maintains the ordering of the subtree rooted at node. Also note this operation will successfully rotate the root node of an unbalanced, but otherwise well‐formed, tree referred to by a RbTreeAnchor object (see isWellFormed) because the parent of the root node is the tree's sentinel node (i.e., not 0), which refers to the root node as its left child, and an RbTreeAnchor object returns the left child of the sentinel node as the root of the tree. |
swap
|
Efficiently exchange the nodes in the specified a tree with the nodes in the specified b tree. This method provides the no‐throw exception‐safety guarantee. The behavior is undefined unless a and b are well‐formed (see isWellFormed). |
upperBound
|
upperBound overloads
|
validateRbTree
|
validateRbTree overloads
|