14.4.1 Steps 1 and 2: Search and Insert

We search much as before. Despite use of the parent pointers, we preserve the use of q as the parent of p because the termination condition is a value of NULL for p, and NULL has no parent. (Thus, q is not, strictly speaking, always p's parent, but rather the last node examined before p.)

Because of parent pointers, there is no need for variable z, used in earlier implementations of AVL insertion to maintain y's parent.

524. <Step 1: Search PAVL tree for insertion point 524> =
y = tree->pavl_root;
for (q = NULL, p = tree->pavl_root; p != NULL; q = p, p = p->pavl_link[dir]) 
  {
    int cmp = tree->pavl_compare (item, p->pavl_data, tree->pavl_param);
    if (cmp == 0)
      return &p->pavl_data;
    dir = cmp > 0;

    if (p->pavl_balance != 0)
      y = p;
  }

This code is included in 523.

The node to create and insert the new node is based on that for PBSTs. There is a special case for a node inserted into an empty tree:

525. <Step 2: Insert PAVL node 525> =
<Step 2: Insert PBST node; pbst => pavl 492>
n->pavl_balance = 0;
if (tree->pavl_root == n)
  return &n->pavl_data;

This code is included in 523.