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:

525. <PAVL item insertion function 525> =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 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.