[andrewparker]

The use of a phonebook analogy is clever, but I think the answerer should modify his answer to cover the O() running time of a trie data structure. A phonebook is essentially a trie. He talks about the "divide and conquor" approach to navigating a phonebook, but that's not how a computer would store the names. The way a computer navigates a phonebook would be interested in read about.

[yuliyp]

A phonebook as trie would only apply if you had tabs for each letter all the way down. It's a vector of pages.