Chapter 7

Section 7.2

1. An enumerated type is compatible with some C integer type, but the particular type is up to the C compiler. Many C compilers will always pick int as the type of an enumeration type. But we want to conserve space in the structure (see Exercise 1), so we specify unsigned char explicitly as the type.

See also:  [ISO 1990], section 6.5.2.2; [ISO 1999], section 6.7.2.2.

Section 7.6

1. When we add a node to a formerly empty tree, this statement will set tree->tbst_root, thereby breaking the if statement's test.

Section 7.7

1. See Finding the Parent of a TBST Node. Function find_parent() is implemented in <Find parent of a TBST node 329>.

657. <Find TBST node to delete, with parent node algorithm 657> =
p = tree->tbst_root;
if (p == NULL)
  return NULL;

for (;;) 
  {
    int cmp = tree->tbst_compare (item, p->tbst_data, tree->tbst_param);
    if (cmp == 0) 
      break;

    p = p->tbst_link[cmp > 0];
  }

q = find_parent (tree, p);
dir = q->tbst_link[0] != p;

See also:  [Knuth 1997], exercise 2.3.1-19.

2. Yes. We can bind a pointer and a tag into a single structure, then use that structure for our links and for the root in the table structure.

/* A tagged link. */
struct tbst_link 
  {
    struct tbst_node *tbst_ptr;     /* Child pointer or thread. */
    unsigned char tbst_tag;         /* Tag. */
  };

/* A threaded binary search tree node. */
struct tbst_node 
  {
    struct tbst_link tbst_link[2];  /* Links. */
    void *tbst_data;                /* Pointer to data. */
  };

/* Tree data structure. */
struct tbst_table 
  {
    struct tbst_link tbst_root;         /* Tree's root; tag is unused. */
    tbst_comparison_func *tbst_compare; /* Comparison function. */
    void *tbst_param;                   /* Extra argument to tbst_compare. */
    struct libavl_allocator *tbst_alloc; /* Memory allocator. */
    size_t tbst_count;                  /* Number of items in tree. */
  };

The main disadvantage of this approach is in storage space: many machines have alignment restrictions for pointers, so the nonadjacent unsigned chars cause space to be wasted. Alternatively, we could keep the current arrangement of the node structure and change tbst_root in struct tbst_table from a pointer to an instance of struct tbst_node.

3. Much simpler than the implementation given before:

658. <Case 4 in TBST deletion, alternate version 658> =
struct tbst_node *s = r->tbst_link[0];
while (s->tbst_tag[0] == TBST_CHILD) 
  {
    r = s;
    s = r->tbst_link[0];
  }

p->tbst_data = s->tbst_data;

if (s->tbst_tag[1] == TBST_THREAD) 
  {
    r->tbst_tag[0] = TBST_THREAD;
    r->tbst_link[0] = p;
  } 
else 
  {
    q = r->tbst_link[0] = s->tbst_link[1];
    while (q->tbst_tag[0] == TBST_CHILD)
      q = q->tbst_link[0];
    q->tbst_link[0] = p;
  }

p = s;

This code is included in 660.

4. If all the possible deletions from a given TBST are considered, then no link will be followed more than once to update a left thread, and similarly for right threads. Averaged over all the possible deletions, this is a constant. For example, take the following TBST:

Consider right threads that must be updated on deletion. Nodes 2, 3, 5, and 6 have right threads pointing to them. To update the right thread to node 2, we follow the link to node 1; to update node 3's, we move to 0, then 2; for node 5, we move to node 4; and for node 6, we move to 3, then 5. No link is followed more than once. Here's a summary table:

	Node	Right Thread Follows	Left Thread Follows
	0:	(none)	2, 1
	1:	(none)	(none)
	2:	1	(none)
	3:	0, 2	5, 4
	4:	(none)	(none)
	5:	4	(none)
	6:	3, 5	7
	7:	(none)	(none)

The important point here is that no number appears twice within a column.

Section 7.9

1. Suppose a node has a right thread. If the node has no left subtree, then the thread will be followed immediately when the node is reached. If the node does have a left subtree, then the left subtree will be traversed, and when the traversal is finished the node's predecessor's right thread will be followed back to the node, then its right thread will be followed. The node cannot be skipped, because all the nodes in its left subtree are less than it, so none of the right threads in its left subtree can skip beyond it.

2. The biggest potential for optimization probably comes from tbst_copy()'s habit of always keeping the TBST fully consistent as it builds it, which causes repeated assignments to link fields in order to keep threads correct at all times. The unthreaded BST copy function bst_copy() waited to initialize fields until it was ready for them. It may be possible, though difficult, to do this in tbst_copy() as well.

Inlining and specializing copy_node() is a cheaper potential speedup.