view release on metacpan or  search on metacpan

btree_rb.c  view on Meta::CPAN

 * of the red-black tree properties. This function performs rotations and 
 * color changes to rebalance the tree
 */
static void do_insert_balancing(BtRbTree *pTree, BtRbNode *pX)
{
  /* In the first iteration of this loop, pX points to the red node just
   * inserted in the tree. If the parent of pX exists (pX is not the root
   * node) and is red, then the properties of the red-black tree are
   * violated.
   *
   * At the start of any subsequent iterations, pX points to a red node
   * with a red parent. In all other respects the tree is a legal red-black
   * binary tree. */
  while( pX != pTree->pHead && !pX->pParent->isBlack ){
    BtRbNode *pUncle;
    BtRbNode *pGrandparent;

    /* Grandparent of pX must exist and must be black. */
    pGrandparent = pX->pParent->pParent;
    assert( pGrandparent );
    assert( pGrandparent->isBlack );