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

search

	Buy GNU books!

GNU libavl 2.0.1

13.3.1 Steps 1 and 2: Search and Insert

The process of search and insertion proceeds as usual. Stack pa[], with pa[k - 1] at top of stack, records the parents of the node p currently under consideration, with corresponding stack da[] indicating the direction moved. We use the standard code for insertion into an RTBST. When the loop exits, p is the node under which a new node should be inserted on side dir.

da[0] = 0; pa[0] = (struct rtrb_node *) &tree->rtrb_root; k = 1; if (tree->rtrb_root != NULL) for (p = tree->rtrb_root; ; p = p->rtrb_link[dir]) { int cmp = tree->rtrb_compare (item, p->rtrb_data, tree->rtrb_param); if (cmp == 0) return &p->rtrb_data; pa[k] = p; da[k++] = dir = cmp > 0; if (dir == 0) { if (p->rtrb_link[0] == NULL) break; } else /* dir == 1 */ { if (p->rtrb_rtag == RTRB_THREAD) break; } } else { p = (struct rtrb_node *) &tree->rtrb_root; dir = 0; }

This code is included in @refalso{456

n = tree->rtrb_alloc->libavl_malloc (tree->rtrb_alloc, sizeof *n); if (n == NULL) return NULL; tree->rtrb_count++; n->rtrb_data = item; n->rtrb_link[0] = NULL; if (dir == 0) { if (tree->rtrb_root != NULL) n->rtrb_link[1] = p; else n->rtrb_link[1] = NULL; } else /* dir == 1 */ { p->rtrb_rtag = RTRB_CHILD; n->rtrb_link[1] = p->rtrb_link[1]; } n->rtrb_rtag = RTRB_THREAD; n->rtrb_color = RTRB_RED; p->rtrb_link[dir] = n;

This code is included in @refalso{456