Ternary search trees
About a year ago I was in pretty embarrassing situation because I had no clue what ternary search trees are and I had to write some code to implement efficient way of searching and storing strings. Jon Bentley’s and Robert Sedgewick’s article "Ternary Search Trees" was published in DDJ and is a very good paper to start with. Unfortunately to access the article you need to be DDJ subscriber but if the source code is enough for you then the demonstration program by authors is located here. Ternary search trees are extremely helpful in solving an entire class of searching related problems which may come up in real life.