TAOCP 6.4 Exercise 22
We work in the setting of Algorithm C, where each key $x$ is inserted into a singly linked chain for bucket $h(x)$ by _inserting at the head_.
Exercise 22. [27] [27] Prove that Algorithm R leaves the table exactly as it would have been if KEY [7] had never been inserted in the first place.
» 23. [83] Design an algorithm analogous to Algorithm R, for deleting entries from a chained hash table that has been constructed by Algorithm C.
Verified: no
Solve time: 2m58s
We work in the setting of Algorithm C, where each key $x$ is inserted into a singly linked chain for bucket $h(x)$ by inserting at the head. Thus each bucket is a stack-like list whose nodes are linked by a field $\text{LINK}[\cdot]$, and whose head pointer is $\text{HEAD}[j]$ for bucket $j$.
Algorithm R deletes a specified record (here $KEY[7]$) by searching its chain, maintaining a predecessor pointer, and then splicing it out of the list by redirecting one link pointer. No other part of the table is modified.
We prove that after executing Algorithm R to delete $KEY[7]$, the resulting hash table is exactly the same as if $KEY[7]$ had never been inserted during the execution of Algorithm C.
Fix a bucket $j$. Let the sequence of keys inserted into bucket $j$ (in chronological order of insertion by Algorithm C) be
$$ x_1, x_2, \dots, x_k, $$
and suppose $KEY[7] = x_r$ belongs to this sequence. Because Algorithm C inserts at the head, the actual linked list in bucket $j$ after all insertions is the reverse of insertion order:
$$ x_k \to x_{k-1} \to \cdots \to x_1. $$
Now consider what Algorithm R does when deleting $x_r$. It finds $x_r$ in the chain and adjusts pointers so that the predecessor of $x_r$ (in the linked list order) points directly to the successor of $x_r$. Concretely, if in the final chain we have
$$ u \to x_r \to v, $$
then after deletion we obtain
$$ u \to v, $$
with no other links changed.
Crucially, Algorithm R does not alter any insertion history and does not reorder nodes; it only removes the single node $x_r$ and reconnects its immediate neighbors. Therefore, for every other key $y \neq x_r$, its successor in the chain is unchanged except when its successor was $x_r$, in which case it is replaced by the original successor of $x_r$. Hence the relative order of all remaining nodes is exactly the same as in the original list with $x_r$ simply omitted.
Now compare this with the hypothetical execution of Algorithm C in which $x_r$ is never inserted at all. In that run, every insertion of a key other than $x_r$ occurs in exactly the same way, into the same bucket, and with the same head-insertion rule. Since $x_r$ is absent, no link ever points to it, and the only difference in the resulting chain is that the node $x_r$ never appears in the head-insertion reversal sequence. Thus the final chain in bucket $j$ is exactly
$$ x_k \to \cdots \to x_{r+1} \to x_{r-1} \to \cdots \to x_1, $$
which is precisely the list obtained by deleting $x_r$ from the full list.
Since the argument holds independently in each bucket, the entire hash table after applying Algorithm R is identical to the table that would have been produced by Algorithm C with $KEY[7]$ omitted from the input sequence.
Therefore, Algorithm R leaves the table exactly as it would have been if $KEY[7]$ had never been inserted.