Class TSTAutocomplete

  • public class TSTAutocomplete
    extends Object
    Ternary Search Trie implementation.
    See Also:
    • Method Detail

      • balancedTree

        public void balancedTree​(Object[] tokens,
                                 Object[] vals,
                                 int lo,
                                 int hi,
                                 TernaryTreeNode root)
        Inserting keys in TST in the order middle,small,big (lexicographic measure) recursively creates a balanced tree which reduces insertion and search times significantly.
        tokens - Sorted list of keys to be inserted in TST.
        lo - stores the lower index of current list.
        hi - stores the higher index of current list.
        root - a reference object to root of TST.
      • insert

        public TernaryTreeNode insert​(TernaryTreeNode currentNode,
                                      CharSequence s,
                                      Object val,
                                      int x)
        Inserts a key in TST creating a series of Binary Search Trees at each node. The key is actually stored across the eqKid of each node in a successive manner.
        currentNode - a reference node where the insertion will take currently.
        s - key to be inserted in TST.
        x - index of character in key to be inserted currently.
        currentNode The new reference to root node of TST
      • prefixCompletion

        public ArrayList<TernaryTreeNode> prefixCompletion​(TernaryTreeNode root,
                                                           CharSequence s,
                                                           int x)
        Auto-completes a given prefix query using Depth-First Search with the end of prefix as source node each time finding a new leaf to get a complete key to be added in the suggest list.
        root - a reference to root node of TST.
        s - prefix query to be auto-completed.
        x - index of current character to be searched while traversing through the prefix in TST.
        suggest list of auto-completed keys for the given prefix query.