Подскажите, пожалуйста, как построить Patricia-дерево. И поиск в нем! Заранее благодарен!

Готовых, работающих сразу реализаций на Паскале не встречал, все время надо или что-то подкручивать, или переписывать почти с нуля.

С языка Cи переведешь?
Тогда ходи сюда: http://cprops.sourceforge.net/cp_trie.3.html

Или здесь: http://sourceware.org/ml/libc-alpha/2006-08/msg00058.html

(не справишься - скажи, где именно возникают сложности)

А можно расказать что такое Патрисия - дерево и по какому алгоритму строится