Trie (Prefix tree/Radix tree) is an efficient data structure for searching words in dictionaries, search complexity with Trie is linear in terms of word (or key) length to be searched.

Trie is an ordered tree data structure that is used to store a dynamic set or associative array where the keys are usually strings, node position in the tree defines the key with which it is associated. All the descendants of a node have a common prefix of the string associated with that node, and the root is associated with the empty string.

ref: https://en.wikipedia.org/wiki/Trie

Comparison:

If we store keys in the binary search tree, a well-balanced BST will need time proportional to M * log N, where M is maximum string length and N is a number of keys in the tree. Using Trie, we can search the key in O(M) time. So it is much faster than BST.

Hashing also provides word search in O(n) time on average. But the advantages of Trie are there are no collisions (like hashing) so worst case time complexity is O(n).

Advantages of Trie:

The most important thing is Prefix Search. With Trie, we can find all words beginning with a prefix (This is not possible with Hashing).

Disadvantages of Trie:

The only problem with Tries is they require a lot of extra space.

 

Trie is also known as Radix tree or Prefix tree.

Time Complexity:

  • Insert time: O(M) where M is the length of the string.
  • Search time: O(M) where M is the length of the string.
  • Space: O(ALPHABET_SIZE * M * N) where N is a number of keys in the trie, ALPHABET_SIZE is 26 if we are only considering upper case Latin characters.
  • Deletion time: O(M)

Example:

  • spell checking
  • prefix checking

 

 

Time Complexity

Space Complexity

 

Average

Worst

Worst

Data Structure 

 Access 
 Search 
 Insertion 
 Deletion 
 Access 
 Search 
 Insertion 
 Deletion 
 

Binary Search Tree

Θ(log(n)) Θ(log(n)) Θ(log(n)) Θ(log(n)) O(n) O(n) O(n) O(n) O(n)

Cartesian Tree

N/A Θ(log(n)) Θ(log(n)) Θ(log(n)) N/A O(n)  O(n)  O(n)  O(n)

B-Tree

Θ(log(n)) Θ(log(n)) Θ(log(n)) Θ(log(n)) O(log(n)) O(log(n)) O(log(n)) O(log(n)) O(n)

Red-Black Tree

Θ(log(n)) Θ(log(n)) Θ(log(n)) Θ(log(n)) O(log(n)) O(log(n)) O(log(n)) O(log(n)) O(n)

Splay Tree

N/A Θ(log(n)) Θ(log(n)) Θ(log(n)) N/A O(log(n)) O(log(n)) O(log(n)) O(n)

AVL Tree

Θ(log(n)) Θ(log(n)) Θ(log(n)) Θ(log(n)) O(log(n)) O(log(n)) O(log(n)) O(log(n)) O(n)

KD Tree

Θ(log(n)) Θ(log(n)) Θ(log(n)) Θ(log(n)) O(n) O(n) O(n) O(n) O(n)