Case Insensitive Ternary Search Tree
- by Yan Cheng CHEOK
I had been using Ternary Search Tree for a while, as the data structure to implement a auto complete drop down combo box. Which means, when user type "fo", the drop down combo box will display
foo
food
football
The problem is, my current used of Ternary Search Tree is case sensitive. My implementation is as follow. It had been used by real world for around 1++ yeas. Hence, I consider it as quite reliable.
My Ternary Search Tree code
However, I am looking for a case insensitive Ternary Search Tree, which means, when I type "fo", the drop down combo box will show me
foO
Food
fooTBall
Here are some key interface for TST, where I hope the new case insentive TST may have similar interface too.
/**
* Stores value in the TernarySearchTree. The value may be retrieved using key.
* @param key A string that indexes the object to be stored.
* @param value The object to be stored in the tree.
*/
public void put(String key, E value) {
getOrCreateNode(key).data = value;
}
/**
* Retrieve the object indexed by key.
* @param key A String index.
* @return Object The object retrieved from the TernarySearchTree.
*/
public E get(String key) {
TSTNode<E> node = getNode(key);
if(node==null) return null;
return node.data;
}
An example of usage is as follow. TSTSearchEngine is using TernarySearchTree as the core backbone.
Example usage of Ternary Search Tree
// There is stock named microsoft and MICROChip inside stocks ArrayList.
TSTSearchEngine<Stock> engine = TSTSearchEngine<Stock>(stocks);
// I wish it would return microsoft and MICROCHIP. Currently, it just return microsoft.
List<Stock> results = engine.searchAll("micro");
