एक trie (prefix tree) हा एक tree आहे जेथे प्रत्येक edge एक character प्रतिनिधित्व करतो आणि root पासूनचा प्रत्येक path एक prefix spell करतो. ज्या शब्दांचे prefix समान आहे ते समान path शेअर करतात, ज्यामुळे prefix lookups अत्यंत वेगवान आहेत.
संरचना
text
Insert "cat", "car", "dog":
root
/ \
c d
| |
a o
/ \ |
t* r* g* (* marks end-of-word)
