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

Insert `newNode` under `parentNode` and rebalance `tree`&period;

== Synopsis

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

[source,cpp,subs="verbatim,replacements,macros,-callouts"]
----
static
void
insertAt(
    xref:BloombergLP/bslalg/RbTreeAnchor.adoc[RbTreeAnchor]* tree,
    xref:BloombergLP/bslalg/RbTreeNode.adoc[RbTreeNode]* parentNode,
    bool leftChildFlag,
    xref:BloombergLP/bslalg/RbTreeNode.adoc[RbTreeNode]* newNode);
----

== Description

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;

== Parameters

[cols="1,4"]
|===
| Name| Description
| *tree*
| well&hyphen;formed tree that receives `newNode`
| *parentNode*
| parent under which `newNode` is attached
| *leftChildFlag*
| `true` to attach as left child, else right
| *newNode*
| node to insert into `tree`
|===


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