Insert newNode under parentNode and rebalance tree.

Synopsis

Declared in <bslalg_rbtreeutil.h>

static
void
insertAt(
    RbTreeAnchor* tree,
    RbTreeNode* parentNode,
    bool leftChildFlag,
    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‐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.

Parameters

Name

Description

tree

well‐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

Created with MrDocs