Trie (تجربة البادئة) هي شجرة حيث يمثل كل edge حرفاً وكل مسار من الجذر يتكون من بادئة. الكلمات التي تشارك بادئة مشتركة تشارك نفس المسار، مما يجعل بحث البادئة سريعاً جداً.
الهيكل
text
Insert "cat", "car", "dog":
root
/ \
c d
| |
a o
/ \ |
t* r* g* (* marks end-of-word)
