[#BloombergLP-bslalg-RbTreeUtil]
= xref:BloombergLP.adoc[BloombergLP]::xref:BloombergLP/bslalg.adoc[bslalg]::RbTreeUtil
:relfileprefix: ../../
:mrdocs:

This `struct` provides a namespace for a suite of utility functions that operate on elements of type `RbTreeNode`.

== Synopsis

Declared in `<bslalg_rbtreeutil.h>`

[source,cpp,subs="verbatim,replacements,macros,-callouts"]
----
struct RbTreeUtil;
----

== Description

Each method of this class, other than `copyTree`, provides the _no‐throw_ exception guarantee if the client‐supplied comparator provides the no‐throw guarantee, and provides the _strong_ guarantee otherwise (see `bsldoc_glossary`). `copyTree` provides the _strong_ guarantee.

== Static Member Functions

[cols="1,4"]
|===
| Name| Description
| xref:BloombergLP/bslalg/RbTreeUtil/copyTree.adoc[`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.
| xref:BloombergLP/bslalg/RbTreeUtil/deleteTree.adoc[`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.
| xref:BloombergLP/bslalg/RbTreeUtil/find-08.adoc[`find`] 
| `find` overloads
| xref:BloombergLP/bslalg/RbTreeUtil/findInsertLocation-080.adoc[`findInsertLocation`] 
| `findInsertLocation` overloads
| xref:BloombergLP/bslalg/RbTreeUtil/findUniqueInsertLocation-0f.adoc[`findUniqueInsertLocation`] 
| `findUniqueInsertLocation` overloads
| xref:BloombergLP/bslalg/RbTreeUtil/insert.adoc[`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`).
| xref:BloombergLP/bslalg/RbTreeUtil/insertAt.adoc[`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.
| xref:BloombergLP/bslalg/RbTreeUtil/isLeftChild.adoc[`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()`.
| xref:BloombergLP/bslalg/RbTreeUtil/isRightChild.adoc[`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()`.
| xref:BloombergLP/bslalg/RbTreeUtil/isWellFormed.adoc[`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:
| xref:BloombergLP/bslalg/RbTreeUtil/leftmost-03.adoc[`leftmost`] 
| `leftmost` overloads
| xref:BloombergLP/bslalg/RbTreeUtil/lowerBound-00.adoc[`lowerBound`] 
| `lowerBound` overloads
| xref:BloombergLP/bslalg/RbTreeUtil/moveTree.adoc[`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.
| xref:BloombergLP/bslalg/RbTreeUtil/next-05.adoc[`next`] 
| `next` overloads
| xref:BloombergLP/bslalg/RbTreeUtil/previous-037.adoc[`previous`] 
| `previous` overloads
| xref:BloombergLP/bslalg/RbTreeUtil/printTreeStructure.adoc[`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.
| xref:BloombergLP/bslalg/RbTreeUtil/remove.adoc[`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`).
| xref:BloombergLP/bslalg/RbTreeUtil/rightmost-023.adoc[`rightmost`] 
| `rightmost` overloads
| xref:BloombergLP/bslalg/RbTreeUtil/rotateLeft.adoc[`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.
| xref:BloombergLP/bslalg/RbTreeUtil/rotateRight.adoc[`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.
| xref:BloombergLP/bslalg/RbTreeUtil/swap.adoc[`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`).
| xref:BloombergLP/bslalg/RbTreeUtil/upperBound-0c.adoc[`upperBound`] 
| `upperBound` overloads
| xref:BloombergLP/bslalg/RbTreeUtil/validateRbTree-0b.adoc[`validateRbTree`] 
| `validateRbTree` overloads
|===



[.small]#Created with https://www.mrdocs.com[MrDocs]#