GNU libavl 2.0.1
15.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.
| | 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 @refalso{523
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:
| | <@xref{\NODE\, , Step 2: Insert PBST node; pbst =>.> pavl,492}
n->pavl_balance = 0;
if (tree->pavl_root == n)
return &n->pavl_data;
|
This code is included in @refalso{523
