Inserting into a PAVL Tree - GNU libavl 2.0.2

The same basic algorithm has been used for insertion in all of our AVL tree variants so far. (In fact, all three functions share the same set of local variables.) For PAVL trees, we will slightly modify our approach. In particular, until now we have cached comparison results on the way down in order to quickly adjust balance factors after the insertion. Parent pointers let us avoid this caching but still efficiently update balance factors.

Before we look closer, here is the function's outline:

523. <PAVL item insertion function 523> =
void **
pavl_probe (struct pavl_table *tree, void *item) 
{
  struct pavl_node *y;     /* Top node to update balance factor, and parent. */
  struct pavl_node *p, *q; /* Iterator, and parent. */
  struct pavl_node *n;     /* Newly inserted node. */
  struct pavl_node *w;     /* New root of rebalanced subtree. */
  int dir;                 /* Direction to descend. */

  assert (tree != NULL && item != NULL);

  <Step 1: Search PAVL tree for insertion point 524>
  <Step 2: Insert PAVL node 525>
  <Step 3: Update balance factors after PAVL insertion 526>
  <Step 4: Rebalance after PAVL insertion 527>
}

This code is included in 522.