I continued to search for a specific definition from past reputable sources to confirm what I had suspected, and I’m writing to provide my findings. Perhaps the most significant is the official paper defining PATRICIA, published by DR Morrison in October 1968s “Journal of the ACM”:
PATRICIA evolved from “A Library Automaton” [3] and other studies. …
Early in this evolution it was decided that the alphabet should be
restricted to a binary one. A theorem which strongly influenced this
decision is one which, in another form, is due to Euler. The theorem
states that if the alphabet is binary, then the number of branches is
exactly one less than the number of ends. Corollaries state that as
the library grows, each new end brings into the library with it
exactly one new branch, and each branch has exactly two exits. These
facts are very useful in the allocation of storage for the index. They
imply that the total storage required is completely determined by the
number of ends, and all of the storage required will actually be used.
This certainly contradicts points 2 and 3 of the libstdc++ reference. There’s further evidence in this paper, such as specific algorithm details, but the quote above should suffice.
There don’t appear to be any deviations from the official description in the Sedgewick quote, however. Based on that, the libstdc++ resource is certainly less valid than the Sedgewick resource.
solved Confusion regarding PATRICIA [closed]