The Pile Approach To Data
> Type […] of accessing can result also in a ‘false’ statement, indicating the non-existence of the required relation in the Pile, i.e. getting a negative result takes the same effort as getting a positive result.
~
A search in Patricia’s tree is carried out as follows: Suppose we are looking up the word THE (bit pattern 10111 01000 00101). (TAOCP, v. 3, p. 499)
> At this point we compare the argument to the TEXT at the point specified in the current node (in this case node 𝛾). If it does not match, the argument is not the beginning of any key; **but if it does match, the argument is the beginning of every key represented by dotted links in node 𝛾 and its descendants** (namely THIS, THAT, THE). (TAOCP, v. 3, p. 499)