11.5 Deletion [ToC] [Index]     [Skip Back] [Skip Fwd]     [Prev] [Up] [Next]

Deletion in an RTAVL tree takes the usual pattern.

431. <RTAVL item deletion function 431> =
void *
rtavl_delete (struct rtavl_table *tree, const void *item)
{ /* Stack of nodes. */ struct rtavl_node *pa[RTAVL_MAX_HEIGHT]; /* Nodes. */ unsigned char da[RTAVL_MAX_HEIGHT]; /* rtavl_link[] indexes. */ int k; /* Stack pointer. */ struct rtavl_node *p; /* Traverses tree to find node to delete. */ assert (tree != NULL && item != NULL); <Step 1: Search RTAVL tree for item to delete 432> <Step 2: Delete RTAVL node 433> <Steps 3 and 4: Update balance factors and rebalance after RTAVL deletion 440> return (void *) item; }

This code is included in 420.