PATRICIA -Practical Algorithm to Retrieve Information Coded in Alphanumeric,D.R.Morrison (1968).
PATRICIA 木はトライに関連している。トライの問題はキーセットが疎であるとき、すなわち。トライの問題は、キーの集合がまばらな場合、すなわち、実際のキーが潜在的キーの集合の小さなサブセットを形成する場合、非常によくあることだが、トライの内部ノードの多く（大部分）は1つの子孫しか持たない。
Trieはキーのすべての部分（ビット、文字、…）を順番に使って、どのサブツリーを選択するかを決定します。PATRICIAツリーはその代わりに、キーのどの要素を次に使って分岐するかを（ノード内の位置を記憶することによって）指定します。
PATRICIAの索引はFredkinの二項対立構造とは異なり、索引には真の枝のみが記録される。このため、インデックスの行数は開始数の2倍となり、格納されるフレーズの長さに依存しない。
– Morrison 1968 pp520.
PATRICIAツリーは大きさが2のアルファベット上のキー（文字列）について作るのが最も簡単： {a,b} または {0,1} 。 しかし、例えばasciiのような2つ以上の要素を持つアルファベットの文字列は、大きい方のアルファベットの各文字の中のビットを取ることで、2つのアルファベットの文字列として扱うことができる。
次の例は、一連の挿入によるPATRICIA木の成長を示している。
C
o
m
p
u
t
e
r
–
S
c
i
e
n
c
e
empty -- initial state
12345 -- number character positionsinsert ababb -- the key
----> ababb
insert ababa; ababb~=ababaで検索終了。1番目の違いは5番目の位置なので。..
----> -- i.e. test position #5 . . a. . b . . ababa ababb
insert ba; has no position #5; can skip key positions but must test in order, so…
--------> . . . . . . ba . . . . . .ababa ababb
insert aaabba; search ends at ababb~=aaabba; can skip key positions but must test in order, so…キーポジションをスキップできるが、順番にテストしなければならない。
--------> . . . . . . ba . . . . . .aaabba . . . . . . ababa ababb
insert ab; abはababaとababbの接頭辞でもある;Triesと同様に中間ノードで終了させる機能を持たなければならない。
-------> . . . . . . ba . . . . . .aaabba --->ab . . . . . . . . . ababa ababb
ab のようなキーが他のキー、例えば `ababa’ の接頭辞である場合、様々な方法で処理することができます。 実際の、あるいは想定される終端文字、しばしば `$’ (Cやその近辺では`0′)はアルファベットの3番目の文字と考えることができますが、キーの終端にのみ出現することが許されます。 R. Morrison.PATRICIA -Practical Algorithm to Retrieve Information Coded in Alphanumeric.Jrnl. of the ACM, 15(4) pp514-534, Oct 1968
元々は、マークアップしたテキストを検索するインデックスとしてPATRICIAを発表している。
PATRICIAアルゴリズムやその他多くのアルゴリズムをわかりやすくコーディングしている。
要素（または要素へのポインタ）を内部の「フォーク」ノードに格納します。