11.4.1 Steps 1–2: Search and Insert [ToC] [Index]     [Skip Fwd]     [Prev] [Up] [Next]

The basic insertion step itself follows the same steps as <RTBST item insertion function 379> does for a plain RTBST. We do keep track of the directions moved on stack da[] and the last-seen node with nonzero balance factor, in the same way as <Step 1: Search AVL tree for insertion point 150> for unthreaded AVL trees.

422. <Step 1: Search RTAVL tree for insertion point 422> =
z = (struct rtavl_node *) &tree->rtavl_root;
y = tree->rtavl_root;
if (tree->rtavl_root != NULL)
  for (q = z, p = y; ; q = p, p = p->rtavl_link[dir]) 
    { int cmp = tree->rtavl_compare (item, p->rtavl_data, tree->rtavl_param); if (cmp == 0) return &p->rtavl_data; if (p->rtavl_balance != 0) z = q, y = p, k = 0; da[k++] = dir = cmp > 0; if (dir == 0)
        { if (p->rtavl_link[0] == NULL) break; }
      else /* dir == 1 */
        { if (p->rtavl_rtag == RTAVL_THREAD) break; } } else
  { p = (struct rtavl_node *) &tree->rtavl_root; dir = 0; }

This code is included in 421.

423. <Step 2: Insert RTAVL node 423> =
n = tree->rtavl_alloc->libavl_malloc (tree->rtavl_alloc, sizeof *n);
if (n == NULL)
  return NULL;

tree->rtavl_count++;
n->rtavl_data = item;
n->rtavl_link[0] = NULL;
if (dir == 0)
  n->rtavl_link[1] = p;
else /* dir == 1 */ 
  { p->rtavl_rtag = RTAVL_CHILD; n->rtavl_link[1] = p->rtavl_link[1]; } n->rtavl_rtag = RTAVL_THREAD; n->rtavl_balance = 0; p->rtavl_link[dir] = n; if (y == NULL)
  { n->rtavl_link[1] = NULL; return &n->rtavl_data; }

This code is included in 421.