A tree of letters: words that share a prefix share a path, so insert, search, delete and prefix queries cost one step per letter.
This interactive visualization needs JavaScript.