14.4 Insertion |

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(structpavl_table*tree,void*item)

{structpavl_node*y; /* Top node to update balance factor, and parent. */structpavl_node*p, *q; /* Iterator, and parent. */structpavl_node*n; /* Newly inserted node. */structpavl_node*w; /* New root of rebalanced subtree. */intdir; /* 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.