7.6 Insertion |

It take a little more effort to insert a new node into a threaded BST than into an unthreaded one, but not much more. The only difference is that we now have to set up the new node's left and right threads to point to its predecessor and successor, respectively.

Fortunately, these are easy to figure out. Suppose that new node *n* is
the right child of its parent *p* (the other case is symmetric). This
means that *p* is *n*'s predecessor, because *n* is the least node in
*p*'s right subtree. Moreover, *n*'s successor is the node that was
*p*'s successor before *n* was inserted, that is to say, it is the same
as *p*'s former right thread.

Here's an example that may help to clear up the description. When new node 3 is inserted as the right child of 2, its left thread points to 2 and its right thread points where 2's right thread formerly did, to 4:

The following code unifies the left-side and right-side cases using
*dir*, which takes the value 1 for a right-side insertion, 0 for a
left-side insertion. The side opposite *dir* can then be expressed
simply as !*dir*.

256. <TBST item insertion function 256> =void**tbst_probe(structtbst_table*tree,void*item)

{structtbst_node*p; /* Traverses tree to find insertion point. */structtbst_node*n; /* New node. */intdir; /* Side ofpon whichnis inserted. */assert(tree!=NULL&&item!=NULL); <Step 1: Search TBST for insertion point 257> <Step 2: Insert TBST node 258>return&n->tbst_data; }

This code is included in 253.

257. <Step 1: Search TBST for insertion point 257> =if(tree->tbst_root!=NULL)for(p=tree->tbst_root; ;p=p->tbst_link[dir])

{intcmp=tree->tbst_compare(item,p->tbst_data,tree->tbst_param);if(cmp== 0)return&p->tbst_data;dir=cmp> 0;if(p->tbst_tag[dir] ==TBST_THREAD)break; }else

{p= (structtbst_node*) &tree->tbst_root;dir= 0; }

This code is included in 256 and 670.

258. <Step 2: Insert TBST node 258> =n=tree->tbst_alloc->libavl_malloc(tree->tbst_alloc,sizeof*n);if(n==NULL)returnNULL;tree->tbst_count++;n->tbst_data=item;n->tbst_tag[0] =n->tbst_tag[1] =TBST_THREAD;n->tbst_link[dir] =p->tbst_link[dir];if(tree->tbst_root!=NULL)

{p->tbst_tag[dir] =TBST_CHILD;n->tbst_link[!dir] =p; }else

n->tbst_link[1] =NULL;p->tbst_link[dir] =n;

This code is included in 256, 305, and 341.

**See also:**
[Knuth 1997], algorithm 2.3.1I.

**Exercises:**

**1.** What happens if we reverse the order of the final **if** statement above
and the following assignment?
[answer]