I wrote something like this for contact auto completion - running in the browser we had to ensure that both tree construction was fast, and also that completion was instantaneous. So the next level of optimization is to amortize tree construction over searches (using the observation that most of the tree is never accessed)