Radix Search Tree Files: rst.c, rst.h The radix search tree is the similar to the digital search tree. However, in a radix search tree, all data items are stored as leaves in the tree, and the internal nodes of the tree have no key. Thus, an internal node's child is either another internal node, or a data item. A radix search tree node, as implemented in the source files rst.c and rst.h, is illustrated below: ------------- | child_links | |-------------| | a[0] | a[1] | --/-------\-- / \ a[0] and a[1] - pointers to the node's children. Whether the child is a node, or a data item, is specified by the child_links field. To allow this flexibility in the type of pointer, a[0] and a[1] are declared with the type (void *) in the source file rst.h. child_links - This is a two bit field. Bit 0 specifies the what kind of pointer a[0] is, and bit 1 specifies what kind of pointer a[1] is. In each case, if the bit value is zero, the pointer is either NULL or points to a data item. Otherwise if the bit is one the pointer points to another node. For example, if the value of child_links is 10 (binary), then a[0] is NULL or points to a data item, and a[1] points to a node. Similarly, if the value of child_links is 11 (binary), then both a[0] and a[1] point to nodes. When trying to locate a node, individual bits in the search key are examined and a[0] or a[1] is traversed according to the bit value. However, unlike the digital search tree, the radix search tree does not need to spend a key comparison at each node that is traversed in the search. Instead, the traversal continues until the corresponding bit in child_links is zero. Then, either a NULL pointer, or a data item has been located. Also, the root node remains in the radix search tree, even when there are no items in the tree. Before reading the description of the find(), insert() and delete() operations below, refer to the digital search tree description for a comparison. find() ------ Pseudo-code for the find operation is given below. The search for an item with a key, k, starts at the root node of the digital search tree, t. The pointer variable, p, points to the current node in the search, and max_b is the key size in bits. p = t->root; i = max_b - 1; loop { let j be the value of the (i)th bit of k; /* (bit 0 being the lowest bit) */ /* Exit the loop if p->a[j] does not point to an internal node. */ if the (j)th bit of p->child_links is not set then exit loop; p = p->a[j]; i = i - 1; } if p->a[j] is not null and key(p->a[j]) == k then a matching item was found. else no item matching key k was found in the tree. insert() -------- Pseudo-code for the insert() operation is given below. This describes inserting an item, item, with key, k, into the tree, t. First, the insertion position is located by traversing the branches of t, according to the bit values of k. p = t->root; i = max_b - 1; loop { let j be the value of the (i)th bit of k; /* (bit 0 being the lowest bit) */ /* Exit the loop if p->a[j] does not point to an internal node. */ if the (j)th bit of p->child_links is not set then exit loop; p = p->a[j]; i = i - 1; } If the insertion position is already occupied by an item, item2, a path of new internal nodes must be created which can distinguish between the key bits of item and item2. Otherwise, if the insertion position is empty, then item can be inserted there. item2 = p->a[j]; if item2 is not null { k2 = key(item2); if k2 == k then then an item with key k already exists, exit, returning insertion failed. create a new internal node, x; p->a[j] = x; set bit j in p->child_links; loop { p = x; i = i - 1; let j be the (i)th bit of k; /* Stop creating internal nodes if the current bit distinguishes * between k1 and k2. */ if the (i)th bit of k2 is not equal to j then exit loop; create a new internal node, x; p->a[j] = x; p->a[!j] = null; assign p->child_links with only bit j set; } /* After the loop has exited, there are enough internal nodes to * distinguish between the keys of item and item2. */ p->a[j] = item; p->a[!j] = item2; assign p->child_links with all bits cleared; } else { p->a[j] = item; } delete() -------- Pseudo-code describing the delete() operation is given below. This describes inserting an item, item, with key, k, into the tree, t. First, the item to be deleted is located by traversing the branches of t. p = t->root; i = max_b - 1; loop { let j be the value of the (i)th bit of k; /* (bit 0 being the lowest bit) */ /* Exit the loop if p->a[j] does not point to an internal node. */ if the (j)th bit of p->child_links is not set then exit loop; p = p->a[j]; i = i - 1; } if p->a[j] is null or key(p->a[j]) != k then no matching item was found, exit, returning delete failed. After removing p->a[j], node p may be unnecessary and also be deleted, and the removal of unnecessary internal nodes may propagate back up the path towards the root node. This requires accessing parent nodes. The pseudo-code below does not give details about accessing the parent nodes, but an actual implementation can do this by storing nodes along the path to p on a stack, or by maintaining parent pointers for each node. /* Special case, deleting the child of a root node. */ if p is the root node then { p->a[j] = NULL; clear bit j in p->child_links; delete was successful, exit. } /* If p->a[!j] points to an internal node, then there are no unnecessary * internal nodes. Otherwise node p is no longer required. */ if the (!j)th bit in p->child_links is set then { p->a[j] = NULL; } else { y = p->a[!j]; /* Remember the value of the sibling pointer since this * is relocated after unnecessary internal nodes are * deleted. */ /* Delete unnecessary internal nodes. */ do { delete the node pointed to by p, and traverse back up the tree... ...obtaining new values for p and j. if p->a[!j] is not null then exit loop; } while p is not at the root node; /* Since p->a[!j] is not null node p cannot be deleted, and we relocate * the pointer saved in y to p->a[j]. */ p->a[j] = y; } clear bit j in p->child_links; find_min() and delete_min() --------------------------- In a radix search tree, the left-most leaf item is has the smallest key among all the items in the tree, t. To locate this item, the traversal favours branching in this order: - left branches to other internal nodes. - a non null left branch to a data item. - right branch (regardless of type). The following pseudo-code accomplishes this: p = t->root; loop { j = p->a[0] ? 0 : 1; /* Exit if p->a[j] is a leaf item or is null. */ if the (j)th bit of p->child_links is not set then exit loop; p = p->a[j]; } When the loop exits, p->a[j] points to the minimum item in the tree. Note that if the tree was empty then p->a[j] will be null. For delete-min the rearrangement process after removing the minimum node is the same as for delete.