[#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`&period;

== Synopsis

Declared in `&lt;bslalg&lowbar;rbtreeutil&period;h&gt;`

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

== Description

Each method of this class, other than `copyTree`, provides the _no&hyphen;throw_ exception guarantee if the client&hyphen;supplied comparator provides the no&hyphen;throw guarantee, and provides the _strong_ guarantee otherwise (see `bsldoc&lowbar;glossary`)&period; `copyTree` provides the _strong_ guarantee&period;

== 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&hyphen;black tree structure as that of the specified `original` tree, where each node in the returned tree is created by invoking `nodeFactory&hyphen;&gt;createNode` on the corresponding `original` node&semi; if an exception occurs, use `nodeFactory&hyphen;&gt;deleteNode` to destroy any newly created nodes, and propagate the exception to the caller (i&period;e&period;, this operation provides the _strong_ exception guarantee)&period; `FACTORY` shall be a class providing two methods that can be called as if they had the following signatures&colon; &grave; RbTreeNode &ast;createNode(const RbTreeNode&amp;)&semi; void deleteNode(RbTreeNode &ast;)&semi; &grave; The behavior is undefined unless `result` is an empty tree, `original` is a well&hyphen;formed (see `isWellFormed`), and `nodeFactory&hyphen;&gt;deleteNode` does not throw&period;
| xref:BloombergLP/bslalg/RbTreeUtil/deleteTree.adoc[`deleteTree`] 
| Call `nodeFactory&hyphen;&gt;deleteNode` on each node in `tree` and reset `tree` to an empty state&period; `FACTORY` shall be a class providing a method that can be called as if it has the following signature&colon; &grave; void deleteNode(RbTreeNode &ast;)&semi; &grave; The behavior is undefined unless `tree` is a valid binary tree, and `nodeFactory&hyphen;&gt;deleteNode` does not throw&period;
| 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`&period; The resulting tree will be well&hyphen;formed (see `isWellFormed`)&period; `NODE&lowbar;COMPARATOR` shall be a functor providing a method that can be called as if it had the following signatures&colon; &grave; bool operator()(const RbTreeNode&amp;, const RbTreeNode&amp;) const&semi; &grave; The behavior is undefined unless `comparator` provides a strict weak ordering on objects of type `VALUE`, and `tree` is well&hyphen;formed (see `isWellFormed`)&period;
| 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&hyphen;black tree (see `validateRbTree`)&period; The behavior is undefined unless `tree` is well&hyphen;formed (see `isWellFormed`), and, if `tree` is empty, `parentNode` is `tree&hyphen;&gt;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&hyphen;black tree)&period; Note that this operation is intended to be used in conjunction with the `findInsertLocation` or `findUniqueInsertLocation` methods&period;
| xref:BloombergLP/bslalg/RbTreeUtil/isLeftChild.adoc[`isLeftChild`] 
| Return `true` if the specified `node` is the left child of its parent, and `false` otherwise&period; The behavior is undefined unless `0 !&equals; node&hyphen;&gt;parent()`&period;
| xref:BloombergLP/bslalg/RbTreeUtil/isRightChild.adoc[`isRightChild`] 
| Return `true` if the specified `node` is the left child of its parent, and `false` otherwise&period; The behavior is undefined unless `0 !&equals; node&hyphen;&gt;parent()`&period;
| xref:BloombergLP/bslalg/RbTreeUtil/isWellFormed.adoc[`isWellFormed`] 
| Return `true` if the specified `tree` is well&hyphen;formed and refers to a valid red&hyphen;black tree, and `false` otherwise&period; For a `RbTreeAnchor` to be considered well&hyphen;formed _all_ of the following must be true&colon;
| 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&hyphen;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`&period; `original` is left in a valid but unspecified state&period; If an exception occurs, both `result` and `original` are left in a valid but unspecified state&period; The behavior is undefined unless `result` is an empty tree, `original` is well&hyphen;formed (see `isWellFormed`), and `nodeFactory&hyphen;&gt;deleteNode` and `originalNodeFactory&hyphen;&gt;deleteNode` do not throw&period;
| 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&hyphen;readable format, using the specified `printValueCallback` to render the value of each node&period; Optionally specify an initial indentation `level`, whose absolute value is incremented recursively for nested objects&period; 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&period; If `level` is negative, suppress indentation of the first line&period; If `spacesPerLevel` is negative, format the entire output on one line, suppressing all but the initial indentation (as governed by `level`)&period; The behavior is undefined unless `node` is 0, or the root of a valid binary tree&period; Note that the implementation of this function is recursive and expensive to perform, it is intended for debugging purposes only&period; Also note that the format is not fully specified, and can change without notice&period;
| 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&hyphen;black tree (see `validateRbTree`)&period; The behavior is undefined unless `tree` is well&hyphen;formed (see `isWellFormed`)&period;
| xref:BloombergLP/bslalg/RbTreeUtil/rightmost-023.adoc[`rightmost`] 
| `rightmost` overloads
| xref:BloombergLP/bslalg/RbTreeUtil/rotateLeft.adoc[`rotateLeft`] 
| Perform counter&hyphen;clockwise rotation on the specified `node`&colon; Rotate the node&apos;s right child (the pivot) to be the node&apos;s parent, and attach the pivot&apos;s left child as the node&apos;s right child&period; &grave; (node) (pivot) &sol; &sol; &period; a (pivot) &hyphen;&hyphen;&hyphen;&gt; (node) c &sol; &sol; &period; b c a b &grave; The behavior is undefined unless `node&hyphen;&gt;rightChild()` is not 0, `node&hyphen;&gt;parent()` is not 0, and node&apos;s parent refers to `node` as one of its children&period; Note that this operation maintains the ordering of the subtree rooted at `node`&period; Also note this operation will successfully rotate the root node of an unbalanced, but otherwise well&hyphen;formed, tree referred to by a `RbTreeAnchor` object (see `isWellFormed`) because the parent of the root node is the tree&apos;s sentinel node (i&period;e&period;, 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&period;
| xref:BloombergLP/bslalg/RbTreeUtil/rotateRight.adoc[`rotateRight`] 
| Perform clockwise rotation on the specified `node`&colon; Rotate the node&apos;s left child (the pivot) to be the node&apos;s parent, and attach the pivot&apos;s right child as the node&apos;s left child&period; &grave; (node) (pivot) &sol; &sol; &period; (pivot) c &hyphen;&hyphen;&hyphen;&gt; a (node) &sol; &sol; &period; a b b c &grave; The behavior is undefined unless `node&hyphen;&gt;leftChild()` is not 0, `node&hyphen;&gt;parent()` is not 0, and node&apos;s parent refers to `node` as one of its children&period; Note that this operation maintains the ordering of the subtree rooted at `node`&period; Also note this operation will successfully rotate the root node of an unbalanced, but otherwise well&hyphen;formed, tree referred to by a `RbTreeAnchor` object (see `isWellFormed`) because the parent of the root node is the tree&apos;s sentinel node (i&period;e&period;, 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&period;
| xref:BloombergLP/bslalg/RbTreeUtil/swap.adoc[`swap`] 
| Efficiently exchange the nodes in the specified `a` tree with the nodes in the specified `b` tree&period; This method provides the no&hyphen;throw exception&hyphen;safety guarantee&period; The behavior is undefined unless `a` and `b` are well&hyphen;formed (see `isWellFormed`)&period;
| 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]#
