12.3 Insertion [ToC] [Index]     [Skip Back] [Skip Fwd]     [Prev] [Up] [Next]

Insertion is, as usual, one of the operations that must be newly implemented for our new type of tree. There is nothing surprising in the function's outline: 

458. <RTRB item insertion function 458> =
void **
rtrb_probe (struct rtrb_table *tree, void *item) 
{
  struct rtrb_node *pa[RTRB_MAX_HEIGHT]; /* Nodes on stack. */
  unsigned char da[RTRB_MAX_HEIGHT];   /* Directions moved from stack nodes. */
  int k;                               /* Stack height. */

  struct rtrb_node *p; /* Current node in search. */
  struct rtrb_node *n; /* New node. */
  int dir;             /* Side of p on which p is located. */

  assert (tree != NULL && item != NULL);

  <Step 1: Search RTRB tree for insertion point 459>
  <Step 2: Insert RTRB node 460>
  <Step 3: Rebalance after RTRB insertion 461>

  return &n->rtrb_data;
}

This code is included in 457.