[#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`] 
| Copy `original` into empty `result` using `nodeFactory`.
| xref:BloombergLP/bslalg/RbTreeUtil/deleteTree.adoc[`deleteTree`] 
| Destroy every node in `tree` and reset it to empty.
| 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 `newNode` into `tree` according to `comparator`.
| xref:BloombergLP/bslalg/RbTreeUtil/insertAt.adoc[`insertAt`] 
| Insert `newNode` under `parentNode` and rebalance `tree`.
| xref:BloombergLP/bslalg/RbTreeUtil/isLeftChild.adoc[`isLeftChild`] 
| Return whether `node` is the left child of its parent.
| xref:BloombergLP/bslalg/RbTreeUtil/isRightChild.adoc[`isRightChild`] 
| Return whether `node` is the right child of its parent.
| xref:BloombergLP/bslalg/RbTreeUtil/isWellFormed.adoc[`isWellFormed`] 
| Return whether `tree` is a well‐formed valid red‐black tree.
| xref:BloombergLP/bslalg/RbTreeUtil/leftmost-03.adoc[`leftmost`] 
| Return the address of the leftmost node in the specified `subtree`.
| xref:BloombergLP/bslalg/RbTreeUtil/lowerBound-00.adoc[`lowerBound`] 
| `lowerBound` overloads
| xref:BloombergLP/bslalg/RbTreeUtil/moveTree.adoc[`moveTree`] 
| Move nodes from `original` into empty `result`.
| xref:BloombergLP/bslalg/RbTreeUtil/next-05.adoc[`next`] 
| Return the in‐order successor of the specified `node`.
| xref:BloombergLP/bslalg/RbTreeUtil/previous-037.adoc[`previous`] 
| Return the in‐order predecessor of the specified `node`.
| xref:BloombergLP/bslalg/RbTreeUtil/printTreeStructure.adoc[`printTreeStructure`] 
| Write a human‐readable description of `subtree` to `file`.
| xref:BloombergLP/bslalg/RbTreeUtil/remove.adoc[`remove`] 
| Remove `node` from `tree` and rebalance the tree.
| xref:BloombergLP/bslalg/RbTreeUtil/rightmost-023.adoc[`rightmost`] 
| `rightmost` overloads
| xref:BloombergLP/bslalg/RbTreeUtil/rotateLeft.adoc[`rotateLeft`] 
| Rotate `node` counter‐clockwise about its right child.
| xref:BloombergLP/bslalg/RbTreeUtil/rotateRight.adoc[`rotateRight`] 
| Rotate `node` clockwise about its left child.
| xref:BloombergLP/bslalg/RbTreeUtil/swap.adoc[`swap`] 
| Exchange the nodes of the specified `a` and `b` trees.
| xref:BloombergLP/bslalg/RbTreeUtil/upperBound-0c.adoc[`upperBound`] 
| Return the first node ordered after `value`, or the sentinel.
| xref:BloombergLP/bslalg/RbTreeUtil/validateRbTree-0b.adoc[`validateRbTree`] 
| `validateRbTree` overloads
|===



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