Let's see various data structures (e.g. Hashing, Binary Search Tree, Trie, Ternary Search Tree, BK- Tree ) which can be used to design data structure and their features and usage:


Spell Checker Using Hashing

Hashing

  • Dictionary
    • Will be stored in Hash Table
  • Spell Checker
    • Matching will be done by exact match.

  • Disadvantage
    • Does not support prefix search, where a user types a prefix and your dictionary shows all words starting with that prefix.

    • Doesn’t support efficient printing of all words in the dictionary in alphabetical order and nearest neighbor search.
  • Complexity
    • Seach - O(n)

Spell Checker Using ​Binary Search Tree

Binary Search Tree

  • Complexity
    • A well-balanced BST will need time proportional to M * log N,
      • M is maximum string length and
      • N is a number of keys in the tree.

 


Spell Checker Using Trie

Trie

  • Advantages
    • Can find all words beginning with a prefix.
  • Disadvantages
    • Tries is they require a lot of extra space.
  • Complexity
    • Search time: O(M) where M is the length of the string.

Spell Checker Using Ternary Search Tree

Ternary Search Tree

  • Advantages
    • More efficient than Trie.
  • Disadvantages
    • Ternary Search Tree requires a lot of extra space than Trie.

Spell Checker Using BK - Tree

BK- Tree (Burkhard-Keller Trees)

  • Time Complexity

    • O(log n)