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.

526. <Step 1: Search PAVL tree for insertion point 526> =
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 525.

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:

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

This code is included in 525.