www.delorie.com/gnu/docs/avl/libavl_252.html

search

	Buy GNU books!

GNU libavl 2.0.1

15.5.1 Step 2: Delete

The actual deletion step is derived from that for PBSTs. We add code to modify balance factors and set up for rebalancing. After the deletion, q is the node at which balance factors must be updated and possible rebalancing occurs and dir is the side of q from which the node was deleted. This follows the pattern already seen in TAVL deletion (see section 9.5.2 Step 2: Delete).

if (p->pavl_link[1] == NULL) { <@xref{\NODE\, , Case 1 in PAVL deletion.>,536} } else { struct pavl_node *r = p->pavl_link[1]; if (r->pavl_link[0] == NULL) { <@xref{\NODE\, , Case 2 in PAVL deletion.>,537} } else { <@xref{\NODE\, , Case 3 in PAVL deletion.>,538} } } tree->pavl_alloc->libavl_free (tree->pavl_alloc, p);

This code is included in @refalso{534

Case 1: p has no right child

No changes are needed for case 1. No balance factors need change and q and dir are already set up correctly.

<@xref{\NODE\, , Case 1 in PBST deletion; pbst =>.> pavl,497}

This code is included in @refalso{535

Case 2: p's right child has no left child

See the commentary on <@xref{\NODE\, , Case 3 in TAVL deletion.>,316} for details.

<@xref{\NODE\, , Case 2 in PBST deletion; pbst =>.> pavl,498} r->pavl_balance = p->pavl_balance; q = r; dir = 1;

This code is included in @refalso{535

Case 3: p's right child has a left child

See the commentary on <@xref{\NODE\, , Case 4 in TAVL deletion.>,317} for details.

<@xref{\NODE\, , Case 3 in PBST deletion; pbst =>.> pavl,499} s->pavl_balance = p->pavl_balance; q = r; dir = 0;

This code is included in @refalso{535