5.4.2 Step 2: Insert [ToC] [Index]     [Skip Back] [Skip Fwd]     [Prev] [Up] [Next]

Following the search loop, q is the last non-null node examined, so it is the parent of the node to be inserted. The code below creates and initializes a new node as a child of q on side dir, and stores a pointer to it into n. Compare this code for insertion to that within <BST item insertion function 33>.

151. <Step 2: Insert AVL node 151> =
n = q->avl_link[dir] = 
  tree->avl_alloc->libavl_malloc (tree->avl_alloc, sizeof *n); if (n == NULL) return NULL; tree->avl_count++; n->avl_data = item; n->avl_link[0] = n->avl_link[1] = NULL; n->avl_balance = 0; if (y == NULL) return &n->avl_data;

This code is included in 148.


1. How can y be NULL? Why is this special-cased? [answer]