14.4 Insertion [ToC] [Index]     [Skip Back] [Skip Fwd]     [Prev] [Up] [Next]

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: 

525. <PAVL item insertion function 525> =
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 526>
  <Step 2: Insert PAVL node 527>
  <Step 3: Update balance factors after PAVL insertion 528>
  <Step 4: Rebalance after PAVL insertion 529>
}

This code is included in 524.